cp's OEIS Frontend

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.

%I A209801 #35 Feb 18 2025 05:56:16
%S A209801 1,2,7,30,152,878,5653,39952,306419,2527984,22277080,208483014,
%T A209801 2062199125,21472152822,234526948183,2678973711602,31919113081724,
%U A209801 395750219427590,5095324584255641,67996852799627404,938939425151949211,13395286474394627364,197162835188949226772
%N 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.
%C A209801 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 A209801 Alois P. Heinz, <a href="/A209801/b209801.txt">Table of n, a(n) for n = 0..535</a>
%H A209801 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 A209801 E.g.f.: exp( (1+x)*exp(x) - 1 ). - _Paul D. Hanna_, Jun 11 2012
%F A209801 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.
%F A209801 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 A209801 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 A209801 a:= proc(n) option remember; `if`(n=0, 1, add(
%p A209801       a(n-j)*binomial(n-1, j-1)*(j+1), j=1..n))
%p A209801     end:
%p A209801 seq(a(n), n=0..23);  # _Alois P. Heinz_, Aug 29 2019
%t A209801 Table[Sum[BellY[n, k, Range[n] + 1], {k, 0, n}], {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 09 2016 *)
%o A209801 (PARI) {a(n)=n!*polcoeff(exp((1+x)*exp(x +x*O(x^n))-1),n)} \\ _Paul D. Hanna_, Jun 11 2012
%Y A209801 Cf. A000110, A000248.
%K A209801 nonn
%O A209801 0,2
%A A209801 _Adam Goyt_, Mar 13 2012