How many instances of number $k$ in sums that add up to number $n$?

Question

Task in Combinatorics course:

$1 \leq k < n$. Prove that the number $k$ can be found $(n-k+3)2^{n-k-2}$ times in sums that add up to $n$.

Example: $n=4, k=2$.

$1+1+2$

$1+2+1$

$2+1+1$

$2+2$

These are the sums that add up to $4$ and the number $2$ can be found $5$ times.

Thus far, I have tried making sense of that formula. $n-k$ is the number or countables left if we have one $k$. $2^{n-1}$ is how many sums that add up to $n$ there are in total so in the second half of the formula it could be $2^{n-1}2^{k-1}$ that would add up to $2^{n-k-2}$. But none of that comes together. Why would there be a $+3$ in the first half.

Answer 1

A composition which sums to $n$ corresponds to the placement of either a comma or an addition sign in each of the $n - 1$ spaces between successive ones in a row of $n$ ones.
$$1 \square 1 \square 1 \square \cdots \square 1 \square 1 \square 1$$ Since there are $2$ ways to fill each of the $n - 1$ spaces, there are $2^{n - 1}$ compositions of the number $n$.

We are told that one of the summands is $k$. That means there is a block of $k$ consecutive ones. Such a block must begin in one of the first $n - k + 1$ positions. Of these, two are at the ends of the row and $n - k - 1$ include neither end of the row. We will consider cases, depending on the position of the block.

If the first summand is $k$, there is a block of exactly $k$ ones at the start of the row. That block must be immediately followed by an addition sign. That leaves $n - k$ ones and $n - k - 1$ spaces where either a comma or an addition sign can be placed. Hence, there are $2^{n - k - 1}$ such compositions.

If the last summand is $k$, there is a block of exactly $k$ ones is at the end of the row. That block must be immediately preceded by an addition sign. That leaves $n - k$ ones and $n - k - 1$ spaces where either a comma or an addition sign can be placed. Hence, there are $2^{n - k - 1}$ such compositions.

If the summand $k$ does not appear in the first or last position of the composition, there are $n - k - 1$ places where the block of exactly $k$ consecutive ones could begin. The block must be immediately preceded and immediately followed by addition signs. That leaves $n - k$ ones and $n - k - 2$ spaces where either a comma or an addition sign can be placed. Hence, there are $(n - k - 1)2^{n - k - 2}$ such compositions.

Since these cases are mutually exclusive and exhaustive, the number of times the summand $k$ appears in compositions of $n$ is \begin{align*} 2 \cdot 2^{n - k - 1} + (n - k - 1)2^{n - k - 2} & = 4 \cdot 2^{n - k - 2} + (n - k - 1)2^{n - k - 2}\\ & = (n - k + 3)2^{n - k - 2} \end{align*} Note that we have implicitly used the hypothesis that $k < n$ in order to separate the cases where $k$ is the first summand, $k$ is the last summand, and $k$ is neither the first nor last summand.

Answer 2

We have the marked generating function

$$Q(z,u) = \sum_{q=1}^n \left(z+\cdots+z^{k-1} + u z^k + z^{k+1} + \cdots\right)^q.$$

The term $u^p z^m$ represents a composition that sums to $m$ and contains $p$ instances of the number $k.$ Hence we differentiate with respect to $u$ and set $u=1$ to get the count. Differentiation yields

$$\sum_{q=1}^n q \left(z+\cdots+z^{k-1} + u z^k + z^{k+1} + \cdots\right)^{q-1} z^k.$$

Set $u=1$ to get

$$[z^n] z^k \sum_{q=1}^n q \frac{z^{q-1}}{(1-z)^{q-1}}.$$

Note that with $k\ge 1$ we may extend $q$ beyond $n$ without getting any additional contributions to the coefficient extractor. This yields

$$[z^n] z^k \sum_{q\ge 1} q \frac{z^{q-1}}{(1-z)^{q-1}} = [z^{n-k}] \frac{1}{(1-z/(1-z))^2} \\ = [z^{n-k}] (1-z)^2 \frac{1}{(1-2z)^2} \\ = [z^{n-k}] \frac{1}{(1-2z)^2} - 2 [z^{n-k-1}] \frac{1}{(1-2z)^2} + [z^{n-k-2}] \frac{1}{(1-2z)^2} \\ = (n-k+1) 2^{n-k} - 2(n-k) 2^{n-k-1} + (n-k-1) 2^{n-k-2} \\ = (4n-4k+4-4n+4k+n-k-1) 2^{n-k-2} = (n - k + 3) 2^{n-k-2}.$$

This is with $n-k\ge 2.$ We get for $k=n-1$

$$(n-k+1) 2^{n-k} - 2(n-k) 2^{n-k-1} = 2\times 2 - 2 = 2$$

which is true because the compositions are $(1,n-1)$ and $(n-1,1).$ We get for $k=n$

$$(n-k+1) 2^{n-k} = 1$$

which is also true because there is just one composition $(n).$

Answer 3

Fix $k$ and let $a_n$ be the number of $k$s that appear among all ($2^{n-1}$) ordered partitions of $n$. Then $a_n=0$ for $n<k$, $a_k=1$, and conditioning on the first part $i$ yields recurrence relation $$a_n = \sum_{i=1}^n ([i=k]2^{n-i-1} + a_{n-i}) = 2^{n-k-1} + \sum_{i=1}^{n-k} a_{n-i} \quad \text{for $n > k$}.$$ Let $A(z) = \sum_{n=0}^\infty a_n z^n$ be the ordinary generating function. Then \begin{align} A(z) &= \sum_{n=0}^{k-1} 0 z^n + 1z^k + \sum_{n=k+1}^\infty \left(2^{n-k-1} + \sum_{i=1}^{n-k} a_{n-i}\right) z^n \\ &= z^k + \sum_{n=k+1}^\infty 2^{n-k-1} z^n + \sum_{i=1}^\infty z^i \sum_{n=i+k}^\infty a_{n-i} z^{n-i} \\ &= z^k + \frac{z^{k+1}}{1-2z} + \sum_{i=1}^\infty z^i A(z) \\ &= z^k + \frac{z^{k+1}}{1-2z} + \frac{zA(z)}{1-z}. \end{align} So \begin{align} A(z) &= \frac{z^k(1-z)^2}{(1-2z)^2} \\ &= z^k \left(\frac{1}{4}+\frac{1/2}{1-2z}+\frac{1/4}{(1-2z)^2}\right) \\ &= z^k \left(\frac{1}{4}+\frac{1}{2}\sum_{n=0}^\infty(2z)^n+\frac{1}{4}\sum_{n=0}^\infty\binom{n+1}{1}(2z)^n\right) \\ &= z^k \left(1+\frac{1}{2}\sum_{n=1}^\infty(2z)^n+\frac{1}{4}\sum_{n=1}^\infty(n+1)(2z)^n\right) \\ &= z^k +\sum_{n=k+1}^\infty \left(2^{n-k-1}+(n-k+1)2^{n-k-2}\right)z^n \\ &= z^k +\sum_{n=k+1}^\infty (n-k+3)2^{n-k-2}z^n, \end{align} which immediately implies that $a_n = (n-k+3)2^{n-k-2}$ for $n>k$.