Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
Thanks! It's really easy to prove it that way. –  rfauffar Sep 30 '11 at 12:48

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.

edit: Apologies. It's not clear to me right now how to do the multiplication!

share|improve this answer
The inequalities are not independent, so I don't see a clear way to simply multiply interval sizes together. –  anon Sep 29 '11 at 22:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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