# Cardinality of a certain set

I was wondering if there's a formula for the cardinality of the set $A_k=\{(i_1,i_2,\ldots,i_k):1\leq i_1<i_2<\cdots<i_k\leq n\}$ for some $n\in\mathbb{N}$. I calculated that $A_2$ has $n(n-1)/2$ elements, and $A_3=\sum_{j=2}^{n-2}\frac{(n-j)(n-j+1)}{2}$. As you can see, the cardinality of $A_3$ is already represented by a not so nice formula.

Is there a general formula?

-
Why isn't it just $\binom{n}{k}$ (choose $k$ distinct numbers and sort them)? – Srivatsan Sep 29 '11 at 18:58
Explicitly, you have $A(n,k) = \frac{n!}{(n-k)!k!}$. Your addition formula looks like an iteration of the well-known identity $$\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}.$$ – Arturo Magidin Sep 29 '11 at 19:22
Of course! Thanks, my counting skills are a bit rusty. – rfauffar Sep 29 '11 at 19:24

You can also get it by induction using the fairly obvious recurrence $$A_{k+1}(n) = \sum_{i=k}^{n-1}A_k(i):$$ if $A_k(i) = \dbinom{i}{k}$, then $$A_{k+1}(n) = \sum_{i=k}^{n-1}\binom{i}{k} = \binom{n}{k+1}$$ by one of the ‘hockey stick’ identities.
The $A_k$ can also be expressed as $\{(i_1,i_2,\ldots,i_k)\;|\; 1\leq i_1\leq n-(k-1),i_1+1\leq i_2\leq n-(k-2),\ldots,i_{k-1}+1\leq i_k\leq n\}$. This way, it is clear how many choices there are for each $i_j$. Multiplying will give you the ol' $n \choose k$ formula.