2
$\begingroup$

I was trying to solve the problem: How many ways are there to pick a set of r out of a collection of n objects? and I found something strange. Instead of using combinatorics, I solved the issue by basically counting in a systemically way, and I found that the answer is: $$ \sum_{a_1 = 1}^{n-r+1} (\sum_{a_2 = 1}^{a_1}(\sum_{a_3=1}^{a_2}(\sum_{a_4 = 1 }^{a_3}...(\sum_{a_{r-1}=1}^{a_{r-2}}a_{r-1})....)))) $$ So I concluded that the expression above is equal to $^nC_r$ for every $r \leq n/2$.

Basically, there are many layers to the summation process and the number of layers is r-1. For example: $$^7C_2 = 6+5+4+3+2+1 = 21$$
$$^7C_3 = (5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+(1) = 35 $$ or: $$^9C_4 = [(6+5+4+3+2+1)+(5+4+3+2+1)+...+(2+1)+1] +[(5+4+3+2+1)+ ...+(2+1)+1] + [(4+3+2+1)+...]+[(3+2+1)+...]+[(2+1)+1]+[1] = 126$$

In $^7C_2$, the number of layers was 1, in $^7C_3$, it was 2, and in $^9C_4$, it was 3.

I apologize for the weird notation and the long examples but I don't know how to write the expression in the neatest way possible. I derive the expression above not directly but by solving a problem in two ways so I was wondering is it really valid and if so, are there any nicer way to write it down. Can you derive it using only algebraic transformation? Thank you for your help.

$\endgroup$
0
$\begingroup$

Clearly, the number of r-subsets out of the set $\{1,2, \cdots,n\}$ corresponds to $$ {\rm N}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ 1 \le {\rm integer}\;x_{\,k} \le n \hfill \cr 1 \le \;x_{\,1} < x_{\,2} < \cdots \, < x_{\,r} \le n \hfill \cr} \right. $$

This means that you can rewrite it as $$ \eqalign{ & N(r,n) = {\rm N}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ 1 \le {\rm integer}\;x_{\,k} \le n \hfill \cr 1 \le \;x_{\,1} < x_{\,2} < \cdots \, < x_{\,r} \le n \hfill \cr} \right. = \cr & = \sum\limits_k {} {\rm N}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ 1 \le {\rm integer}\;x_{\,k} \le n \hfill \cr x_{\,1} = k \hfill \cr k + 1 \le \;x_{\,2} < \cdots \, < x_{\,r} \le n \hfill \cr 1 \le \;k\left( { \le n - r + 1} \right) \le n \hfill \cr} \right. = \cr & = \sum\limits_k {} {\rm N}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ 1 \le {\rm integer}\;x_{\,1} ,y_{\,k} \le n \hfill \cr 1 \le \;x_{\,1} \le k \hfill \cr 1 \le \;y_{\,1} < \cdots \, < y_{\,r - 1} \le n - k \hfill \cr 1 \le \;k\left( { \le n - r + 1} \right) \le n \hfill \cr} \right. \cr & \Rightarrow \;\quad N(r,n) = \sum\limits_{k = 1}^{n - r + 1} {N(r - 1,n - k)} = \sum\limits_{k = r - 1}^{n - 1} {N(r - 1,k)} \cr} $$

The recursion is the "hokey stick" identity $$ \left( \matrix{ n \cr r \cr} \right)\quad \left| {\,2 \le r} \right.\quad = \sum\limits_{k = 1}^{n - r + 1} {\left( \matrix{ n - k \cr r - 1 \cr} \right)} = \sum\limits_{\left( {0 \le } \right)\,k = r - 1}^{n - 1} {\left( \matrix{ k \cr r - 1 \cr} \right)} $$

You can nest the recursion in various ways $$ \eqalign{ & \Rightarrow \;\quad N(r,n) = \sum\limits_{k = 1}^{n - r + 1} {N(r - 1,n - k)} = \cr & = \sum\limits_{k = 1}^{n - r + 1} {\sum\limits_{j = 1}^{n - k - r + 1} {N(r - 2,n - k - j)} } = \cr & = \sum\limits_{k = 1}^{n - r + 1} {\sum\limits_{i = k + 1}^{n - r + 1} {N(r - 2,n - i)} } = \cr & = \sum\limits_{k = 1}^{n - r + 1} {\sum\limits_{j = r - 1}^{n - k - 1} {N(r - 2,j)} } = \cr & = \cdots \cr} $$

But to reach to yours, we have better figure it through the "hokey stick" identity $$ \eqalign{ & \sum\limits_{\,k_{\,1} = 0}^{k_{\,2} } {\left( \matrix{ k_{\,1} \cr 0 \cr} \right)} = \left( \matrix{ k_{\,2} + 1 \cr 1 \cr} \right) \cr & \sum\limits_{\,k_{\,2} = 0}^{k_{\,3} } {\sum\limits_{\,k_{\,1} = 0}^{k_{\,2} } {\left( \matrix{ k_{\,1} \cr 0 \cr} \right)} } = \left( \matrix{ k_{\,3} + 2 \cr 2 \cr} \right) \cr & \quad \quad \vdots \cr & \sum\limits_{k_r = 0}^{k_{\,r + 1} = n - r} { \cdots \sum\limits_{\,k_2 = 0}^{k_{\,3} } {\sum\limits_{\,k_{\,1} = 0}^{k_{\,2} } {\left( \matrix{ k_{\,1} \cr 0 \cr} \right)} } } = \sum\limits_{k_r = 0}^{k_{\,r + 1} = n - r} { \cdots \sum\limits_{\,k_2 = 0}^{k_{\,3} } {\sum\limits_{\,k_{\,1} = 0}^{k_{\,2} } {\left( \matrix{ k_{\,1} \cr 0 \cr} \right)} } } = \left( \matrix{ n \cr r \cr} \right) \cr} $$

and rewriting the starting recursion a bit differently $$ \eqalign{ & \left( \matrix{ n + 1 \cr r + 1 \cr} \right) = \sum\limits_{\left( {1 \le } \right)\,k = r}^n {\left( \matrix{ k \cr r \cr} \right)} = \sum\limits_{\,k = 1}^n {\left( \matrix{ k \cr r \cr} \right)} \quad \left| {\,1 \le r} \right. \cr & \quad \quad \Downarrow \cr & \sum\limits_{\,k_{\,1} = 0}^{k_{\,2} } {\left( \matrix{ k_{\,1} \cr 1 \cr} \right)} = \left( \matrix{ k_{\,2} + 1 \cr 2 \cr} \right) \cr & \sum\limits_{\,k_{\,2} = 1}^{k_{\,3} } {\sum\limits_{\,k_{\,1} = 1}^{k_{\,2} } {\left( \matrix{ k_{\,1} \cr 0 \cr} \right)} } = \left( \matrix{ k_{\,3} + 2 \cr 3 \cr} \right) \cr & \quad \quad \vdots \cr & \left( \matrix{ n \cr r \cr} \right) = \sum\limits_{k_{r - 1} = 1}^{k_{\,r} = n - r + 1} { \cdots \sum\limits_{\,k_{\,2} = 1}^{k_{\,3} } {\sum\limits_{\,k_1 = 1}^{k_{\,2} } {\left( \matrix{ k_{\,1} \cr 1 \cr} \right)} } } = \sum\limits_{k_{r - 1} = 1}^{k_{\,r} = n - r + 1} { \cdots \sum\limits_{\,k_{\,2} = 1}^{k_{\,3} } {\sum\limits_{\,k_1 = 1}^{k_{\,2} } {k_{\,1} } } } \quad \left| {\,1 \le r} \right. \cr} $$ we finally get your formula.

$\endgroup$
  • $\begingroup$ Is there a way to express the recursion sum in a "neat" notation? $\endgroup$ – random Oct 9 at 13:14
  • $\begingroup$ @ random what do you mean by "neat" ? $\endgroup$ – G Cab Oct 9 at 13:15
  • $\begingroup$ Because I don't know whether or not I'm allowed to write a series of sigmas like that, so is there a shorter way to express a recursion process? $\endgroup$ – random Oct 9 at 13:19
  • $\begingroup$ @random: I recasted my answer to better match your formula. $\endgroup$ – G Cab Oct 9 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.