OFFSET
0,5
COMMENTS
Original name: Table T(n, m) giving total degree of n-th-order elementary symmetric polynomials in m variables, -1 <= n, 1 <= m, transposed and read by upward antidiagonals.
A(n, k) is the number of n-step walks on the treshhold graph G_k with vertex set {0,1,...,k} and edge relation i ~ j <=> i + j >= k (self-loops included), starting from vertex k. - Peter Luschny, Mar 15 2026
REFERENCES
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
Václav Chvátal and Peter L. Hammer, Aggregation of inequalities in integer programming, Studies in Integer Programming, Annals of Discrete Mathematics 1, pp. 145-162, 1977.
S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 120).
Manfred Goebel, Rewriting Techniques and Degree Bounds for Higher Order Symmetric Polynomials, Applicable Algebra in Engineering, Communication and Computing (AAECC), Volume 9, Issue 6 (1999), 559-573.
LINKS
T. D. Noe, Table of 100 antidiagonals
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
R. P. Stanley, Examples of Magic Labelings, Unpublished Notes, 1973. [Cached copy, with permission] See p. 31.
Wikipedia, Threshold graph.
FORMULA
G.f. for row n >= 0: f(n, x) = (x + f(n-2, x))/(1 - x^2 - x*f(n-2, x)), where f(0, x) = 1 and f(1, x) = 1/(1 - x) [R. P. Stanley]. - L. Edson Jeffery, Oct 19 2017
From Peter Luschny, Mar 15 2026: (Start)
Algorithmic definition: Initialize v = (1,1,...,1) in Z^(k+1). Apply n times: reverse v, then replace by its prefix sums. A(n, k) is the last entry of the resulting vector. This reverse-accumulate iteration can also be casted into a matrix-vector product. See the first and the second Python function.
A(n, k) satisfies a linear recurrence of order k + 1 with characteristic polynomial det(lambda*I - M_k) where M_k denotes the (k+1) X (k+1) binary Hankel matrix with M_k(i, j) = 1 if i + j >= k and otherwise 0. (End)
EXAMPLE
Array begins:
[0] 1 1 1 1 1 1 1 1 1 1
[1] 1 2 3 5 8 13 21 34 55 89
[2] 1 3 6 14 31 70 157 353 793 1782
[3] 1 4 10 30 85 246 707 2037 5864 16886
[4] 1 5 15 55 190 671 2353 8272 29056 102091
[5] 1 6 21 91 371 1547 6405 26585 110254 457379
[6] 1 7 28 140 658 3164 15106 72302 345775 1654092
[7] 1 8 36 204 1086 5916 31998 173502 940005 5094220
[8] 1 9 45 285 1695 10317 62349 377739 2286648 13846117
[9] 1 10 55 385 2530 17017 113641 760804 5089282 34053437
.
Illustrating the reverse-accumulate procedure computing row 3 (see Python code).
ini[ 1, 1, 1, 1] -> 1;
rev[ 1, 1, 1, 1] = [ 1, 1, 1, 1], accu -> [ 1, 2, 3, 4] -> 4;
rev[ 1, 2, 3, 4] = [ 4, 3, 2, 1], accu -> [ 4, 7, 9, 10] -> 10;
rev[ 4, 7, 9,10] = [10, 9, 7, 4], accu -> [10, 19, 26, 30] -> 30;
rev[10,19,26,30] = [30,26,19,10], accu -> [30, 56, 75, 85] -> 85;
rev[30,56,75,85] = [85,75,56,30], accu -> [85,160,216,246] -> 246;
Trow(3, 6) = [1, 4, 10, 30, 85, 246].
MAPLE
A := proc(n, k) option remember; local j;
ifelse(n = 0 or k = 0, 1, ifelse(n < 0 or k < 0, 0, A(n, k - 1 ) +
add(A(2 * j, k - 1) * A(n - 1 - 2 * j, k), j = 0..iquo(n-1, 2)))) end:
for n from 0 to 9 do seq(A(k, n), k = 0..9) od; # Peter Luschny, Mar 15 2026
MATHEMATICA
nmax = 12; t[n_, m_?Positive] := t[n, m] = t[n, m-1] + Sum[t[2k, m-1]*t[n-1-2k, m], {k, 0, (n-1)/2}]; t[n_, 0]=1; Flatten[ Table[ t[k-1, n-k], {n, 1, nmax}, {k, 1, n}]] (* Jean-François Alcover, Nov 14 2011 *)
nmax = 10; f[0, x_] := 1; f[1, x_] := 1/(1 - x); f[n_, x_] := (x + f[n - 2, x])/(1 - x^2 - x*f[n - 2, x]); t[n_, m_] := Coefficient[Series[f[n, x], {x, 0, m}], x, m]; Grid[Table[t[n, m], {n, nmax}, {m, 0, nmax - 1}]] (* L. Edson Jeffery, Oct 19 2017 *)
PROG
(PARI) M(n)=matrix(n, n, i, j, if(sign(i+j-n)-1, 0, 1)); V(n)=vector(n, i, 1); P(r, n)=vecmax(V(r)*M(r)^n) \\ P(r, n) is T(n, k); Benoit Cloitre, Jan 27 2003
(Python)
from itertools import accumulate
def Arow(row: int, rowlen: int) -> list[int]:
acc = [1] * (row + 1)
vec = [1] * rowlen
for k in range(1, rowlen):
acc = list(accumulate(reversed(acc)))
vec[k] = acc[-1]
return vec
for n in range(10): print(Arow(n, 10)) # Peter Luschny, Mar 15 2026
# Alternative: matrix form and numpy based.
import numpy as np
def MatRow(n: int, rowlen: int) -> list[int]:
M = np.array([[1 if i + j >= n else 0
for j in range(n + 1)] for i in range(n + 1)], dtype=object)
ones = np.ones(n + 1, dtype=object)
v = ones.copy()
row = [int(v[n])]
for _ in range(rowlen - 1):
v = M @ v
row.append(int(v[n]))
return row
for n in range(10): print(MatRow(n, 10)) # Peter Luschny, Mar 15 2026
CROSSREFS
KEYWORD
AUTHOR
N. J. A. Sloane, Dec 23 1999
EXTENSIONS
More terms from Naohiro Nomoto, Jul 03 2001
New name using Stanley's formula by Peter Luschny, Mar 15 2026
STATUS
approved