1
$\begingroup$

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}$$

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .