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 Is there a general formula?
Cardinality of a certain set
3
$\begingroup$
combinatorics
elementary-set-theory
-
6Why isn't it just $\binom{n}{k}$ (choose $k$ distinct numbers and sort them)? – 2011-09-29
-
0Explicitly, 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}.$$ – 2011-09-29
-
0Of course! Thanks, my counting skills are a bit rusty. – 2011-09-29
2 Answers
2
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.
-
0Thanks! It's really easy to prove it that way. – 2011-09-30
1
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!
-
0The inequalities are not independent, so I don't see a clear way to simply multiply interval sizes together. – 2011-09-29