# Expanding Restricted Compositions formula

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?

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.

• 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? Feb 10, 2016 at 8:19
• @MB_CE: Found the problem and adjusted my answer correspondingly. Feb 10, 2016 at 16:19
• 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. Feb 10, 2016 at 17:03
• math.stackexchange.com/questions/1649372/… here is the link to the follow up question. Feb 10, 2016 at 17:39