login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A220101 Number of ordered set partitions of {1,...,n} into n-1 blocks avoiding the pattern 123. 6
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

a(n) = A051666(2*(n-1),n-1) / 2. - Reinhard Zumkeller, Aug 05 2013

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

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

Sequence in context: A108958 A005284 A198694 * A014825 A141844 A176476

Adjacent sequences:  A220098 A220099 A220100 * A220102 A220103 A220104

KEYWORD

nonn,easy

AUTHOR

Lara Pudwell, Dec 04 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:19 EDT 2020. Contains 333104 sequences. (Running on oeis4.)