1
$\begingroup$

Consider a set $A$ of $k$ distinct integers (perhaps $1, 2, 3, \ldots, k$).

Let $O = \{\left(a_1, \ldots , a_n\right) \mid a_1 < a_2 < \cdots < a_n \,\}, \quad n<k$ be a set of tuples containing different elements from $A$, such that they are sorted.

Do you have any ideas as to calculate the cardinality of $O$? Or maybe the fraction of ordered tuples among all possible tuples of length $n$ with distinct elements from $A$.

If it's hard to derive as is, it would also be possible to assume $k \to \infty$.

$\endgroup$
  • $\begingroup$ Each set of $n$ distinct numbers gives rise to exactly one ordered $n$-tuple, and there are $n!$ ways to arrange it in an $n$-tuple without caring about the order. $\endgroup$ – Daniel Fischer Sep 7 '13 at 19:46
  • $\begingroup$ Presumably $n$ is variable. Answer is simplest if you allow the empty sequence. $\endgroup$ – André Nicolas Sep 7 '13 at 19:56
  • $\begingroup$ And $k \choose n$ ways to choose numbers from $A$? So $|O| = {k \choose n}$ ? $\endgroup$ – wh1t3cat1k Sep 7 '13 at 20:28
4
$\begingroup$

The cardinality of $O$ is easy: It's just the number of subsets of a set of size $k$, so that's $2^k$.

If you want the fraction of members of $O$ among all sequences, then you also need the number of sequences.

As phrased, the word "different" is redundant, since the inequality $a_1<a_2<\cdots < a_n$ certainly cannot hold unless they are different. But I'm going to surmise at this point that when you wrote "among all sequences" and later wrote "different", you also meant that the members of each sequence "among all sequences" are all different.

The number of sequences of length $n$ in which all elements are different members of a set of size $k$ is $\dfrac{k!}{(k-n)!}$. Summing that from $n=0$ to $n=k$ gives the total number of sequences of distinct elements: $$ \sum_{n=0}^k \frac{k!}{(k-n)!}=k!\sum_{n=0}^k \frac{1}{(k-n)!}. $$ Now do a substitution $m=k-n$ and notice that as $n$ goes from $0$ to $k$, then $m$ goes from $k$ to $0$, so the last expression displayed above is equal to $$ k!\sum_{m=0}^k \frac{1}{m!}. \tag{1} $$ Now notice that $$ k!\sum_{m=0}^\infty \frac{1}{m!} = k!e, $$ so the expression in $(1)$ is approximately $k!e$, and the error is $$ k! \sum_{m=k+1}^\infty \frac{1}{m!} = \frac{1}{k+1}+\frac{1}{(k+1)(k+2)}+\cdots. $$ This is bounded above by $$ \sum_{m=1}^\infty \frac{1}{(k+1)^m} = \frac1k < \frac12. $$

Therefore the number of sequences with distinct terms in a set of size $k$ is $k!e$ rounded to the nearest integer.

$\endgroup$
  • $\begingroup$ If I'm not mistaken, the sequence whose $k$th term is the nearest integer to $k!e$ satisfies a recursion formula: $x_{k+1}=(k+1)x_k+1.$ ${}\qquad{}$ $\endgroup$ – Michael Hardy Sep 8 '13 at 4:51
  • $\begingroup$ Michael, brilliant result, thanks, though (sorry for bad problem formulation) not what I expected :) I have to think about that one - because I really presumed that $n$ is not a variable but a fixed number (and $k$ as well). Different elements means that the elements inside the sequence are different. $\endgroup$ – wh1t3cat1k Sep 8 '13 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.