A227532 -id:A227532 - 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

A145855 Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.

Original entry on oeis.org

1, 1, 4, 9, 26, 76, 246, 809, 2704, 9226, 32066, 112716, 400024, 1432614, 5170604, 18784169, 68635478, 252085792, 930138522, 3446167834, 12815663844, 47820414962, 178987624514, 671825133644, 2528212128776, 9536894664376

Offset: 1

T. D. Noe, Oct 21 2008, Oct 22 2008, Oct 24 2008

nonn

It is easy to see that {1,2,...,2n-1} can be replaced by any 2n-1 consecutive numbers and the results will be the same. Erdos, Ginzburg and Ziv proved that every set of 2n-1 numbers -- not necessarily consecutive -- contains a subset of n elements whose sum is a multiple of n.

			a(3)=4 because, of the 10 3-element subsets of 1..7, only {1,2,3}, {1,3,5}, {2,3,4} and {3,4,5} have sums that are multiples of 3.
L.g.f.: L(x) = x + x^2/2 + 4*x^3/3 + 9*x^4/4 + 26*x^5/5 + 76*x^6/6 + 246*x^7/7 +...
where exponentiation yields the g.f. of A000571:
exp(L(x)) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 22*x^6 + 59*x^7 + 167*x^8 +...

Seiichi Manyama, Table of n, a(n) for n = 1..1669 (terms 1..200 from T. D. Noe)
Max Alekseyev, Proof of Jovovic's formula, 2008.
Michal Bassan, Serte Donderwinkel, and Brett Kolesnik, Tournament score sequences, Erdős-Ginzburg-Ziv numbers, and the Lévy-Khintchine method, arXiv:2407.01441 [math.CO], 2024. See p. 7.
Shane Chern, An extension of a formula of Jovovic, Integers (2019) Vol. 19, Article A47.
Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurður Örn Stefánsson, Counting tournament score sequences, arXiv:2209.03925 [math.CO], 2022.
P. Erdős, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel 10 (1961).
Steven Rayan, Aspects of the topology and combinatorics of Higgs bundle moduli spaces, arXiv:1809.05732 [math.AG], 2018.
Mithat Ünsal, Graded Hilbert spaces, quantum distillation and connecting SQCD to QCD, arXiv:2104.12352 [hep-th], 2021.

Cf. A000571, A227532.

Column k=2 of A309148.

Table[Length[Select[Plus@@@Subsets[Range[2n-1],{n}], Mod[ #,n]==0&]], {n,10}]
Table[d=Divisors[n]; Sum[(-1)^(n+d[[i]]) EulerPhi[n/d[[i]]] Binomial[2d[[i]], d[[i]]]/2/n, {i,Length[d]}], {n,30}] (* T. D. Noe, Oct 24 2008 *)

{a(n)=sumdiv(n, d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/(2*n))}

{A227532(n, k)=local(G=1); for(i=1, n, G=1+x*subst(G, x, q*x)*G +x*O(x^n)); n*polcoeff(polcoeff(log(G), n, x), k, q)}
{a(n)=sum(k=0,n\2, A227532(n, n*k))} \\ Paul D. Hanna, Jul 17 2013

a(n) = (1/(2*n))*Sum_{d|n} (-1)^(n+d)*phi(n/d)*binomial(2*d,d). Conjectured by Vladeta Jovovic, Oct 22 2008; proved by Max Alekseyev, Oct 23 2008 (see link).
a(2n+1) = A003239(2n+1) and a(2n) = A003239(2n) - A003239(d), where d is the largest odd divisor of n. - T. D. Noe, Oct 24 2008
a(n) = Sum_{d|n} (-1)^(n+d)*d*A131868(d). - Vladeta Jovovic, Oct 28 2008
a(n) = Sum_{k=0..[n/2]} A227532(n,n*k), where A227532 is the logarithmic derivative, wrt x, of the g.f. G(x,q) = 1 + x*G(q*x,q)*G(x,q) of triangle A227543. - Paul D. Hanna, Jul 17 2013
Logarithmic derivative of A000571, the number of different scores that are possible in an n-team round-robin tournament. - Paul D. Hanna, Jul 17 2013
G.f.: -Sum_{m >= 1} (phi(m)/m) * log((1 + sqrt(1 + 4*(-y)^m))/2). - Petros Hadjicostas, Jul 15 2019
a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 28 2023

Extension T. D. Noe, Oct 24 2008

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

A145855 Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

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

A145855 Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

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.