I recently started to look into restricted compositions and I found a formula for a problem that I was trying to solve, the Formula E at page 441 of this document.

In my case I have n =8, k=3, t=1 and w=4.

If I expand the summation I get negative integers in the polynomial and I don't know how to handle them in a binomial coefficient. Can someone give me an example of the correct way of expanding and solving the formula for this case?


1 Answer 1


Note that $t$ does not appear in formula (E). The useful definition of $\binom{n}k$ here is

$$\binom{n}k=\frac{n^{\underline k}}{k!}\;,$$

where $x^{\underline k}=\prod_{i=0}^{k-1}(x-i)$. Thus,

$$\begin{align*} \sum_{j=0}^3(-1)^j\binom3j\binom{8-4j-1}2&=\binom30\binom72-\binom31\binom32+\binom32\binom{-1}2-\binom33\binom{-5}2\\ &=1\cdot21-3\cdot3+3\cdot\frac{(-1)(-2)}2-1\cdot\frac{(-5)(-6)}2\\ &=21-9+3-15\\ &=0\;. \end{align*}$$

Added: However, I did that strictly on the basis of the formula. Now that I’ve taken a look at what it’s supposed to be counting, something for which I’ve previously worked out the formula, I realize that Abramson must be using a non-standard definition of $\binom{n}k$, taking it to be $0$ unless $0\le k\le n$. With that convention the last two terms in the summation above become $0$, and the whole expression then evaluates to $12$. This is correct: the compositions are the $6$ permutations of $1+3+4$, the $3$ permutations of $2+2+4$, and the $3$ permutations of $2+3+3$.

And on further investigation, I see that Abramson actually does specify his convention at the very end of the Introduction.

  • $\begingroup$ yes that's the answer I arrived at as well. However, that's not right, is it? Since there are compositions that lead to a sum of 8. E.g. 2+2+4 or 1+3+4 and more. Or am I understanding something incorrectly? $\endgroup$
    – mbbce
    Feb 10, 2016 at 8:19
  • $\begingroup$ @MB_CE: Found the problem and adjusted my answer correspondingly. $\endgroup$ Feb 10, 2016 at 16:19
  • $\begingroup$ Yes he does. My bad for not reading the whole document. I have another follow up question about the Section 3 formula 3.2. Regarding the Summation over all taken over all j-combinations. I am a little uncertain about it. So, I will link another question. $\endgroup$
    – mbbce
    Feb 10, 2016 at 17:03
  • $\begingroup$ math.stackexchange.com/questions/1649372/… here is the link to the follow up question. $\endgroup$
    – mbbce
    Feb 10, 2016 at 17:39

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.