cp's OEIS Frontend

A220101 Number of ordered set partitions of {1,...,n} into n-1 blocks avoiding the pattern 123.

%I A220101 #80 Feb 17 2023 10:08:23
%S A220101 0,1,6,27,112,450,1782,7007,27456,107406,419900,1641486,6418656,
%T A220101 25110020,98285670,384942375,1508593920,5915896470,23213240820,
%U A220101 91140287370,358042932000,1407342229020,5534695100220,21777424274502,85729014099072,337635166767500
%N A220101 Number of ordered set partitions of {1,...,n} into n-1 blocks avoiding the pattern 123.
%C A220101 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
%H A220101 Lara Pudwell and Giorgio Balzarotti, <a href="/A220101/b220101.txt">Table of n, a(n) for n = 1..101</a> (first 37 terms from Lara Pudwell, terms generated by Maple code below).
%H A220101 W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, <a href="http://arxiv.org/abs/1304.3187">Ordered Partitions Avoiding a Permutation of Length 3</a>, arXiv:1304.3187 [math.CO], 2013. See Eq. (2.6).
%H A220101 Anant Godbole, Adam Goyt, Jennifer Herdan, and Lara Pudwell, <a href="http://arxiv.org/abs/1212.2530">Pattern Avoidance in Ordered Set Partitions</a>, arXiv:1212.2530 [math.CO], 2012.
%H A220101 Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/123_scheme">Maple code</a> to generate this and other sequences enumerating 123-avoiding ordered set partitions.
%F A220101 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]
%F A220101 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
%F A220101 a(n) = A051666(2*(n-1),n-1) / 2. - _Reinhard Zumkeller_, Aug 05 2013
%F A220101 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
%F A220101 a(n) = 3*2^(-2+2*n)*Gamma(-1/2+n)*(-1+n)^2/(sqrt(Pi)*Gamma(2+n)). - _Peter Luschny_, Dec 14 2015
%F A220101 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
%F A220101 From _Amiram Eldar_, Feb 17 2023: (Start)
%F A220101 Sum_{n>=2} 1/a(n) = Pi^2/27 + 11*Pi/(27*sqrt(3)) + 1/9.
%F A220101 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)
%e A220101 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.
%e A220101 For n=3, the a(3)=6 ordered partitions are 12/3, 13/2, 23/1, 3/12, 2/13, 23/1.
%e A220101 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.
%p A220101 g:=(2*x^2-7*x+2+3*x*sqrt(1-4*x)-2*sqrt(1-4*x))/(2*x*sqrt(1-4*x));
%p A220101 series(g,x,50);
%p A220101 seriestolist(%); # _N. J. A. Sloane_, Apr 13 2014
%p A220101 a := n -> 3*2^(-2+2*n)*GAMMA(n-1/2)*(n-1)^2/(sqrt(Pi)*GAMMA(2+n)):
%p A220101 seq(simplify(a(n)), n=1..26); # _Peter Luschny_, Dec 14 2015
%t A220101 T[n_, 0] := n^2; T[n_, n_] := n^2;
%t A220101 T[n_, k_] := T[n, k] = T[n-1, k-1] + T[n-1, k];
%t A220101 a[n_] := T[2(n-1), n-1]/2;
%t A220101 Array[a, 26] (* _Jean-François Alcover_, Jul 13 2018, after _Reinhard Zumkeller_ *)
%t A220101 Table[3*(n-1)/(2*n-1)*Binomial[2*n-1,n-2], {n,1,30}] (* _G. C. Greubel_, Feb 12 2019 *)
%o A220101 (Haskell)
%o A220101 a220101 n = (a051666 (2 * (n - 1)) (n - 1)) `div` 2
%o A220101 -- _Reinhard Zumkeller_, Aug 05 2013
%o A220101 (PARI) vector(30, n, 3*(n-1)/(2*n-1)*binomial(2*n-1,n-2)) \\ _G. C. Greubel_, Feb 12 2019
%o A220101 (Magma) [3*(n-1)/(2*n-1)*Binomial(2*n-1,n-2): n in [1..30]]; // _G. C. Greubel_, Feb 12 2019
%o A220101 (Sage) [3*(n-1)/(2*n-1)*binomial(2*n-1,n-2) for n in (1..30)] # _G. C. Greubel_, Feb 12 2019
%o A220101 (GAP) List([1..30], n -> 3*(n-1)/(2*n-1)*Binomial(2*n-1,n-2)); # _G. C. Greubel_, Feb 12 2019
%Y A220101 Cf. A220097 (counts 123-avoiding ordered set partitions where all blocks have size 2), A051666, A001622.
%K A220101 nonn,easy
%O A220101 1,3
%A A220101 _Lara Pudwell_, Dec 04 2012