How many times does $k$ occur in the composition of $n$?

Question

How many times does the number $k$ occur in the composition of $n$?

Composition of Integer

In short, the difference between the partition of an integer and composition is the order of numbers. In partition, the order doesn't matter whereas, in composition, it does. That's why Partitions are sometimes called as ordered Compositions.

Example: $k$ = $1$ & $n$ = $5$

The composition of 5 are:

$5$

$4 + 1$

$3 + 2$

$3 + 1 + 1$

$2 + 3$

$2 + 2 + 1$

$2 + 1 + 2$

$2 + 1 + 1 + 1$

$1 + 4$

$1 + 3 + 1$

$1 + 2 + 2$

$1 + 2 + 1 + 1$

$1 + 1 + 3$

$1 + 1 + 2 + 1$

$1 + 1 + 1 + 2$

$1 + 1 + 1 + 1 + 1$

In all $1$ occurs $28$ times in the composition of $5$

Similarly is there any relation between $k$ and $n$ for all $n \geq 0$ & $k \leq n$

Answer 1

It's recursively defined. Think about it, if k happens in the composition of n then it was tagged on to a composition of n-k. This implies, that there are at least as many k's in compositions of n, as there are compositions of n-k). so you can sum the number of such compositions of earlier positive numbers in the arithmetic progression $kx+(n \bmod k)$. So, for you k=1, n=5 example we have:

compositions of 1:

$$\color{red}1$$

for 2 we have : $$\color{red} 1,\color {green}1\\ \color{green}2 $$ for 3 we have: $$\color{green}{1,1},\color{blue}1\\ \color{green}2,\color{blue}1\\ \color{blue}3$$

for 4 we have: $$\color{blue}{1,1,1},\color{purple}1\\ \color{blue}{2,1},\color{purple}1\\ \color{blue}{3},\color{purple}1\\\color{purple}{2,2}\\\color{purple}4$$

and for 5 we have:

$$\color{purple}{1,1,1,1},\color{lime}1\\ \color{purple}{2,1,1},\color{lime}1\\ \color{purple}{3,1},\color{lime}1\\\color{purple}{2,2},\color{lime}1\\\color{purple}4,\color{lime}1\\\color{lime}5$$

So, let $f(n,k)$ be the the number of such compositions for the value of n, and let g(v) be the number of compositions of v total:

$$f(n,k)=\sum_{i\gt0,i\equiv n\bmod k}^n g(v) +f(n\bmod k,k)$$

Answer 2

First, for $k=1$. Let $a(n)$ be the number of times $1$ appears in the compositions of $n+1$ (as per the OEIS indexing). Then a composition of $n+1$ either ends in $1,2,3,\dots$. The compositions ending in $1$ contribute $a(n-1)+2^{n-1}$ (since there are $2^{n-1}$ total compositions of $n$). The compositions ending in $j$, $j\geq 2$, contribute $a(n-j)$; thus we get the recurrence $$ a(n)=2^{n-1}+\sum_{j=0}^{n-1}a(j), $$ with $a(0)=1$. A straightforward induction proof (just manipulate a few sums) shows $a(n)=(n+3)2^{n-2}$ for $n\geq1$.

For a general $k$, the recursion is essentially the same, but with different initial conditions. Let $a_k(n)$ be the number of times $k$ appears in the compositions of $n+1$. Then clearly $a_j=0$ for $j<k-1$ and $a_{k-1}=1$. Now as before condition a composition based on its last letter. We get $$ a_k(n)=2^{n-k-1}+\sum_{j=0}^{n-1}a_k(j)=2^{n-k-1}+\sum_{j=k-1}^{n-1}a_k(j) $$ I will leave the details but from inspection you can see from a change of variables and induction that $$a_k(n)=a_1(n-k+1)=(n-k+4)2^{n-k-1}$$

Answer 3

The generating function here is

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

We then have that

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

Extracting coefficients we find for $n\ge k+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} \\ = 2^{n-k} (n-k+1) - 2^{n-k} (n-k) + 2^{n-k-2} (n-k-1) \\ = 2^{n-k} + 2^{n-k-2} (n-k-1) = 2^{n-k-2} (n-k+3).$$

We get for $n=k+1$

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

which corresponds to $(1,k)$ and $(k,1)$ and for $n=k$

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

These only depend on $n-k$ as pointed out in the comments.

Answer 4

Suppose that $k$ (such that $0<k<n$) occurs at "position $p$" in a composition of $n$: $$\ldots+k+\ldots$$ by which I mean that everything to its left is a composition of $p$, and everything to its right is a composition of $n-p-k$.

If $p>0$ and $n-p-k>0$, there are $2^{p-1}$ compositions of $p$ and $2^{n-p-k-1}$ compositions of $n-p-k$, thus there are $2^{p-1}\cdot2^{n-p-k-1}=2^{n-k-2}$ possibilities for the rest of the composition of $n$. If $p=0$ or $n-p-k=0$, there are $2^{n-k-1}$ possibilities for the rest of the composition of $n$.

Summing over $p$, you will find that for $k<n$ the answer is: $$2\cdot2^{n-k-1}+\sum_{p=1}^{n-k-1}2^{n-k-2}=(n-k+3)\cdot2^{n-k-2}$$