Mistake in the closed-form formula for the number of restricted compositions?

Question

I'm interested in a closed-form formula for the number of compositions of an integer n with k parts where each part is not greater than w: C(n,k,w). [Abramson 1976] contains formula E at page 441, but I always get only $0$ as results. Already formula 3.2 seems to have only 0 as results. Where is the mistake?

[Abramson 1976] Abramson, M.: Restricted combinations and compositions. Fibonacci Q. 14 (1976) (5) 439-452

Answer 1

Formula (E) says that the number of $k$-compositions $a_1+\ldots+a_k$ of $n$ such that $1\le a_i\le w$ for $i=1,\ldots,k$ is given by the sum

$$\sum_{j=0}^k(-1)^j\binom{k}j\binom{n-jw-1}{k-1}\;.\tag{1}$$

Let’s try it with $k=w=3$ and $n=7$. The $3$-compositions of $7$ bounded by $3$ are $1+3+3$, $3+1+3$, $3+3+1$, $2+2+3$, $2+3+2$, and $3+2+2$, so there are $6$ of them, and

$$\sum_{j=0}^3(-1)^j\binom3j\binom{7-3j-1}2=\binom62-3\binom32+3\binom02-\binom{-3}2=15-9+0=0=6\;,$$

as it should.

In fact $(1)$ is definitely correct. In an earlier answer I noted that an inclusion-exclusion calculation shows that the number of weak $k$-compositions of $m$ with an upper bound of $b$ on each term is

$$\sum_j(-1)^j\binom{k}j\binom{m+k-j(b+1)-1}{k-1}\;.\tag{2}$$

Let $m=n-k$ and $b=w-1$. There is an obvious bijection between $k$-compositions of $n$ whose terms are bounded by $w$ and weak $k$-compositions of $m=n-k$ whose terms are bounded by $b=w-1$: just subtract $1$ from each term of the $k$-composition to get the corresponding weak $k$-composition. Thus, by $(2)$ there are

$$\sum_j(-1)^j\binom{k}j\binom{m+k-j(b+1)-1}{k-1}=\sum_j(-1)^j\binom{k}j\binom{n-jw-1}{k-1}$$

$k$-compositions of $n$ bounded by $w$, and $(1)$ follows from $(2)$.