Number of compositions of N that contain an integer component X What is a closed-form or recursive expression for the number of compositions of an integer $N$ that contain a specific integer $X$? Assume $0<X<=N$. The goal is to count the number of compositions which contain at least one instance of $X$, not the number of instances of $X$ in all compositions of $N$.  
An equivalent way of thinking about this is to consider the number of binary sequences of length $N-1$ that contain a run of length $X-1$.
 A: It will be easier to compute the number of compositions of $n$ that don't contain a specific integer $k$.  Then since there are $2^{n-1}$ compositions of $n$, so subtract.
To do this, we'll use generating functions.  The possible parts of a composition which avoids $k$ have generating function
$$ F(z) = (z + z^2 + z^3 + z^4 + \cdots) - z^k = {z \over 1-z} - z^k = {z - z^k + z^{k+1} \over 1-z}$$
and so the generating function which counts $k$-avoiding compositions is
$$ G(z) = {1 \over 1 - F(z)} = {1 \over 1 - {z - z^k + z^{k+1} \over 1-z}} = {1-z \over 1-2z+z^k - z^{k+1}}. $$
Let $g(n)$ denote the number of $k$-free compositions of $n$. Then from standard results in the theory of generating functions, you have the recurrence
$$ g(n) = 2 g(n-1) - g(n-k) + g(n-k-1) $$
which you can basically read off the denominator of $G(z)$.  The initial conditions are:


*

*$g(\ell) = 2^{\ell-1}$ for $l = 1, 2, \cdots, k-1$ (all compositions of numbers up to $k-1$ are $k$-avoiding)

*$g(k) = 2^{k-1} - 1$ (all compositions of $k$ are $k$-avoiding except for the one consisting of $k$ alone)

*$g(k+1) = 2^k - 2$ (all compositions of $k+1$ are $k$-avoiding except for the two with parts $k$ and $1$ in either order).


In the particular case $k = 1$, note this reduces to $g(n) = g(n-1) + g(n-2)$, which is the recurrence for the Fibonacci numbers.  So the Fibonacci numbers count the $1$-avoiding compositions.
A: Michael Lugo’s recurrence is probably more useful, but we can also get the desired number in the form of a summation. We want the number of compositions of $n$ that contain at least one part $m$; we can get this with an inclusion-exclusion argument.
Fix $p$, and consider compositions of $n$ with $p$ parts. For $k\in[p]$ let $C_k$ be the set of compositions of $n$ whose $k$-th part is $m$. If $\varnothing\ne I\subseteq[p]$, then
$$\left|\,\bigcap_{k\in I}C_k\,\right|=\binom{n-m|I|-1}{p-|I|-1}\;,$$
the number of compositions of $n-m|I|$ into $p-|I|$ parts, provided that neither the upper nor the lower number in the binomial coefficient is negative. For convenience I’ll adopt the non-standard convention that $\binom{n}k=0$ not only if $k<0$, but also if $n<0$.
Thus, the number of compositions of $n$ with $p$ parts, at least one of which is $m$, is
$$\begin{align*}
\left|\,\bigcup_{k\in[p]}C_k\,\right|&=\sum_{\varnothing\ne I\subseteq[p]}(-1)^{|I|+1}\binom{n-m|I|-1}{p-|I|-1}\\
&=\sum_{k=1}^p(-1)^{k+1}\binom{p}k\binom{n-km-1}{p-k-1}\;.
\end{align*}$$
Summing over $p$ then gives the desired number,
$$\sum_p\sum_{k=1}^p(-1)^{k+1}\binom{p}k\binom{n-km-1}{p-k-1}\;.\tag{1}$$
For example, take $n=5$ and $m=2$. There are $9$ compositions of $5$ containing at least one $2$:
$$\begin{align*}
&2+2+1\\
&2+1+2\\
&1+2+2\\
&2+3\\
&3+2\\
&2+1+1+1\\
&1+2+1+1\\
&1+1+2+1\\
&1+1+1+2
\end{align*}$$
And formula $(1)$ yields
$$\begin{align*}
\sum_{p\ge 1}\sum_{k=1}^p\binom{p}k\binom{4-2k}{p-k-1}&=\binom11\binom2{-1}+\left(\binom21\binom20-\binom22\binom0{-1}\right)+\\
&\qquad+\left(\binom31\binom21-\binom32\binom00+\binom33\binom{-2}{-1}\right)+\\
&\qquad+\left(\binom41\binom22-\binom42\binom01+\binom43\binom{-2}0-\binom44\binom{-4}{-1}\right)\\
&=0+(2-0)+(6-3+0)+(4-0+0-0)\\
&=9\;,
\end{align*}$$
as it should.
