Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
