I found a formula for a problem that I was trying to solve, the Formula 3.2 in Section 3 at page 441 of this document.I am a little unsure about the "Summation over all j-combinations". Here is what I think but I am unsure about it. For example for k=3

$$\begin{align*}F(n,k;h_1,p_1;h_2,p_2;h_3,p_3)&=\binom{n-h+k-1}{k-1}+(-1)^1\binom{n-h+k-j-1-(p_1-h_1)}{k-1}+(-1)^2\binom{n-h+k-j-1-(p_1-h_1)-(p_2-h_2)}{k-1}+(-1)^3\binom{n-h+k-j-1-(p_1-h_1)-(p_2-h_2)-(p_3-h_3)}{k-1} \end{align*}$$

Is this the correct expansion? According to a couple of numerical solutions that I have tried it works for me. But I just want to be sure before I actually use it.

Edit: So this is the correct expansion from what I understand? $$\begin{align*}F(n,k;h_1,p_1;h_2,p_2;h_3,p_3)=\binom{n-h+k-1}{k-1}+(-1)^1\Bigg(\binom{n-h+k-j-1-(p_1-h_1)}{k-1}+\binom{n-h+k-j-1-(p_2-h_2)}{k-1}+\binom{n-h+k-j-1-(p_3-h_3)}{k-1}\Bigg)+(-1)^2\Bigg(\binom{n-h-(p_1-h_1)-(p_2-h_2)}{k-1}+\binom{n-h-(p_2-h_2)-(p_3-h_3)}{k-1}+\binom{n-h-(p_1-h_1)-(p_3-h_3)}{k-1}\Bigg)+(-1)^3\binom{n-h+k-j-1-(p_1-h_1)-(p_2-h_2)-(p_3-h_3)}{k-1} \end{align*}$$


1 Answer 1


Since $k=3$, there are $\binom31=1$ $1$-combinations: $\{1\}$, $\{2\}$, and $\{3\}$. There are $\binom32=3$ $2$-combinations: $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$. And there is $\binom33=1$ $3$-combination, $\{1,2,3\}$. For $j=2$, for instance, $k-j-1=0$, so the $\Sigma^*$ expression expands to

$$\begin{align*} \binom{n-h-(p_1-h_1)-(p_2-h_2)}2&+\binom{n-h-(p_1-h_1)-(p_3-h_3)}2\\ &+\binom{n-h-(p_2-h_2)-(p_3-h_3)}2\;, \end{align*}$$

where the first term is for $\{1,2\}$, the second for $\{1,3\}$, and the third for $\{2,3\}$.

The $j=1$ expansion will also have three terms, while the $j=3$ expansion will have only one.

  • $\begingroup$ So, according to what I understand from your answer. The edit that I have done to the question is the correct expansion? $\endgroup$
    – mbbce
    Feb 10, 2016 at 18:20
  • $\begingroup$ @MB_CE: Yes, it looks right. $\endgroup$ Feb 10, 2016 at 18:23
  • $\begingroup$ Great. Thanks a lot. I thought at first that it might be the expansion that you have suggested. However, the numerical test led me astray. Definitely because of the values that I chose to give the expansion a little try. $\endgroup$
    – mbbce
    Feb 10, 2016 at 18:25
  • $\begingroup$ @MB_CE: You’re very welcome. $\endgroup$ Feb 10, 2016 at 18:25

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.