A209629 The number of partitions of the set [n] where each element can be colored 1 or 2 avoiding the patterns 1^12^2 and 1^22^1 in the pattern sense.

2, 6, 16, 44, 134, 468, 1880, 8534, 42804, 232972, 1359186, 8431288, 55297064, 381815026, 2765949856, 20960349828, 165729870678, 1364153874460, 11665484934400, 103448317519318, 949739634410652, 9013431481088948, 88304011718557298, 891917738606387792

Offset

1,1

Comments

A partition of the set [n] is a family nonempty disjoint sets whose union is [n]. The blocks are written in order of increasing minima. A partition of the set [n] can be written as a word p=p_1p_2...p_n where p_i=j if element i is in block j. A partition q=q_1q_2...q_n contains partition p=p_1p_2...p_k if there is a subword q_{i_1}q_{i_2}...q_{i_k} such that q_{i_a}<q_{i_b} whenever p_a<p_b, these words are called order isomorphic. A colored partition q contains the colored partition p in the pattern sense if there is a copy of the uncolored partition p in the uncolored partition q, and the colors on this copy of p are order isomorphic to the colors on p, otherwise we say q avoids p in the pattern sense.

Links

Table of n, a(n) for n=1..24.

Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786, 2012. - From N. J. A. Sloane, Sep 17 2012

Formula

a(n) = 2^n + 2*(B(n)-1), where B(n) is the n-th Bell number.

Example

For n=2 the a(2)=6 solutions are 1^11^1, 1^11^2, 1^21^1, 1^21^2, 1^12^1, 1^22^2.

Crossrefs

Sequence in context: A105696 A074413 A263897 * A349488 A055544 A126285

Adjacent sequences: A209626 A209627 A209628 * A209630 A209631 A209632

Keyword

nonn

Author

Adam Goyt, Mar 13 2012

Status

approved