3
$\begingroup$

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 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?

  • 0
    Of course! Thanks, my counting skills are a bit rusty.2011-09-29

2 Answers 2

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.

  • 0
    Thanks! 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!

  • 0
    The inequalities are not independent, so I don't see a clear way to simply multiply interval sizes together.2011-09-29