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

Comments

Let A(i, j) denote the infinite array such that the i-th row of this array is the sequence obtained by applying the partial sum operator i times to the function n^2 for n > 0. Then A(n, n) equals a(n+1) for all n > 0. - John M. Campbell, Jan 20 2019

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.

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)

Example

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.

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

Prog

(Haskell)
a220101 n = (a051666 (2 * (n - 1)) (n - 1)) `div` 2
-- Reinhard Zumkeller, Aug 05 2013
(PARI) vector(30, n, 3*(n-1)/(2*n-1)*binomial(2*n-1, n-2)) \\ G. C. Greubel, Feb 12 2019
(Magma) [3*(n-1)/(2*n-1)*Binomial(2*n-1, n-2): n in [1..30]]; // 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
(GAP) List([1..30], n -> 3*(n-1)/(2*n-1)*Binomial(2*n-1, n-2)); # G. C. Greubel, Feb 12 2019

Crossrefs

Cf. A220097 (counts 123-avoiding ordered set partitions where all blocks have size 2), A051666, A001622.

Sequence in context: A005284 A371965 A198694 * A014825 A141844 A176476

Adjacent sequences: A220098 A220099 A220100 * A220102 A220103 A220104

Keyword

nonn,easy

Author

Lara Pudwell, Dec 04 2012

Status

approved