login
A208275
The number of partitions of the set [n] where each element can be colored 1 or 2 avoiding the patterns 1^11^1 and 1^22^1 in the pattern sense.
1
2, 5, 10, 21, 46, 107, 262, 675, 1818, 5105, 14882, 44929, 140070, 450055, 1487294, 5047327, 17562546, 62578845, 228062522, 849213293, 3227667742, 12511072803, 49417391350, 198758992859, 813460577482, 3385607683977, 14320923895890, 61532392279385
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
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
sum(sum(binomial(i-1, j)*binomial(n-i, j)*j!, j = 0 .. min(i-1, n-i)), i = 1 .. n)+sum(sum((i-1)*binomial(i-2, j)*binomial(n-i, j)*j!, j = 0 .. min(i-2, n-i)), i = 2 .. n)+sum(sum(binomial(i-1, j)*binomial(n-i-1, j)*j!, j = 0 .. min(i-1, n-i-1)), i = 1 .. n-1)+1
EXAMPLE
For n=2 the a(2)=5 solutions are 1^11^2, 1^21^1, 1^12^1, 1^12^2, 1^22^2.
MATHEMATICA
a[n_] := With[{B = Binomial},
Sum[B[i-1, j] B[n-i, j] j!, {i, 1, n}, {j, 0, Min[i-1, n-i]}] +
Sum[B[i-2, j] B[n-i, j] (i-1) j!, {i, 2, n}, {j, 0, Min[i-2, n-i]}] +
Sum[B[i-1, j] B[n-i-1, j] j!, {i, 1, n-1}, {j, 0, Min[i-1, n-i-1]}] + 1
];
Array[a, 28] (* Jean-François Alcover, Oct 08 2018 *)
CROSSREFS
Sequence in context: A018106 A247594 A209469 * A327764 A192317 A361779
KEYWORD
nonn
AUTHOR
Adam Goyt, Mar 12 2012
STATUS
approved