1

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

it's a hire car baby
  • 8,731
  • 2
  • 22
  • 55
  • Did you mean to say that $\{ 2,1,1\}$ and $\{1,1,2\}$ are the same as $\{1,2,1\}$? Also, would $\{ 1,1,1,1 \}$ be a third partition for $n = 4$? – Bram28 May 08 '17 at 15:33
  • 3
    I don't understand your equivalence relation. – mercio May 08 '17 at 15:35
  • I think it is safe to assume he meant to write what Bram28 suggested... – Corey May 08 '17 at 15:37
  • 2
    but then everyone is equivalent to $\{1,1,1,1\}$ – mercio May 08 '17 at 15:40
  • @Bram28 no, the opposite; $\{ 2,1,1\}\sim\{ 2,2\}\sim \{ 1,1,2\}$ but $\{ 1,2,1\}$ is distinct from them. – it's a hire car baby May 08 '17 at 16:01
  • @PaoloLeonetti I am defining an equivalence relation. I *think* it is $\{2,1\}\sim\{1,2\}$ – it's a hire car baby May 08 '17 at 16:03
  • 1
    @RobertFrost But then why not $\{1,2,1\} \sim \{1,1,1,1\} \sim \{1,1,2 \}$? – Bram28 May 08 '17 at 16:03
  • @PaoloLeonetti I think the interpretation in your answer is correct. – it's a hire car baby May 08 '17 at 16:04
  • So, for $n=3$ does this mean that $\{1,1,1\}$, $\{2,1\}$ and $\{1,2\}$ are *all* equivalent? Because if so that doesn't seem to be the prevailing interpretation below (I.e. no two consecutive 1s). – N. Shales May 08 '17 at 16:10
  • @N.Shales My intent - which is perhaps not clear in the question - is that $\{1,1,1\}$ has not been partitioned into pairs and singles and is therefore not a valid solution. It's a triple. – it's a hire car baby May 08 '17 at 16:16
  • @RobertFrost Okay I misspoke $\{1,1,1\}$ was just to represent the set to be partitioned but if $\{1,2\}$ is equivalent to $\{2,1\}$ then this isn't the same as an ordered sum of 1s and 2s with no consecutive 1s. If it was then $\{1,2\}$ and $\{2,1\}$ would be counted as distinct. – N. Shales May 08 '17 at 16:31
  • @N.Shales good point – it's a hire car baby May 08 '17 at 16:35
  • @N.Shales then I think the relation is more like $\{2,\{1,1\}\}=\{\{1,1\},\{1,1\}\}$ – it's a hire car baby May 08 '17 at 16:47
  • 1
    @RobertFrost so $\{\{1,1\},1\}$ is different from $\{1,\{1,1\}\}$ then? I'm still confused about the problem statement although I do understand both answers, I just can't quite see that the problem *must* be interpreted this way. Despite this I cannot think of a better interpretation. – N. Shales May 08 '17 at 16:56
  • 1
    @N.Shales: What Robert wants here is certainly not an equivalence relation for the reason both *mercio* and *Bram28* already mentioned above. But one can define a partial order where for any two sequences $x,y$ we have $x – user21820 May 09 '17 at 14:36
  • 1
    @user21820 what may have thrown N.Shales is my statement that this problem is related to the Dyck Words corresponding to unique values of $2^{2^{\ldots}}$ because in that instance $(2^2)^2=2^{(2^2)}$ which, if this problem were equivalent would indeed suggest $\{1,2\}\sim\{2,1\}$; but that's not the case. I saw a relation between the two when I wrote the question yesterday. It's to do with the fact every pair $\{2,1\}$ can then be interchanged without changing the value of the tetration. – it's a hire car baby May 09 '17 at 14:57
  • 1
    @RobertFrost: Whatever it was, I'm just providing a rigorous way to formalize the intuitive notion of pairing; we get a partial order by taking the transitive closure of the ordering given by a reduction by a single pairing operation. So (1,1,2) is **not** equivalent to (2,2) but rather (1,1,2) > (2,2). Similarly (2,1,1) > (2,2). And (1,2,1),(2,2) are incomparable minimal elements. – user21820 May 09 '17 at 15:12
  • @user21820 thank you for formalising the question. This partial order formality, I feel, should be part of the problem statement to avoid any confusion. It certainly avoids the confusion that arises due to the term *equivalent*. – N. Shales May 09 '17 at 16:02

2 Answers2

3

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

Paolo Leonetti
  • 15,021
  • 3
  • 23
  • 57
3

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$

Ross Millikan
  • 369,215
  • 27
  • 252
  • 444
  • Does this agree with Paolo's interpretation of the question? I've clarified that no sequence of three $1$'s is permitted. Sorry if it was vague. – it's a hire car baby May 08 '17 at 16:22
  • 1
    Yes, it agrees. In particular, you can find explicitely the $n$-term of the sequence as a convex combination of the $n$-th powers of the roots of the polynomial $x^3-x-1$. – Paolo Leonetti May 08 '17 at 16:29
  • @PaoloLeonetti we're looking at the Padovan sequence aren't we? – it's a hire car baby May 08 '17 at 16:34
  • 1
    This is using the same interpretation as @Paolo Leonetti. In fact, I found it first by essentially his approach, then computed some terms and looked it up in OEIS. That gave me the recurrence and I recognized how it arose. Yes, this is the Padovan sequence. There are many combinatorial interpretations in the OEIS entry. I didn't see this one. – Ross Millikan May 08 '17 at 16:39
  • @RossMillikan I like both answers... but can only accept 1 :( – it's a hire car baby May 08 '17 at 19:16
  • No worries. I think the two answers complement each other. I have plenty of points not to be concerned. – Ross Millikan May 08 '17 at 19:34