login
Reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2).
25

%I #100 Apr 15 2024 13:16:56

%S 1,1,3,10,37,146,602,2563,11181,49720,224540,1027038,4748042,22150519,

%T 104146733,493012682,2347796965,11239697816,54061835288,261130778516,

%U 1266125122956,6160158505040,30065608532008,147161532388934

%N Reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2).

%C From _David Callan_, Mar 30 2007: (Start)

%C a(n) is the number of vertex-labeled ordered trees (A000108) on n vertices, in which each non-leaf vertex is labeled with a positive integer <= its outdegree. Example. a(3)=3 counts the trees on 3 vertices with labels as shown (the 2 edges in each tree are shown, you have to visualize the vertices).

%C .

%C 1 2 1

%C / \ / \ |1

%C |

%C .

%C Proof. Let F(x) = x + x^2 + 3x^3 + ... denote the g.f. for these trees, with x marking number of vertices. Counting these trees by degree of the root leads to F = x + Sum_{k>=1} k*x*F^k, or F = x + x*F/(1-F)^2. This is the same equation as that satisfied by the reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2). (End)

%C (1 + 3x + 10x^2 + ...) = (1 + 2x + 6x^2 + ...)*(1 + x + 2x^2 + 6x^3 + ...), where A106228 = (1, 1, 2, 6, 21, ...). - _Gary W. Adamson_, Nov 15 2011

%C Reversion of x/(1 + sum(k>=1, k*x^k )) (cf. A028310). - _Joerg Arndt_, Aug 19 2012

%C a(n) is the number of Motzkin paths of length 2n-3 with no downsteps in even position (n>=2). Example: a(3)=3 counts FFF, FUD, UFD, where U denotes an upstep (1,1), F a flatstep (1,0), and D a downstep (1,-1). - _David Callan_, May 20 2015

%C a(n) is the number of peakless Motzkin paths of length 2n-2 where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on 2n-2 vertices where only vertices of the same parity can be matched. - _Alexander Burstein_, May 17 2021

%H Robert Israel, <a href="/A109081/b109081.txt">Table of n, a(n) for n = 1..1400</a>

%H Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.

%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.

%H Tian-Xiao He and Louis W. Shapiro, <a href="https://doi.org/10.1016/j.laa.2016.05.035">Row sums and alternating sums of Riordan arrays</a>, Linear Algebra and its Applications, Volume 507, 15 October 2016, Pages 77-95. See R_2^{-}.

%H JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, <a href="https://arxiv.org/abs/2404.04091">Bijections on pattern avoiding inversion sequences and related objects</a>, arXiv:2404.04091 [math.CO], 2024. See p. 22.

%H Markus Kuba and Alois Panholzer, <a href="http://dx.doi.org/10.1016/j.disc.2012.07.011">Enumeration formulas for pattern restricted Stirling permutations</a>, Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012

%H Hanna Mularczyk, <a href="https://arxiv.org/abs/1908.04025">Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations</a>, arXiv:1908.04025 [math.CO], 2019.

%H Jun Yan, <a href="https://arxiv.org/abs/2404.07958">Results on pattern avoidance in parking functions</a>, arXiv:2404.07958 [math.CO], 2024. See p. 11.

%F G.f. A(x) satisfies 0 = f(x, A(x)) where f(x, y) = x*(1 - y + y^2) - y*(1 - y)^2.

%F G.f. A(x) satisfies 0 = f(x, A(x)) where f(x, y) = y*(1 - y)*((1 - y) / x + 1) - 1.

%F From _Paul D. Hanna_, Jun 19 2009: (Start)

%F G.f. satisfies: A(x) = x/(1 - x/(1 - A(x))^2).

%F a(n) = Sum_{k=0..n} C(n,k)/(n-k+1) * C(n+k-1,n-k). (End)

%F From _Gary W. Adamson_, Nov 15 2011: (Start)

%F a(n) is the upper left term in M^(n-1), M = an infinite square matrix as follows:

%F 1, 1, 0, 0, 0, ...

%F 2, 1, 1, 0, 0, ...

%F 3, 2, 1, 1, 0, ...

%F 4, 3, 2, 1, 1, ...

%F 5, 4, 3, 2, 1, ...

%F ... (End)

%F With different signs, g.f. = 2/(3-sqrt(1-4xC(x))) where C = g.f. for A000108 [He-Shapiro]. - _N. J. A. Sloane_, Apr 28 2017

%F From _Vaclav Kotesovec_, Aug 14 2018: (Start)

%F Recurrence: 2*n*(2*n - 1)*(19*n^2 - 85*n + 90)*a(n) = 2*(190*n^4 - 1230*n^3 + 2783*n^2 - 2595*n + 828)*a(n-1) + 2*(n-3)*(38*n^3 - 189*n^2 + 289*n - 132)*a(n-2) + 3*(n-4)*(n-3)*(19*n^2 - 47*n + 24)*a(n-3).

%F a(n) ~ (1 - (1-s)*s)^(n + 1/2) / (2*sqrt(Pi*(3 - 6*s + s^2)) * n^(3/2) * s^n * (1-s)^(2*n-2)), where s = 0.3611030805286473776346465621590281395264149... is the real root of the equation (s^2 - s + 3)*s = 1. (End)

%e a(5) = 37 = the upper left term of M^4: (37, 26, 12, 4, 1); where (37 + 26 + 12 + 4 + 1) = 80 = A106228(5). - _Gary W. Adamson_, Nov 15 2011

%e G.f. = x + x^2 + 3*x^3 + 10*x^4 + 37*x^5 + 146*x^6 + 602*x^7 + 2563*x^8 + ...

%p S:= series(RootOf(-x*z^2+z^3+x*z-2*z^2-x+z, z), x, 101):

%p seq(coeff(S,x,j),j=1..100); # _Robert Israel_, Nov 19 2015

%t a[ n_] := If[ n < 2, Boole[n == 1], (n - 1) HypergeometricPFQ[ {n, 1 - n, 2 - n}, {3/2, 2}, 1/4]]; (* _Michael Somos_, May 28 2014 *)

%t Join[{1}, Table[Sum[ Binomial[n,k] / (n-k+1) Binomial[n+k-1, n-k], {k, n}], {n, 25}]] (* _Vincenzo Librandi_, Sep 23 2015 *)

%o (PARI) {a(n) = if( n<1, 0, polcoeff( serreverse( x * (1 - x) * (1 - x^2) * (1 - x^3) / (1 - x^6) + x * O(x^n)), n))};

%o (PARI) {a(n)=sum(k=0,n,binomial(n,k)/(n-k+1)*binomial(n+k-1,n-k))} \\ _Paul D. Hanna_, Jun 19 2009

%o (Sage)

%o def A109081(n) :

%o return (n-1)*hypergeometric([n,1-n,2-n],[3/2, 2],1/4) if n > 1 else 1

%o [simplify(A109081(n)) for n in (1..24)] # _Peter Luschny_, Aug 02 2012, Nov 13 2014

%o (Magma) [&+[Binomial(n, k)/(n-k+1)*Binomial(n+k-1, n-k): k in [0..n]]: n in [0..25]]; // _Vincenzo Librandi_, Sep 23 2015

%Y Cf. A000108, A028310, A106228, A365770.

%K nonn

%O 1,3

%A _Michael Somos_, Jun 17 2005