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?

  • 6
    Why isn't it just $\binom{n}{k}$ (choose $k$ distinct numbers and sort them)?2011-09-29
  • 0
    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}.$$2011-09-29
  • 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