A326454 -id:A326454 - cp's OEIS frontend

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

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

Offset: 0

Paul D. Hanna, Jul 15 2013

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

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

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)
M. Archibald, A. Blecher, S. Elizalde, and A. Knopfmacher, Subdiagonal and superdiagonal partitions, Afr. Mat. 36, 77 (2025). See p. 4.
Peter Bala, Illustration of triangular decomposition of area beneath Dyck paths
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.

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

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

/* 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(""))

/* 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(""))

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

\\ 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

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

A224704 Number of stacks of n triangles, pointing upwards or downwards depending on row parity.

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 13, 24, 45, 84, 156, 291, 543, 1013, 1889, 3524, 6575, 12266, 22883, 42691, 79647, 148593, 277221, 517197, 964911, 1800189, 3358526, 6265846, 11689902, 21809313, 40688632, 75910917, 141623529, 264220545, 492944193, 919663462, 1715774125

Offset: 0

Paul Tek, Apr 16 2013

nonn

A stack is formed by starting with a row of triangles pointing upwards, and then additional triangles pointing downwards can be inserted between adjacent triangles pointing upwards, and additional triangles pointing upwards can be put on top of triangles pointing downwards.
Number of compositions of n with a(1) = 1 and a(i+1) <= a(i) + 1 + mod(a(i),2).
From Peter Bala, Jul 12 2019: (Start)
These triangle stacks may be defined using Schröder paths. A Schröder path is a lattice path in the plane starting and ending on the x-axis, never going below the x-axis, using the steps (1,1) rise, (1,-1) fall or (2,0) flat. A small Schröder path is a Schröder path with no flat steps on the x-axis.
The area between a small Schröder path and the x-axis may be decomposed into a stack of unit area triangles of two types - up triangles with vertices at the lattice points (x, y), (x+1, y+1) and (x+2, y) and down triangles with vertices at the lattice points (x, y), (x-1, y+1) and (x+1, y+1). (End)

Seiichi Manyama, Table of n, a(n) for n = 0..3694 (terms 0..500 from Paul Tek)
P. Bala, The area beneath small Schröder paths: Notes on A224704, A326453 and A326454
Paul Tek, Illustration of the first terms

Column 1 of A316354 (except a(0)).

Cf. A005169, A001524.

a[ n_] := SeriesCoefficient[ 1/(1 + ContinuedFractionK[ - q^(2 k - 1), 1 - q^(2 k), {k, Ceiling @ Sqrt[n]}]), {q, 0, n}]; (* Michael Somos, Jul 14 2019 *)

use bigint;
my $max = 100;
my @d = ( [1] );
foreach my $n (0..$max) {
    my $a = 0;
    foreach my $h (0..$#{$d[$n]}) {
        $a += $d[$n][$h];
        my $maxh = ($h % 2) ? ($h+2) : ($h+1);
        foreach my $newh (1..$maxh) {
            $d[$n+$newh][$newh] += $d[$n][$h];
        }
    }
    print "$a,";
}

From Peter Bala, Jul 03 2019: (Start)
O.g.f. as a continued fraction: A(q) = 1/(1 - q/(1 - q^2 - q^3/(1 - q^4 - q^5/(1 - q^6 - q^7/( ... ) )))). Also,
A(q) = 1/(1 - q/(1 - (q^2 + q^3)/(1 - q^5/(1 - (q^4 + q^7)/(1 - q^9/(1 - (q^6 + q^11)/(1 - q^13/( ... ) ))))))) and
A(q) = 1/(2 - (1 + q)/(2 - (1 + q^3)/(2 - (1 + q^5)/(2 - (1 + q^7)/( ... ) )))).
O.g.f. as a ratio of q-series: A(q) =  N(q)/D(q), where N(q) = Sum_{n >= 0} (-1)^n*q^(2*n^2+n)/( (1-q^2)*(1-q^4)*...*(1-q^(2*n)) )^2 and D(q) = Sum_{n >= 0} (-1)^n*q^(2*n^2-n)/( (1-q^2)*(1-q^4)*...*(1-q^(2*n)) )^2.
D(q) has its least (simple) real zero at x = 0.53600 49695 29708 61653 44946 12214 97438 08884 63471 33627....
a(n) ~ c*x^(-n) where c = 0.30516 69461 42293 61432 58334 29163 22891 57284 39056 20388 ... = - N(x)/(x*D'(x)) and the prime indicates differentiation w.r.t. q. (End)

A326453 Triangle read by rows: T(n,k) is the number of small Schröder paths of semilength k such that the area between the path and the x-axis is equal to n (n >= 0; 0 <= k <= n).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 0, 3, 3, 1, 0, 0, 0, 2, 6, 4, 1, 0, 0, 0, 1, 7, 10, 5, 1, 0, 0, 0, 1, 6, 16, 15, 6, 1, 0, 0, 0, 1, 5, 19, 30, 21, 7, 1, 0, 0, 0, 0, 5, 19, 45, 50, 28, 8, 1, 0, 0, 0, 0, 4, 19, 55, 90, 77, 36, 9, 1, 3, 19, 61, 131, 161, 112, 45, 10, 1

Offset: 0

Peter Bala, Jul 06 2019

A239927 is the companion triangle for Dyck paths.
A Schröder path is a lattice path in the plane starting and ending on the x-axis, never going below the x-axis, using the steps (1,1) rise, (1,-1) fall or (2,0) flat. A small Schröder path is a Schröder path with no flat steps on the x-axis.
The area between a small Schröder path and the x-axis may be decomposed into a stack of unit area triangles; the triangles are of two types: up-triangles with vertices at the lattice points (x, y), (x+1, y+1) and (x+2, y) and down-triangles with vertices at the lattice points (x, y), (x-1, y+1) and (x+1, y+1). A small Schröder path of semilength k has k up-triangles in the bottom row of its stack. See the illustration in the Links section for an example. Thus an alternative description of the triangle entry T(n,k) is the number of n triangle stacks, in the sense of A224704, containing k up-triangles in the bottom row.

			Triangle begins
  n\k|  0    1   2    3    4    5    6    7   8    9
  --------------------------------------------------
   0 |  1
   1 |  0    1
   2 |  0    0   1
   3 |  0    0   1    1
   4 |  0    0   1    2    1
   5 |  0    0   0    3    3    1
   6 |  0    0   0    2    6    4    1
   7 |  0    0   0    1    7   10    5    1
   8 |  0    0   0    1    6   16   15    6   1
   9 |  0    0   0    1    5   19   30   21   7   1
   ...
Example of a stack of 10 up- and down-triangles with 5 up-triangles in the bottom row.
          /\  /\
         /__\/__\     __
        /\  /\  /\  /\  /\
       /__\/__\/__\/__\/__\

P. Bala, Illustration for row 5
P. Bala, The area beneath small Schröder paths: Notes on A224704, A326453 and A326454

Row sums A224704. Cf. A047998, A227543, A239927, A309086, A326454.

O.g.f. as a continued fraction: A(q,u) = 1/(1 + u - (1 + q)*u/(1 + u - (1 + q^3)*u/(1 + u - (1 + q^5)*u/( (...) )))) =  1 + q*u + q^2*u^2 + q^3*(u^2 + u^3) + q^4*(u^2 + 2*u^3 + u^4) + ...(q marks the area, u marks the up- triangles in the bottom row).
Alternative forms: A(q,u) = 1/(1 - q*u/(1 - q^2*u - q^3*u/(1 - q^4*u/( (...) ))));
A(q,u) = 1/(1 - q*u/(1 - (q^2 + q^3)*u/(1 - q^5*u/(1 - (q^4 + q^7)*u/(1 - q^9*u/(1 - (q^6 + q^11)*u/(1 - q^13*u/( (...) )))))))).
O.g.f. as a ratio of q-series: N(q,u)/D(q,u), where N(q,u) = Sum_{n >= 0} (-1)^n*u^n*q^(2*n^2 + n)/( (1 - q^2)*(1 - q^4)*...*(1 - q^(2*n)) * (1 - u*q^2)*(1 - u*q^4)*...*(1 - u*q^(2*n)) ) and D(q,u) = Sum_{n >= 0} (-1)^n*u^n*q^(2*n^2 - n)/( (1 - q^2)*(1 - q^4)*...*(1 - q^(2*n)) * (1 - u*q^2)*(1 - u*q^4)*...*(1 - u*q^(2*n)) ).

A309086 Irregular triangle read by rows: T(n,k) is the number of small Schröder paths of semilength n such that the area between the path and the x-axis contains k down-triangles.

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 4, 2, 1, 6, 12, 12, 8, 4, 2, 1, 8, 24, 38, 40, 32, 24, 16, 8, 4, 2, 1, 10, 40, 88, 128, 140, 130, 112, 88, 64, 44, 28, 16, 8, 4, 2, 1, 12, 60, 170, 3320, 448, 512, 520, 488, 428, 358, 288, 220, 160, 112, 76, 48, 28, 16, 8, 4, 2

Offset: 0

Peter Bala, Jul 16 2019

A Schröder path is a lattice path in the plane starting and ending on the x-axis, never going below the x-axis, using the steps (1,1) rise, (1,-1) fall or (2,0) flat. A small Schröder path is a Schröder path with no flat steps on the x-axis.

The area between a small Schröder path and the x-axis may be decomposed into a stack of unit area triangles; the triangles come in two types: up-triangles with vertices at the lattice points (x, y), (x+1, y+1) and (x+2, y) and down-triangles with vertices at the lattice points (x, y), (x-1, y+1) and (x+1, y+1). These are the triangle stacks of A224704. Here we enumerate triangle stacks with n >= 1 up-triangles in the bottom row of the stack (corresponding to small Schröder paths of semilength n) and containing k >= 0 down-triangles in the stack. See the illustration in the Links section for an example.

			   n\k |  0    1    2    3    4    5    6    7   8   9  10
   - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    0  |  1
    1  |  1
    2  |  1    2
    3  |  1    4    4    2
    4  |  1    6   12   12    8    4    2
    5  |  1    8   24   38   40   32   24   16   8   4   2
   ...

P. Bala, The area beneath small Schröder paths: Notes on A224704, A326453 and A326454
P. Bala, Illustration for row 3

Row sums A001003. Cf. A224704, A227543, A326453, A326454.

O.g.f. as a continued fraction: A(u,d) = 1/(1 - u/(1 - u*d - u*d/(1 - u*d^2 - u*d^2/(1 - u*d^3 -  (...) )))) =  1 + u + (1 + 2*d)*u^2 + (1 + 4*d + 4*d^2 + 2*d^3)*u^3 + ... (u marks the semilength of the path (or, equivalently, up-triangles in the bottom row of the associated triangle stack) and d marks down-triangles in the stack).
Other continued fractions: A(u,d) = 1/(1 + u - 2*u/(1 + u - (1 + d)*u/(1 + u - (1 + d^2)*u/(1 + u - (...) )))).
A(u,d) = 1/(1 - u/(1 - (d + d)*u/(1 - d^2*u/(1 - (d^2 + d^3)*u/(1 - d^4*u/(1 - (d^3 + d^5)*u/(1 - d^6*u/(1 - (d^4 + d^7)*u/(1 - (...) ))))))))).
O.g.f. as a ratio of q-series: N(u,d)/D(u,d), where N(u,d) = Sum_{n >= 0} (-1)^n*u^n*d^(n^2)/( (1 - d)*(1 - d^2)*...*(1 - d^n) * (1 - u*d)*(1 - u*d^2)*...*(1 - u*d^n) ) and D(u,d) =  Sum_{n >= 0} (-1)^n*u^n*d^(n(n-1))/( (1 - d)*(1 - d^2)*...*(1 - d^n) * (1 - u*d)*(1 - u*d^2)*...*(1 - u*d^n) ).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

A224704 Number of stacks of n triangles, pointing upwards or downwards depending on row parity.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Perl

Formula

A326453 Triangle read by rows: T(n,k) is the number of small Schröder paths of semilength k such that the area between the path and the x-axis is equal to n (n >= 0; 0 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A309086 Irregular triangle read by rows: T(n,k) is the number of small Schröder paths of semilength n such that the area between the path and the x-axis contains k down-triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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