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