OFFSET
0,6
COMMENTS
See related triangle A138158.
Row sums are the Catalan numbers (A000108), set q=1 in the g.f. to see this.
Antidiagonal sums equal A005169, the number of fountains of n coins.
The maximum in each row of the triangle is A274291. - Torsten Muetze, Nov 28 2018
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
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
LINKS
Paul D. Hanna and Seiichi Manyama, Table of n, a(n) for n = 0..9919 (rows n=0..39 of triangle, flattened). (first 1351 terms from Paul D. Hanna)
Peter Bala, The area beneath small Schröder paths: Notes on A224704, A326453 and A326454, Section 4
Luca Ferrari, Unimodality and Dyck paths, arXiv:1207.7295 [math.CO], 2012.
FindStat - Combinatorial Statistic Finder, The bounce statistic of a Dyck path, The diagonal inversion statistic of a Dyck path, The area of a Dyck path.
J. Haglund, Catalan Paths and q,t-Enumeration.
Stéphane Ouvry and Alexios P. Polychronakos, Exclusion statistics for particles with a discrete spectrum, arXiv:2105.14042 [cond-mat.stat-mech], 2021.
Hao Pan, A finite field approach to the Carlitz-Riordan q-Catalan numbers, Journal of Algebraic Combinatorics: An International Journal: Volume 56, Issue 4, Dec 2022, pp 1005-1009.
Thomas Prellberg, Area-perimeter generating functions of lattice walks: q-series and their asymptotics, Slides, School of Mathematical Sciences, Queen Mary, University of London, July 1, 2009.
Eric Weisstein's World of Mathematics, Rogers-Ramanujan Continued Fraction.
FORMULA
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.
G.f. satisfies: A(x,q) = P(x,q)/Q(x,q), where
P(x,q) = Sum_{n>=0} q^(n^2) * (-x)^n / Product_{k=1..n} (1-q^k),
Q(x,q) = Sum_{n>=0} q^(n*(n-1)) * (-x)^n / Product_{k=1..n} (1-q^k),
due to Ramanujan's continued fraction identity.
...
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.
Logarithmic derivative of the g.f. A(x,q), wrt x, yields triangle A227532.
From Peter Bala, Jul 11 2019: (Start)
(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.
1/A(q*x,q) is the generating function for the triangle A047998. (End)
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
EXAMPLE
G.f.: A(x,q) = 1 + x*(1) + x^2*(1 + q) + x^3*(1 + 2*q + q^2 + q^3)
+ x^4*(1 + 3*q + 3*q^2 + 3*q^3 + 2*q^4 + q^5 + q^6)
+ 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)
+ 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) +...
where g.f.:
A(x,q) = Sum_{k=0..n*(n-1)/2, n>=0} T(n,k)*x^n*q^k
satisfies:
A(x,q) = 1 + x*A(q*x,q)*A(x,q).
This triangle of coefficients T(n,k) in A(x,q) begins:
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, 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, 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;
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; ...
MATHEMATICA
T[n_, k_] := Module[{P, Q},
P = Sum[q^(m^2) (-x)^m/Product[1-q^j, {j, 1, m}] + x O[x]^n, {m, 0, n}];
Q = Sum[q^(m(m-1)) (-x)^m/Product[1-q^j, {j, 1, m}] + x O[x]^n, {m, 0, n}];
SeriesCoefficient[P/Q, {x, 0, n}, {q, 0, k}]
];
Table[T[n, k], {n, 0, 10}, {k, 0, n(n-1)/2}] // Flatten (* Jean-François Alcover, Jul 27 2018, from PARI *)
PROG
(PARI) /* From g.f. A(x, q) = 1 + x*A(q*x, q)*A(x, q): */
{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)}
for(n=0, 10, for(k=0, n*(n-1)/2, print1(T(n, k), ", ")); print(""))
(PARI) /* By Ramanujan's continued fraction identity: */
{T(n, k)=local(P=1, Q=1);
P=sum(m=0, n, q^(m^2)*(-x)^m/prod(k=1, m, 1-q^k)+x*O(x^n));
Q=sum(m=0, n, q^(m*(m-1))*(-x)^m/prod(k=1, m, 1-q^k)+x*O(x^n));
polcoeff(polcoeff(P/Q, n, x), k, q)}
for(n=0, 10, for(k=0, n*(n-1)/2, print1(T(n, k), ", ")); print(""))
(PARI)
P(x, n) =
{
if ( n<=1, return(1) );
return( sum( i=0, n-1, P(x, i) * P(x, n-1 -i) * x^((i+1)*(n-1 -i)) ) );
}
for (n=0, 10, print( Vec( P(x, n) ) ) ); \\ Joerg Arndt, Jan 23 2024
(PARI) \\ faster with memoization:
N=11;
VP=vector(N+1); VP[1] =VP[2] = 1; \\ one-based; memoization
P(n) = VP[n+1];
for (n=2, N, VP[n+1] = sum( i=0, n-1, P(i) * P(n-1 -i) * x^((i+1)*(n-1-i)) ) );
for (n=0, N, print( Vec( P(n) ) ) ); \\ Joerg Arndt, Jan 23 2024
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Paul D. Hanna, Jul 15 2013
STATUS
approved