Counting number of occurences

Question

Let $1\leq k\leq n$. We find all finite sequences of positive integers with sum $n$. Suppose that the term $k$ occurs a total of $T(n, k)$ times in all these sequences.

Find $T(n, k)$.

As an example to make things more clear: $T(3,1)=5$, $T(3,2)=2$ and $T(3,3)=1$

This on base of the sums $1+1+1=3$, $1+2=3$, $2+1=3$ and $3=3$.

In this I'm pretty sure we can do this by choosing $r$ $x$'s and letting them be equal to $k$ individually, in groups of $2$ and so on. We can then sum it over $r$. But I'm unable to write a solution and obtain an expression for $T(n,k)$.

Thanks in advance!

Answer 1

The number $T(n,k)$ can be calculated from the following recurrence relation:

$$T(n, k)=2^{n-k-1}+\sum_{i=1}^{n}T(n-i, k)\tag{1}$$

...with the following "boundary" conditions:

$$T(k, k)=1$$

$$T(n, k)=0 \quad\text{for} \quad n<k$$

Proof:

To evaluate $T(n, k)$ we need all sequences with sum equal to $n$. That sum can either start with $k$ or not. In how many sequencies will $k$ appear as a starting one? Obviously, the number of such sequencies is equal to the number of sequencies with the sum equal to $n-r$.

If you have $p$ members of the sequence, it's like splitting a group of $n-r$ elements with $p-1$ dividers. And you can put those dividers in $n-r-1$ different places. So the number of sequencies with $p$ terms is:

$$\binom{n-r-1}{p-1}$$.

The total number of sequencies starting with $r$ is therefore:

$$\sum_{p=1}^{n-r}\binom{n-r-1}{p-1}=2^{n-r-1}\tag{2}$$

On top of that we should add a number of appearances of $k$ in all shorter sequences. Shorter sequencies are defined by picking the first number of the sequence, say $i$, between 1 and $n$ and counting the number of appearances of $k$ in a sequence with sum $n-i$. That number of appearances is given with the following sum:

$$\sum_{i=1}^{n}T(n-i, k)\tag{3}$$

Add (2) and (3) and you get (1).

A little play with Mathematica:

t[n_, k_] := Sum[t[n - i, k], {i, 1, n}] + 2^(n - k - 1)
t[n_, k_] := 1 /; n == k
t[n_, k_] := 0 /; n < k

$$ \begin{matrix} k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ n=1 & 1 \\ n=2 & 2 & 1 \\ n=3 & 5 & 2 & 1 \\ n=4 & 12 & 5 & 2 & 1 \\ n=5 & 28 & 12 & 5 & 2 & 1 \\ n=6 & 64 & 28 & 12 & 5 & 2 & 1 \\ n=7 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\ n=8 & 320 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\ n=9 & 704 & 320 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\ n=10 & 1536 & 704 & 320 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\ \end{matrix} $$

The sequence 1, 2, 5, 12, 28, 64, 144, 320, 704, 1536... is also described in OEIS A045623 as "Number of 1's in all compositions of n+1".

OEIS also states that for $n>1$:

$$T(n,1)=(n+2)\times2^{n-3}$$

$$$$

Answer 2

With $q$ the length of the sequence and $k$ marked with $u$ we get the generating function

$$G(z, u) = \sum_{q\ge 0} (z+z^2+\cdots+uz^k+\cdots)^q \\ = \sum_{q\ge 0} z^q (1+z+\cdots+uz^{k-1}+\cdots)^q \\ = \sum_{q\ge 0} z^q \left(\frac{1}{1-z} + (u-1)z^{k-1}\right)^q \\ = \frac{1}{1-z(1/(1-z)+(u-1)z^{k-1})} \\ = \frac{1-z}{1-z-z(1+(u-1)(1-z)z^{k-1})}.$$

The desired quantity is given by

$$[z^n] \left. \frac{\partial}{\partial u} G(z, u)\right|_{u=1} \\ = [z^n] \left. \frac{1-z}{(1-z-z(1+(u-1)(1-z)z^{k-1}))^2} (z (1-z) z^{k-1})\right|_{u=1} \\ = [z^n] \frac{1-z}{(1-2z)^2} (z (1-z) z^{k-1}) \\ = [z^n] \frac{1-2z+z^2}{(1-2z)^2} z^k = [z^{n-k}] \frac{1-2z+z^2}{(1-2z)^2}.$$

We thus have for $k=n$ the value one, corresponding to the composition $n=n$, for $k=n-1$ the value

$$[z^1] \frac{1-2z+z^2}{(1-2z)^2} = 4 - 2 = 2$$

corresponding to the compositions $1 + (n-1) = (n-1) + 1$ and for $k\le n-2$

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

for a closed form of

$$\bbox[5px,border:2px solid #00A000]{ 2^{n-k-2} (n-k+3).}$$

We clearly obtain zero when $k\gt n.$