# How many distinct ways can a sequence of $n$ 1s be partitioned into triples and singles?

Following on from this question:

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

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

$\{3,1,1\}$

$\{1,3,1\}$

$\{1,3,1\}$

But no result containing $\{1,1,1\}$ should be enumerated since this should be counted as a triple.

So for $n=5$, the answer is 3 ways.

I think the answer to this question equals the number of Dyck words which give unique results when exponentiating powers of $2$... as asked in this question, since groups of 3 powers of 2 always give the same result; 16 irrespective of order, but the orders of carrying out individual exponents around them make distinct results.

Number of solutions for small $N$: $$\begin{pmatrix}n & N\\1&1\\2&1\\3&1\\4&2\\5&3\\6&3\\7&4\end{pmatrix}$$

Let's see… using Millikan's approach on the other question, a partition of $n$ is one of the following:

• partition of $n-3$ + 3
• partition of $n-4$ + 31
• partition of $n-5$ + 311

Therefore $f(n)=f(n-3)+f(n-4)+f(n-5)$ with $f(1,2,3,4,5)=1,1,1,2,3$. This is OEIS A017818.

• $n=1, N=1$ is probably a better value isn't it? May 10, 2017 at 10:24
• @RobertFrost Yes. And $n=0,N=1$ because it is the empty sum. May 10, 2017 at 10:25
• I think I'm getting a different sequence 1, 1, 1, 2, 3, 3, 4, 6, 8, 10, 13 May 10, 2017 at 10:47
• @RobertFrost That is the OEIS sequence I linked. There's nothing wrong! May 10, 2017 at 10:49
• Oh ok sorry, my bad! We need $n=12$ to discriminate this one: oeis.org/A218947 or does your solution do that already? May 10, 2017 at 10:54