How many compositions of n are there where all parts of the composition are odd?
I know how to solve for the number of composition when all are even. However, I'm getting stuck with finding all the odd ones.
Any help would be appreciated
[Math] Compositions with all odd parts
combinatorics
Related Solutions
How about finding the number of compositions of $\frac n2$ and then doubling all the parts? Since there are $2^{\frac n2-1}$ of them, that is the number of compositions of $n$ into even parts.
Method 1 (counting).
The number of compositions of $n$ is $2^{n-1}$, via standard stars and bars: a composition corresponds to lining up $n$ stars in a row, and inserting bars in any subset of the $n-1$ gaps.
Similarly, the number of compositions of $n$ into $k$ parts is $\binom{n-1}{k-1}$: choose $k-1$ of the $n-1$ gaps to insert bars in.
The compositions we care about for this question are those that either
have all parts even: $n = 2a_1 + 2a_2 + \dots + 2a_k$, which corresponds via the observation that $n/2 = a_1 + a_2 + \dots + a_k$ to an arbitrary composition of $n/2$ into $k$ parts, whose number is $2^{n/2 - 1}$ (if $n$ is even, and $0$ otherwise).
have exactly one part equal to $1$, and the other parts even: this can be either the first part ($n = 1 + 2a_1 + 2a_2 + \dots + 2a_{k-1}$) or the second part ($n = 2a_1 + 1 + 2a_2 + \dots + 2a_{k-1}$)... or any part up to the $k$th part ($n = 2a_1 + 2a_2 + \dots + 2a_{k-1} + 1$). Note that all these compositions are distinct. In each case, any such composition corresponds via the observation that $\frac{n - 1}{2} = a_1 + a_2 + \dots + a_{k-1}$ to an arbitrary partition of $\frac{n-1}{2}$ into $k-1$ parts, whose number is $\binom{(n-1)/2-1}{k-1}$ (if $n$ is odd, and $0$ otherwise).
So the answer is
$$\binom{n/2 - 1}{k-1}[n\text{ is even}] + k\binom{(n-1)/2 - 1}{k-1}[n\text{ is odd}].$$
Method 2 (generating functions).
Let $\mathcal{E}$ denote the class of all positive even numbers. We have a specification and consequent generating function for $\mathcal{E}$ as $$\mathcal{E} = \operatorname{S\scriptsize EQ}_{\ge 1}(\mathcal{Z}\times\mathcal{Z})$$ $$E(z) = \frac{z^2}{1-z^2}$$ (Check that $E(z) = z^2 + z^4 + z^6 + \dots$ as expected.)
Let $\mathcal{C}$ denote the class of compositions of the kind we want. A specification for $\mathcal{C}$ is, considering the compositions with all parts even, and then with first part $1$, second part $1$, and so on: $$ \mathcal{C} = (\mathcal{E}\times\cdots\times\mathcal{E}) + (\mathcal{Z}\times\mathcal{E}\times\cdots\times\mathcal{E}) + (\mathcal{E}\times\mathcal{Z}\times\cdots\times\mathcal{E}) + \dots + (\mathcal{E}\times\cdots\times\mathcal{E}\times\mathcal{Z}) $$ which in simpler notation is $$\mathcal{C} = (\mathcal{E}^k) + k(\mathcal{Z}\times\mathcal{E}^{k-1})$$ giving the generating function $$C(z) = E(z)^k + kzE(z)^{k-1}$$ which with our previously found generating function $E(z)$ is $$C(z) = \left(\frac{z^2}{1-z^2}\right)^k + kz\left(\frac{z^2}{1-z^2}\right)^{k-1}.$$
Note: it is possible to derive the coefficients from the generating function, or the generating function from the coefficients, but depending on what you're after (closed forms or asymptotics), it may not be worth going that route.
For example, from $C(z)$ we can get $C_n = [z^n]C(z)$ by calculating coefficients. $$[z^n]\left(\frac{z^2}{1-z^2}\right)^k = [z^{n-2k}](1-z^2)^{-k} = [z^{n/2-k}](1-z)^{-k}[n\text{ is even}] = (-1)^{n/2-k}\binom{-k}{n/2-k}[n\text{ is even}] = \binom{n/2-1}{n/2-k}[n\text{ is even}] = \binom{n/2-1}{k-1}[n\text{ is even}]$$ (would be a bit faster if you know beforehand that $[z^n]\left(\frac{z}{1-z}\right)^r = \binom{n-1}{r-1}$) and similarly $$[z^n]\left(kz(\frac{z^2}{1-z^2})^{k-1}\right)=k[z^{(n-1)/2}](\frac{z}{1-z})^{k-1}[n\text{ is odd}] = k\binom{(n-1)/2 - 1}{k-1}[n\text{ is odd}].$$
Best Answer
The following lemma should help you out (or at least partially) for small cases of $n$:
The number of compositions of n into odd parts equals the number of compositions of n + 1 into parts greater than one.
proof: We'll construct a bijection. We'll start with a composition of $n$ of length $l$, $n=a_1+a_2+\dots+a_l$. We will represent this composition with a binary sequences of $n-l-1$ 0's and $l-1$ 1's, as follows:
$a_1-1$ zeros, $1$, $a_2-1$ zeros, $1$, $\dots$ $a_l-1$ zeros
(Thus, for example, the associated binary sequence to $13=3+1+5+3+1$ is $001100001001$)
Notice that a composition of $n$ where each $a_i$ is odd, then the associated binary sequence must have strings of zeros of even length. And thus if we take the conjugate composition (Which is, turn every zero in the corresponding binary sequence of the composition into a 1 and vice versa), we obtain a composition of $n$ of lenth $n-l+1$ with strings of $1$'s of even length. Denote this conjugate composition by $n-l+1=c_1+c_2+\dots+c_{n+l-1}$
(in our example, we have the conjugate composition $13=1+1+3+1+1+1+2+1+2$)
Next, we define $b_i=c_{2i-1}+c_{2i}$ for all $1\leq i \leq (n-l)/2$ and $b_{\frac{n-l}{2}+1}=c_{n-l+1}+1$ (notice how $n$ and $l$ must have the same parity)
Then $n+1=b_1+b_2+\dots +b_{\frac{n-l}{2}}+b_{\frac{n-l}{2}+1}$ is a composition of $n+1$ and length $\frac{n-l}{2}+1$, and moreover, all $b_i>1$!
(In our example: $14=2+4+2+3+3$)
To conclude the bijective relation, we have to check if all steps are reversible, but this is easy: Begin with a composition of n + 1 into parts greater than one, reduce the last part by 1, split each part $j$ (other than the last part) into the pair of parts $j − 1, 1$, and calculute the conjugate composition of the precedent composition. $\Box$
in the following article, Cayley showed that the number of compositions of n + 1 into parts greater than one equals the $n$th Fibonacci number $F_n$.
A. Cayley, Theorems in trigonometry and on partitions, Collected Mathematical Papers, vol. 10, 16.
Quite surprisingly, it follows that the number of compositions into odd parts equals the $n$'th fibonnaci number.
Which is suggested in this OEIS entry: http://oeis.org/A000045: "$F(n) =$ number of compositions of n into odd parts; e.g., $F_6$ counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1. - Clark Kimberling, Jun 22 2004"