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
Keywords
A209629 The number of partitions of the set [n] where each element can be colored 1 or 2 avoiding the patterns 1^12^2 and 1^22^1 in the pattern sense.
2, 6, 16, 44, 134, 468, 1880, 8534, 42804, 232972, 1359186, 8431288, 55297064, 381815026, 2765949856, 20960349828, 165729870678, 1364153874460, 11665484934400, 103448317519318, 949739634410652, 9013431481088948, 88304011718557298, 891917738606387792
Offset: 1
Keywords
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)=6 solutions are 1^11^1, 1^11^2, 1^21^1, 1^21^2, 1^12^1, 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
Formula
a(n) = 2^n + 2*(B(n)-1), where B(n) is the n-th Bell number.
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
Keywords
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
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
A209798 The number of partitions of the set [n] where each element can be colored 1 or 2 avoiding the patterns 1^11^2, 1^12^2, and 1^22^1 in the pattern sense.
2, 5, 12, 33, 108, 411, 1760, 8287, 42302, 231959, 1357150, 8427205, 55288886, 381798657, 2765917104, 20960284309, 165729739624, 1364153612335, 11665484410132, 103448316470763, 949739632313522, 9013431476894667, 88304011710168714, 891917738589610601
Offset: 1
Keywords
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^1, 1^21^1, 1^21^2, 1^12^1, 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
Formula
2*B(n)+n-1, where B(n) is the n-th Bell number.
A209797 The number of partitions of the set [n] where each element can be colored 1 or 2 avoiding the patterns 1^11^2 and 1^22^1 in the pattern sense.
2, 6, 18, 56, 188, 695, 2838, 12726, 62140, 327760, 1854488, 11189273, 71627546, 484332314, 3446042310, 25712613664, 200599911596, 1632055365951, 13814906940846, 121414108567114, 1105838412755384, 10420517690466168, 101439025287805552, 1018689421191417393
Offset: 1
Keywords
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)=6 solutions are 1^11^1, 1^21^1, 1^21^2, 1^12^1, 1^12^2, 1^22^2.
Formula
For n >=2, 2*B(n)+B(n-1)+sum(sum(B(n-j-k), k = 0 .. n-j), j = 2 .. n)+sum(B(j-1)*(B(n-j)+sum((k+binomial(n-j, k))*B(n-j-k), k = 1 .. n-j)), j = 2 .. n-1)
A113485 Number of partitions of [n] avoiding the pattern 12/34.
1, 2, 5, 14, 41, 122, 367, 1114, 3423, 10670, 33841, 109398, 361045, 1217346, 4195267, 14775986, 53172411, 195396310, 732806677, 2802898190, 10926431393, 43381582538, 175311002903, 720640632074, 3011495745175, 12786738800254
Offset: 1
Keywords
Comments
The first sum in the formula counts those partitions with a single block of size at least 3. The second sum counts those partitions with blocks of size at most 2. It's easy to see that to avoid 12/34 a partition cannot contain more than one block of size at least 3.
The elements shown satisfy the hypergeometric recurrence 2*a(n) -10*a(n-1) +(-n+13)*a(n-2) +2*(2*n+1)*a(n-3) +3*(-n-5)*a(n-4) +4*(-n+6)*a(n-5) +4*(n-5)*a(n-6)=0. - R. J. Mathar, Jan 25 2013
Examples
For n=1,2,3 a(n)=B_n, where B_n is the n-th Bell number, since there aren't enough distinct elements for such a partition to contain a copy of 12/34. By a similar argument a(4)=B_4-1=14.
References
- M. Klazar, Counting Pattern-free Set Partitions I: A Generalization of Stirling Numbers of the Second Kind, Europ. J. Combinatorics, Vol. 21 (2000), pp. 367-378.
Links
- G. C. Greubel, Table of n, a(n) for n = 1..880
Crossrefs
Cf. A084261.
Programs
-
Mathematica
Table[Sum[Sum[(k+1)^2 Binomial[n, 2k+p] k!, {k, 0, Floor[(n-p)/2]}], {p, 3, n}]+Sum[Binomial[n, 2k] k!, {k, 0, Floor[n/2]}], {n, 1, 31}] -
PARI
a(n)=sum(p=3,n, sum(k=0,(n-p)\2, binomial(n,2*k+p)*(k+1)^2*k!)) + sum(k=0,n\2, binomial(n,2*k)) \\ Charles R Greathouse IV, Mar 12 2017
Formula
a(n) = Sum[Sum[(k+1)^2 binomial[n, 2k+p] k!, {k, 0, Floor[(n-p)/2]}], {p, 3, n}] + Sum[binomial[n, 2k] k!, {k, 0, Floor[n/2]}].
From Vaclav Kotesovec, Jun 10 2019: (Start)
Recurrence: 2*(n^2-8*n+13)*a(n) = 2*(4*n^2-31*n+43)*a(n-1) + (n^3-17*n^2+87*n-91)*a(n-2) - (3*n^3-27*n^2+78*n-64)*a(n-3) + 2*(n-3)*(n^2-6*n+6)*a(n-4).
a(n) ~ sqrt(Pi) * exp(sqrt(2*n) - n/2 - 1/2) * n^(n/2 + 1) / 2^(n/2 + 3/2) * (1 + 4*sqrt(2)/(3*sqrt(n))). (End)
Comments
Examples
Links
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