A220101 Number of ordered set partitions of {1,...,n} into n-1 blocks avoiding the pattern 123.
0, 1, 6, 27, 112, 450, 1782, 7007, 27456, 107406, 419900, 1641486, 6418656, 25110020, 98285670, 384942375, 1508593920, 5915896470, 23213240820, 91140287370, 358042932000, 1407342229020, 5534695100220, 21777424274502, 85729014099072, 337635166767500
Offset: 1
Examples
An ordered set partition is a set partition where the order of the blocks is important. A 123 pattern within such a set partition is a list of 3 elements a from block i, b from block j, and c from block k such that i < j < k and a < b < c. For n=3, the a(3)=6 ordered partitions are 12/3, 13/2, 23/1, 3/12, 2/13, 23/1. For n=4, the a(4)=27 ordered partitions are 12/4/3, 3/12/4, 3/4/12, 4/12/3, 4/3/12, 13/4/2, 2/4/13, 4/13/2, 4/2/13, 14/3/2, 2/14/3, 3/2/14, 2/3/14, 23/1/4, 23/4/1, 1/4/23, 4/1/23, 4/23/1, 24/1/3, 24/3/1, 3/1/24, 3/24/1, 34/1/2, 34/2/1, 2/34/1, 2/1/34, 1/34/2.
Links
- Lara Pudwell and Giorgio Balzarotti, Table of n, a(n) for n = 1..101 (first 37 terms from Lara Pudwell, terms generated by Maple code below).
- W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, Ordered Partitions Avoiding a Permutation of Length 3, arXiv:1304.3187 [math.CO], 2013. See Eq. (2.6).
- Anant Godbole, Adam Goyt, Jennifer Herdan, and Lara Pudwell, Pattern Avoidance in Ordered Set Partitions, arXiv:1212.2530 [math.CO], 2012.
- Lara Pudwell, Maple code to generate this and other sequences enumerating 123-avoiding ordered set partitions.
Crossrefs
Programs
-
GAP
List([1..30], n -> 3*(n-1)/(2*n-1)*Binomial(2*n-1,n-2)); # G. C. Greubel, Feb 12 2019
-
Haskell
a220101 n = (a051666 (2 * (n - 1)) (n - 1)) `div` 2 -- Reinhard Zumkeller, Aug 05 2013
-
Magma
[3*(n-1)/(2*n-1)*Binomial(2*n-1,n-2): n in [1..30]]; // G. C. Greubel, Feb 12 2019
-
Maple
g:=(2*x^2-7*x+2+3*x*sqrt(1-4*x)-2*sqrt(1-4*x))/(2*x*sqrt(1-4*x)); series(g,x,50); seriestolist(%); # N. J. A. Sloane, Apr 13 2014 a := n -> 3*2^(-2+2*n)*GAMMA(n-1/2)*(n-1)^2/(sqrt(Pi)*GAMMA(2+n)): seq(simplify(a(n)), n=1..26); # Peter Luschny, Dec 14 2015
-
Mathematica
T[n_, 0] := n^2; T[n_, n_] := n^2; T[n_, k_] := T[n, k] = T[n-1, k-1] + T[n-1, k]; a[n_] := T[2(n-1), n-1]/2; Array[a, 26] (* Jean-François Alcover, Jul 13 2018, after Reinhard Zumkeller *) Table[3*(n-1)/(2*n-1)*Binomial[2*n-1,n-2], {n,1,30}] (* G. C. Greubel, Feb 12 2019 *)
-
PARI
vector(30, n, 3*(n-1)/(2*n-1)*binomial(2*n-1,n-2)) \\ G. C. Greubel, Feb 12 2019
-
Sage
[3*(n-1)/(2*n-1)*binomial(2*n-1,n-2) for n in (1..30)] # G. C. Greubel, Feb 12 2019
Formula
G.f.: (2*x^2-7*x+2+3*x*sqrt(1-4*x)-2*sqrt(1-4*x))/(2*x*sqrt(1-4*x)) [see Chen et al., 2013 - Bruno Berselli, Dec 05 2012]
a(n)/a(n-1) = 2*(2*n-3)*(n-1)^2/((n+1)*(n-2)^2) for n> 2 . - Bruno Berselli, Dec 05 2012
a(n) = A051666(2*(n-1),n-1) / 2. - Reinhard Zumkeller, Aug 05 2013
a(n) = 3*(n-1)/(2*n-1)*binomial(2*n-1,n-2). [See Godbole et al., Theorem 4.] - Peter Bala, Dec 18 2013
a(n) = 3*2^(-2+2*n)*Gamma(-1/2+n)*(-1+n)^2/(sqrt(Pi)*Gamma(2+n)). - Peter Luschny, Dec 14 2015
a(n) ~ (3/4)*4^n*(1 - (21/8)/n + (393/128)/n^2 - (3055/1024)/n^3 + (99099/32768)/n^4) /sqrt(n*Pi). - Peter Luschny, Dec 16 2015
From Amiram Eldar, Feb 17 2023: (Start)
Sum_{n>=2} 1/a(n) = Pi^2/27 + 11*Pi/(27*sqrt(3)) + 1/9.
Sum_{n>=2} (-1)^n/a(n) = 4*log(phi)^2/3 + 34*log(phi)/(15*sqrt(5)) + 1/15, where phi is the golden ratio (A001622). (End)
Comments