|
%I #32 Aug 29 2019 17:59:50
%S 1,2,7,30,152,878,5653,39952,306419,2527984,22277080,208483014,
%T 2062199125,21472152822,234526948183,2678973711602,31919113081724,
%U 395750219427590,5095324584255641,67996852799627404,938939425151949211,13395286474394627364,197162835188949226772
%N 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.
%C 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.
%H Alois P. Heinz, <a href="/A209801/b209801.txt">Table of n, a(n) for n = 0..535</a>
%H Adam M. Goyt and Lara K. Pudwell, <a href="http://arxiv.org/abs/1203.3786">Avoiding colored partitions of two elements in the pattern sense</a>, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012
%F E.g.f.: exp( (1+x)*exp(x) - 1 ). - _Paul D. Hanna_, Jun 11 2012
%F 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.
%F 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
%e 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.
%p a:= proc(n) option remember; `if`(n=0, 1, add(
%p a(n-j)*binomial(n-1, j-1)*(j+1), j=1..n))
%p end:
%p seq(a(n), n=0..23); # _Alois P. Heinz_, Aug 29 2019
%t Table[Sum[BellY[n, k, Range[n] + 1], {k, 0, n}], {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 09 2016 *)
%o (PARI) {a(n)=n!*polcoeff(exp((1+x)*exp(x +x*O(x^n))-1),n)} \\ _Paul D. Hanna_, Jun 11 2012
%Y Cf. A000110, A000248.
%K nonn
%O 0,2
%A _Adam Goyt_, Mar 13 2012
|
