How many ways can a sequence of $1$s be partitioned into pairs or singles?

101 Views Asked by At

How many distinct ways can a sequence of $n$ $1$s be partitioned into pairs or singles, in which $\{1,1\}=\{2\}$ is considered a pair and $\{1\}$ is considered a single?

For example $\{1,1,1,1\}$ can be partitioned into:

$\{2,2\}$

$\{1,2,1\}$

But

$\{2,1,1\}$ and $\{1,1,2\}$ are equivalent to $\{2,2\}$

No result containing $\{1,1,1\}$ should be enumerated since this is a triple and has not been partitioned into pairs or singles.

So for $n=4$, the answer is $2$ ways.

I think the answer to this question describes the the number of Dyck words which give unique results when exponentiating powers of $2$... as discussed in this question. Or it is at least part of the answer in respect of the fact that it factors out the identity $2^4=4^2$.

2

There are 2 best solutions below

2
On BEST ANSWER

I guess what you are trying to ask is:

"In how many way you can express $n\ge 1$ as ordered sum of $1$ and $2$ so that there are no two consecutive ones?"

Solution: Suppose that $n$ is even, i.e., $n=2k$. Then we can place at most $k$ times the number $2$. So, given $i \in \{0,\ldots,k\}$, we miss to place (if possible) $n-2i$ times the number $1$ in the $i+1$ possible positions. Hence the total number is $$ 1+\binom{k}{2}+\binom{k-1}{4}+\cdots=\sum_{j\ge 0}\binom{k+1-j}{2j}. $$

With a similar argument, if $n$ is odd, i.e., $n=2k+1$, we obtain $$ (k+1)+\binom{k}{3}+\binom{k-1}{5}+\cdots=\sum_{j\ge 0}{\binom{k+1-j}{2j+1}}. $$

6
On

A composition of $n$ can either be a composition of $n-2$ followed by a $2$ or a composition of $n-3$ followed by $2,1$. This gives the recurrence $f(n)=f(n-2)+f(n-3)$ with $f(1)=1, f(2)=1, f(3)=2.$ We find it, offset, in OEIS A000931 and it begins $1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739, 10252, 13581, 17991, 23833, 31572, 41824, 55405, 73396, 97229, 128801, 170625$