A050446 Table read by ascending antidiagonals: T(n, m) giving total degree of n-th-order elementary symmetric polynomials in m variables.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 5, 6, 4, 1, 1, 8, 14, 10, 5, 1, 1, 13, 31, 30, 15, 6, 1, 1, 21, 70, 85, 55, 21, 7, 1, 1, 34, 157, 246, 190, 91, 28, 8, 1, 1, 55, 353, 707, 671, 371, 140, 36, 9, 1, 1, 89, 793, 2037, 2353, 1547, 658, 204, 45, 10, 1, 1, 144, 1782, 5864, 8272, 6405, 3164, 1086, 285, 55, 11, 1

Offset: 0

Author

N. J. A. Sloane, Dec 23 1999

Keywords

• nonn
• easy
• nice
• tabl

Comments

T(n, m) is a polynomial of degree n in m. For example, T(2, m) = (m + 1)(m + 2)/2. For the polynomials corresponding to n = 1, 2, ..., 10, see the Cyvin-Gutman reference (p. 143). Kekulé numbers for certain benzenoids. - Emeric Deutsch, Jun 12 2005

Let LOOP X C_k, k >= 1, be the graph constructed by attaching a loop to each vertex of the cycle graph C_k. Let G_n, n >= 0, be the graph obtained by deleting one edge from LOOP X C_{n+1} while retaining the n + 1 loops; e.g., for n = 4, see the graph G_4 at the top of the page in the Stanley link below. Then T(n, m) equals the number of magic labelings of G_n having magic sum m. (See the second Mathematica program below which requires the "Omega" package authored by Axel Riese and which can be downloaded from the link provided in the article by Andrews et al.) - L. Edson Jeffery, Oct 19 2017

For n != 1, T(n, m) is the number of up-down words of length n over an alphabet of size m. - Sela Fried, Apr 08 2025

Conjecture: T(n,m) is the number of words of length n over the alphabet [m] such that any pair of adjacent letters sum to at most m + 1. - John Tyler Rascoe, Jun 06 2025

Examples

			Array begins:
  [0]  1  1    1     1      1      1       1       1        1        1
  [1]  1  2    3     4      5      6       7       8        9       10
  [2]  1  3    6    10     15     21      28      36       45       55
  [3]  1  5   14    30     55     91     140     204      285      385
  [4]  1  8   31    85    190    371     658    1086     1695     2530
  [5]  1 13   70   246    671   1547    3164    5916    10317    17017
  [6]  1 21  157   707   2353   6405   15106   31998    62349   113641
  [7]  1 34  353  2037   8272  26585   72302  173502   377739   760804
  [8]  1 55  793  5864  29056 110254  345775  940005  2286648  5089282
  [9]  1 89 1782 16886 102091 457379 1654092 5094220 13846117 34053437
  ...
Triangle starts:
  [0] 1;
  [1] 1,  1;
  [2] 1,  2,  1;
  [3] 1,  3,  3,  1;
  [4] 1,  5,  6,  4,  1;
  [5] 1,  8, 14, 10,  5, 1;
  [6] 1, 13, 31, 30, 15, 6, 1;
		

References

• J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
• S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (pp. 142-144).

Links

• G. E. Andrews, P. Paule and A. Riese, MacMahon's partition analysis III. The Omega package.
• J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
• Byeong-Gil Choe and Hyeong-Kwan Ju, A Recurrence Relation Associated with Unit-Primitive Matrices, arXiv:2305.03930 [math.CO], 2023.
• L. Carlitz and R. Scoville, Up-down sequences, Duke Math. J. (39) (1972), 583-598.
• Jane Ivy Coons and Seth Sullivant, The h*-polynomial of the order polytope of the zig-zag poset, arXiv:1901.07443 [math.CO], 2019.
• Sela Fried, A formula for the number of up-down words, arXiv:2503.02005 [math.CO], 2025.
• Emma L. L. Gao, Sergey Kitaev, and Philip B. Zhang, Pattern-avoiding alternating words, arXiv:1505.04078 [math.CO], 2015.
• 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.
• Hyeong-Kwan Ju, On the sequence generated by a certain type of matrices, Honam Math. J. 39, No. 4, 665-675 (2017).
• Daeseok Lee and H.-K. Ju, An Extension of Hibi's palindromic theorem, arXiv preprint arXiv:1503.05658 [math.CO], 2015.
• T. Kyle Petersen and Yan Zhuang, Zig-zag Eulerian polynomials, arXiv:2403.07181 [math.CO], 2024.
• R. P. Stanley, Examples of Magic Labelings, Unpublished Notes, 1973. [Cached copy, with permission] See p. 31.
• Guoce Xin and Yueming Zhong, Proving some conjectures on Kekulé numbers for certain benzenoids by using Chebyshev polynomials, arXiv:2201.02376 [math.CO], 2022.

Crossrefs

Rows give A000012, A000027, A000217, A000330, A006322, ...

Columns give A000012, A000045, A000045, A006356, A006357, A006358, ...

Cf. A050447.

Programs

Maple

A050446 := proc(n,m)
    option remember;
    if m=0 then
        1;
    else
        procname(n,m-1)+add( procname(2*k,m-1) *procname(n-1-2*k,m), k=0..floor((n-1)/2) );
    end if;
end proc:
for d from 0 to 12 do
    for m from 0 to d do
        printf("%d,",A050446(d-m,m)) ;
    end do:
end do: # R. J. Mathar, Dec 14 2011
A050446 := := (n, m) -> evalf(abs(add(tan(2*j*Pi/(2*m + 1))^2*sec(2*j*Pi/(2*m + 1))^(n - 1), j = 1 .. m))/(2^(n - 1)*(2*m + 1))): # Sela Fried, Apr 28 2025

Mathematica

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[i-k , k-1], {i, 1, 12}, {k, 1, i}]] (* Jean-François Alcover, Jul 25 2011, after formula *)
<< Omega.m; nmax = 9; Do[cond[n_] = {}; If[n == 0, cond[n] = {a[1] == a[2]}, AppendTo[cond[n], {a[1] + a[2] == a[2 n + 2], a[2 n] + a[2 n + 1] == a[2 n + 2]}]; If[n > 1, Do[AppendTo[cond[n], a[2 j] + a[2 j + 1] + a[2 j + 2] == a[2 n + 2]], {j, n - 1}]]]; cond[n] = Flatten[cond[n]]; f[n_] = OEqSum[Product[x[i]^a[i], {i, 2 n + 2}], cond[n], u][[1]] /. x[2 n + 2] -> y /. x[] -> 1; Do[f[n] = OEqR[f[n], Subscript[u, j]], {j, Length[cond[n]]}], {n, 0, nmax}]; Grid[Table[CoefficientList[Series[f[n], {y, 0, nmax}], y], {n, 0, nmax}]] (* _L. Edson Jeffery, Oct 19 2017 *)

Python

from functools import cache
@cache
def T(n, k):
    return T(n, k - 1) + sum(T(2 * j, k - 1) * T(n - 1 - 2 * j, k)
        for j in range(1 + (n - 1) // 2)) if k > 0 else 1
for n in range(6): print([T(n - k, k) for k in range(n + 1)])
# Peter Luschny, Jun 08 2024

Formula

T(n, m) = T(n, m - 1) + Sum_{k=0..(n-1)/2} T(2*k, m - 1)*T(n - 1 - 2*k, m).

From Sela Fried, Apr 08 2025: (Start)

T(n, m) = 1/(2^(n-1)*(2*m+1))*|Sum_{j = 1..m} tan^2(2*j*Pi/(2*m+1))*sec^(n+1)(2*j*Pi/(2*m+1)))|.

G.f. for words of odd length over an alphabet of size m: x*U_{m-1}(1-x^2/2)/V_{m-1}(1-x^2/2),

g.f. for words of even length over an alphabet of size m: 1/V_{m-1}(1-x^2/2),

where U_k(x) and V_k(x) are the Chebyshev polynomials of the second and third kind, respectively. (End)

Extensions

More terms from Naohiro Nomoto, Jul 03 2001