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
6  
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. –  Robert Auffarth 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. –  Robert Auffarth 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

 
discard

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.