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.

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

Author

Adam Goyt, Mar 12 2012

Keywords

• nonn

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}

Examples

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

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

Programs

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 *)

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.