A227543 - OEIS

%I #89 Sep 27 2024 23:17:44

%S 1,1,1,1,1,2,1,1,1,3,3,3,2,1,1,1,4,6,7,7,5,5,3,2,1,1,1,5,10,14,17,16,

%T 16,14,11,9,7,5,3,2,1,1,1,6,15,25,35,40,43,44,40,37,32,28,22,18,13,11,

%U 7,5,3,2,1,1,1,7,21,41,65,86,102,115,118,118,113,106,96,85,73,63,53,42,34,26,20,15,11,7,5,3,2,1,1

%N Triangle defined by g.f. A(x,q) such that: A(x,q) = 1 + x*A(q*x,q)*A(x,q), as read by terms k=0..n*(n-1)/2 in rows n>=0.

%C See related triangle A138158.

%C Row sums are the Catalan numbers (A000108), set q=1 in the g.f. to see this.

%C Antidiagonal sums equal A005169, the number of fountains of n coins.

%C The maximum in each row of the triangle is A274291. - _Torsten Muetze_, Nov 28 2018

%C The area between a Dyck path and the x-axis may be decomposed into unit area triangles of two types - up-triangles with vertices at the integer lattice points (x, y), (x+1, y+1) and (x+2, y) and down-triangles with vertices at the integer lattice points (x, y), (x-1, y+1) and (x+1, y+1). The table entry T(n,k) equals the number of Dyck paths of semilength n containing k down triangles. See the illustration in the Links section. Cf. A239927. - _Peter Bala_, Jul 11 2019

%C The row polynomials of this table are a q-analog of the Catalan numbers due to Carlitz and Riordan. For MacMahon's q-analog of the Catalan numbers see A129175. - _Peter Bala_, Feb 28 2023

%H Paul D. Hanna and Seiichi Manyama, <a href="/A227543/b227543.txt">Table of n, a(n) for n = 0..9919 (rows n=0..39 of triangle, flattened).</a> (first 1351 terms from Paul D. Hanna)

%H Peter Bala, <a href="/A227543/a227543.pdf">Illustration of triangular decomposition of area beneath Dyck paths</a>

%H Peter Bala, <a href="/A224704/a224704.pdf">The area beneath small Schröder paths: Notes on A224704, A326453 and A326454</a>, Section 4

%H Luca Ferrari, <a href="http://arxiv.org/abs/1207.7295">Unimodality and Dyck paths</a>, arXiv:1207.7295 [math.CO], 2012.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000005">The bounce statistic of a Dyck path</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000006">The diagonal inversion statistic of a Dyck path</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000012">The area of a Dyck path</a>.

%H J. Haglund, <a href="https://www2.math.upenn.edu/~jhaglund/books/qtcat.pdf">Catalan Paths and q,t-Enumeration</a>.

%H Stéphane Ouvry and Alexios P. Polychronakos, <a href="https://arxiv.org/abs/2105.14042">Exclusion statistics for particles with a discrete spectrum</a>, arXiv:2105.14042 [cond-mat.stat-mech], 2021.

%H Hao Pan, <a href="https://doi.org/10.1007/s10801-022-01141-2">A finite field approach to the Carlitz-Riordan q-Catalan numbers</a>, Journal of Algebraic Combinatorics: An International Journal: Volume 56, Issue 4, Dec 2022, pp 1005-1009.

%H Thomas Prellberg, <a href="http://www.maths.qmul.ac.uk/~tp/talks/asymptotics.pdf"> Area-perimeter generating functions of lattice walks: q-series and their asymptotics</a>, Slides, School of Mathematical Sciences, Queen Mary, University of London, July 1, 2009.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rogers-RamanujanContinuedFraction.html">Rogers-Ramanujan Continued Fraction</a>.

%F G.f.: A(x,q) = 1/(1 - x/(1 - q*x/(1 - q^2*x/(1 - q^3*x/(1 - q^4*x/(1 -...)))))), a continued fraction.

%F G.f. satisfies: A(x,q) = P(x,q)/Q(x,q), where

%F   P(x,q) = Sum_{n>=0} q^(n^2) * (-x)^n / Product_{k=1..n} (1-q^k),

%F   Q(x,q) = Sum_{n>=0} q^(n*(n-1)) * (-x)^n / Product_{k=1..n} (1-q^k),

%F due to Ramanujan's continued fraction identity.

%F ...

%F Sum_{k=0..n*(n-1)/2} T(n,k)*k = 2^(2*n-1) - C(2*n+1,n) + C(2*n-1,n-1) = A006419(n-1) for n>=1.

%F Logarithmic derivative of the g.f. A(x,q), wrt x, yields triangle A227532.

%F From _Peter Bala_, Jul 11 2019: (Start)

%F (n+1)th row polynomial R(n+1,q) = Sum_{k = 0..n} q^k*R(k,x)*R(n-k,q), with R(0,q) = 1.

%F 1/A(q*x,q) is the generating function for the triangle A047998. (End)

%F Conjecture: b(n) = P(n, n) where b(n) is an integer sequence with g.f. B(x) = 1/(1 - f(0)*x/(1 - f(1)*x/(1 - f(2)*x/(1 - f(3)*x/(1 - f(4)*x/(1 -...)))))), P(n, k) = P(n-1, k) + f(n-k)*P(n, k-1) for 0 < k <= n with P(n, k) = 0 for k > n, P(n, 0) = 1 for n >= 0 and where f(n) is an arbitrary function. In fact for this sequence we have f(n) = q^n. - _Mikhail Kurkov_, Sep 26 2024

%e G.f.: A(x,q) = 1 + x*(1) + x^2*(1 + q) + x^3*(1 + 2*q + q^2 + q^3)

%e + x^4*(1 + 3*q + 3*q^2 + 3*q^3 + 2*q^4 + q^5 + q^6)

%e + x^5*(1 + 4*q + 6*q^2 + 7*q^3 + 7*q^4 + 5*q^5 + 5*q^6 + 3*q^7 + 2*q^8 + q^9 + q^10)

%e + x^6*(1 + 5*q + 10*q^2 + 14*q^3 + 17*q^4 + 16*q^5 + 16*q^6 + 14*q^7 + 11*q^8 + 9*q^9 + 7*q^10 + 5*q^11 + 3*q^12 + 2*q^13 + q^14 + q^15) +...

%e where g.f.:

%e A(x,q) = Sum_{k=0..n*(n-1)/2, n>=0} T(n,k)*x^n*q^k

%e satisfies:

%e A(x,q) = 1 + x*A(q*x,q)*A(x,q).

%e This triangle of coefficients T(n,k) in A(x,q) begins:

%e 1;

%e 1;

%e 1, 1;

%e 1, 2, 1, 1;

%e 1, 3, 3, 3, 2, 1, 1;

%e 1, 4, 6, 7, 7, 5, 5, 3, 2, 1, 1;

%e 1, 5, 10, 14, 17, 16, 16, 14, 11, 9, 7, 5, 3, 2, 1, 1;

%e 1, 6, 15, 25, 35, 40, 43, 44, 40, 37, 32, 28, 22, 18, 13, 11, 7, 5, 3, 2, 1, 1;

%e 1, 7, 21, 41, 65, 86, 102, 115, 118, 118, 113, 106, 96, 85, 73, 63, 53, 42, 34, 26, 20, 15, 11, 7, 5, 3, 2, 1, 1;

%e 1, 8, 28, 63, 112, 167, 219, 268, 303, 326, 338, 338, 331, 314, 293, 268, 245, 215, 190, 162, 139, 116, 97, 77, 63, 48, 38, 28, 22, 15, 11, 7, 5, 3, 2, 1, 1; ...

%t T[n_, k_] := Module[{P, Q},

%t P = Sum[q^(m^2) (-x)^m/Product[1-q^j, {j, 1, m}] + x O[x]^n, {m, 0, n}];

%t Q = Sum[q^(m(m-1)) (-x)^m/Product[1-q^j, {j, 1, m}] + x O[x]^n, {m, 0, n}];

%t SeriesCoefficient[P/Q, {x, 0, n}, {q, 0, k}]

%t ];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n(n-1)/2}] // Flatten (* _Jean-François Alcover_, Jul 27 2018, from PARI *)

%o (PARI) /* From g.f. A(x,q) = 1 + x*A(q*x,q)*A(x,q): */

%o {T(n, k)=local(A=1); for(i=1, n, A=1+x*subst(A, x, q*x)*A +x*O(x^n)); polcoeff(polcoeff(A, n, x), k, q)}

%o for(n=0, 10, for(k=0, n*(n-1)/2, print1(T(n, k), ", ")); print(""))

%o (PARI) /* By Ramanujan's continued fraction identity: */

%o {T(n,k)=local(P=1,Q=1);

%o P=sum(m=0,n,q^(m^2)*(-x)^m/prod(k=1,m,1-q^k)+x*O(x^n));

%o Q=sum(m=0,n,q^(m*(m-1))*(-x)^m/prod(k=1,m,1-q^k)+x*O(x^n));

%o polcoeff(polcoeff(P/Q,n,x),k,q)}

%o for(n=0, 10, for(k=0, n*(n-1)/2, print1(T(n, k), ", ")); print(""))

%o (PARI)

%o P(x, n) =

%o {

%o     if ( n<=1, return(1) );

%o     return( sum( i=0, n-1, P(x, i) * P(x, n-1 -i) * x^((i+1)*(n-1 -i)) ) );

%o }

%o for (n=0, 10, print( Vec( P(x, n) ) ) ); \\ _Joerg Arndt_, Jan 23 2024

%o (PARI) \\ faster with memoization:

%o N=11;

%o VP=vector(N+1);  VP[1] =VP[2] = 1;  \\ one-based; memoization

%o P(n) = VP[n+1];

%o for (n=2, N, VP[n+1] = sum( i=0, n-1, P(i) * P(n-1 -i) * x^((i+1)*(n-1-i)) ) );

%o for (n=0, N, print( Vec( P(n) ) ) ); \\ _Joerg Arndt_, Jan 23 2024

%Y Cf. A129175, A138158, A227532, A005169, A000108, A274291, A047998, A224704, A239927.

%K nonn,tabf

%O 0,6

%A _Paul D. Hanna_, Jul 15 2013