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,2

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 equality 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 equal to the colors on p, otherwise we say q avoids p in the equality sense.

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

Formula

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

a(n) = sum(sum(binomial(n, i)*binomial(n-i, j)*add(binomial(n-i-j, p)*S(p, j)*j!*B(n-i-j-p), p = j .. n-i-j), j = 0 .. floor((n-i)/2))), i = 0 .. n), 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

Example

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.

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

Prog

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

Crossrefs

Cf. A000110, A000248.

Sequence in context: A030836 A030931 A030896 * A030848 A321735 A030975

Adjacent sequences: A209798 A209799 A209800 * A209802 A209803 A209804

Keyword

nonn

Author

Adam Goyt, Mar 13 2012

Status

approved