A209801 The number of partitions of the set [n] where each element can be colored 1 or 2 avoiding the patterns 1^11^2 in the equality sense.

1, 2, 7, 30, 152, 878, 5653, 39952, 306419, 2527984, 22277080, 208483014, 2062199125, 21472152822, 234526948183, 2678973711602, 31919113081724, 395750219427590, 5095324584255641, 67996852799627404, 938939425151949211, 13395286474394627364, 197162835188949226772

Offset: 0

Author

Adam Goyt, Mar 13 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)=7 solutions are 1^11^1, 1^21^1, 1^21^2, 1^12^1, 1^12^2, 1^22^1, 1^22^2.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..535
• Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012

Crossrefs

Cf. A000110, A000248.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*binomial(n-1, j-1)*(j+1), j=1..n))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Aug 29 2019

Mathematica

Table[Sum[BellY[n, k, Range[n] + 1], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)

PARI

{a(n)=n!*polcoeff(exp((1+x)*exp(x +x*O(x^n))-1),n)} \\ Paul D. Hanna, Jun 11 2012

Formula

E.g.f.: exp( (1+x)*exp(x) - 1 ). - Paul D. Hanna, Jun 11 2012

a(n) = Sum_{i=0..n} Sum_{j=0..floor((n-i)/2)} binomial(n, i)*binomial(n-i, j)*(Sum_{p=j..n-i-j} binomial(n-i-j, p)*S(p, j)*j!*B(n-i-j-p)), where B(n) is the n-th Bell number and S(n,k) is the Stirling number of the second kind.

a(n) = Sum_{j=1..n} (j+1) * binomial(n-1,j-1) * a(n-j) for n>0, a(0)=1. - Alois P. Heinz, Aug 29 2019

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

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