cp's OEIS Frontend

G.f. for row polynomials S(n,x) (signed triangle): 1/(1-x*z+z^2). Unsigned triangle |a(n,m)| has Fibonacci polynomials F(n+1,x) as row polynomials with g.f. 1/(1-x*z-z^2). |a(n,m)| triangle has rows of Pascal's triangle A007318 in the even-numbered diagonals (odd-numbered ones have only 0's).

Row sums (unsigned triangle) A000045(n+1) (Fibonacci). Row sums (signed triangle) S(n,1) sequence = periodic(1,1,0,-1,-1,0) = A010892.

Alternating row sums A049347(n) = S(n,-1) = periodic(1,-1,0). - Wolfdieter Lang, Nov 04 2011

S(n,x) is the characteristic polynomial of the adjacency matrix of the n-path. - Michael Somos, Jun 24 2002

S(n,x) is also the matching polynomial of the n-path. - Eric W. Weisstein, Apr 10 2017

|T(n,k)| = number of compositions of n+1 into k+1 odd parts. Example: |T(7,3)| = 10 because we have (1,1,3,3), (1,3,1,3), (1,3,3,1), (3,1,1,3), (3,1,3,1), (3,3,1,1), (1,1,1,5), (1,1,5,1), (1,5,1,1) and (5,1,1,1). - Emeric Deutsch, Apr 09 2005

S(n,x)= R(n,x) + S(n-2,x), n >= 2, S(-1,x)=0, S(0,x)=1, R(n,x):=2*T(n,x/2) = Sum_{m=0..n} A127672(n,m)*x^m (monic integer Chebyshev T-Polynomials). This is the rewritten so-called trace of the transfer matrix formula for the T-polynomials. - Wolfdieter Lang, Dec 02 2010

In a regular N-gon inscribed in a unit circle, the side length is d(N,1) = 2*sin(Pi/N). The length ratio R(N,k):=d(N,k)/d(N,1) for the (k-1)-th diagonal, with k from {2,3,...,floor(N/2)}, N >= 4, equals S(k-1,x) = sin(k*Pi/N)/sin(Pi/N) with x=rho(N):=R(N,2) = 2*cos(Pi/N). Example: N=7 (heptagon), rho=R(7,2), sigma:=R(N,3) = S(2,rho) = rho^2 - 1. Motivated by the quoted paper by P. Steinbach. - Wolfdieter Lang, Dec 02 2010

From Wolfdieter Lang, Jul 12 2011: (Start)

In q- or basic analysis, q-numbers are [n]_q := S(n-1,q+1/q) = (q^n-(1/q)^n)/(q-1/q), with the row polynomials S(n,x), n >= 0.

The zeros of the row polynomials S(n-1,x) are (from those of Chebyshev U-polynomials):

x(n-1;k) = +- t(k,rho(n)), k = 1..ceiling((n-1)/2), n >= 2, with t(n,x) the row polynomials of A127672 and rho(n):= 2*cos(Pi/n). The simple vanishing zero for even n appears here as +0 and -0.

Factorization of the row polynomials S(n-1,x), x >= 1, in terms of the minimal polynomials of cos(2 Pi/2), called Psi(n,x), with coefficients given by A181875/A181876:

S(n-1,x) = (2^(n-1))*Product_{n>=1}(Psi(d,x/2), 2 < d | 2n).

(From the rewritten eq. (3) of the Watkins and Zeitlin reference, given under A181872.) [See the W. Lang ArXiv link, Proposition 9, eq. (62). - Wolfdieter Lang, Apr 14 2018]

(End)

The discriminants of the S(n,x) polynomials are found in A127670. - Wolfdieter Lang, Aug 03 2011

This is an example for a subclass of Riordan convolution arrays (lower triangular matrices) called Bell arrays. See the L. W. Shapiro et al. reference under A007318. If a Riordan array is named (G(z),F(z)) with F(z)=z*Fhat(z), the o.g.f. for the row polynomials is G(z)/(1-x*z*Fhat(z)), and it becomes a Bell array if G(z)=Fhat(z). For the present Bell type triangle G(z)=1/(1+z^2) (see the o.g.f. comment above). This leads to the o.g.f. for the column no. k, k >= 0, x^k/(1+x^2)^(k+1) (see the formula section), the one for the row sums and for the alternating row sums (see comments above). The Riordan (Bell) A- and Z-sequences (defined in a W. Lang link under A006232, with references) have o.g.f.s 1-x*c(x^2) and -x*c(x^2), with the o.g.f. of the Catalan numbers A000108. Together they lead to a recurrence given in the formula section. - Wolfdieter Lang, Nov 04 2011

The determinant of the N x N matrix S(N,[x[1], ..., x[N]]) with elements S(m-1,x[n]), for n, m = 1, 2, ..., N, and for any x[n], is identical with the determinant of V(N,[x[1], ..., x[N]]) with elements x[n]^(m-1) (a Vandermondian, which equals Product_{1 <= i < j<= N} (x[j] - x[i])). This is a special instance of a theorem valid for any N >= 1 and any monic polynomial system p(m,x), m>=0, with p(0,x) = 1. For this theorem see the Vein-Dale reference, p. 59. Thanks to L. Edson Jeffery for an email asking for a proof of the non-singularity of the matrix S(N,[x[1], ...., x[N]]) if and only if the x[j], j = 1..N, are pairwise distinct. - Wolfdieter Lang, Aug 26 2013

These S polynomials also appear in the context of modular forms. The rescaled Hecke operator T*n = n^((1-k)/2)*T_n acting on modular forms of weight k satisfies T*(p^n) = S(n, T*p), for each prime p and positive integer n. See the Koecher-Krieg reference, p. 223. - _Wolfdieter Lang, Jan 22 2016

For a shifted o.g.f. (mod signs), its compositional inverse, and connections to Motzkin and Fibonacci polynomials, non-crossing partitions and other combinatorial structures, see A097610. - Tom Copeland, Jan 23 2016

From M. Sinan Kul, Jan 30 2016; edited by Wolfdieter Lang, Jan 31 2016 and Feb 01 2016: (Start)

Solutions of the Diophantine equation u^2 + v^2 - k*u*v = 1 for integer k given by (u(k,n), v(k,n)) = (S(n,k), S(n-1,k)) because of the Cassini-Simson identity: S(n,x)^2 - S(n+1,x)*S(n-1, x) = 1, after use of the S-recurrence. Note that S(-n, x) = -S(-n-2, x), n >= 1, and the periodicity of some S(n, k) sequences.

Hence another way to obtain the row polynomials would be to take powers of the matrix [x, -1; 1,0]: S(n, x) = (([x, -1; 1, 0])^n)[1,1], n >= 0.

See also a Feb 01 2016 comment on A115139 for a well-known S(n, x) sum formula.

Then we have with the present T triangle

A039834(n) = -i^(n+1)*T(n-1, k) where i is the imaginary unit and n >= 0.

A051286(n) = Sum_{i=0..n} T(n,i)^2 (see the Philippe Deléham, Nov 21 2005 formula),

A181545(n) = Sum_{i=0..n+1} abs(T(n,i)^3),

A181546(n) = Sum_{i=0..n+1} T(n,i)^4,

A181547(n) = Sum_{i=0..n+1} abs(T(n,i)^5).

S(n, 0) = A056594(n), and for k = 1..10 the sequences S(n-1, k) with offset n = 0 are A128834, A001477, A001906, A001353, A004254, A001109, A004187, A001090, A018913, A004189.

(End)

For more on the Diophantine equation presented by Kul, see the Ismail paper. - Tom Copeland, Jan 31 2016

The o.g.f. for the Legendre polynomials L(n,x) is 1 / sqrt(1- 2x*z + z^2), and squaring it gives the o.g.f. of U(n,x), A053117, so Sum_{k=0..n} L(k,x/2) L(n-k,x/2) = S(n,x). This gives S(n,x) = L(n/2,x/2)^2 + 2*Sum_{k=0..n/2-1} L(k,x/2) L(n-k,x/2) for n even and S(n,x) = 2*Sum_{k=0..(n-1)/2} L(k,x/2) L(n-k,x/2) for odd n. For a connection to elliptic curves and modular forms, see A053117. For the normalized Legendre polynomials, see A100258. For other properties and relations to other polynomials, see Allouche et al. - Tom Copeland, Feb 04 2016

LG(x,h1,h2) = -log(1 - h1*x + h2*x^2) = Sum_{n>0} F(n,-h1,h2,0,..,0) x^n/n is a log series generator of the bivariate row polynomials of A127672 with A127672(0,0) = 0 and where F(n,b1,b2,..,bn) are the Faber polynomials of A263916. Exp(LG(x,h1,h2)) = 1 / (1 - h1*x + h2*x^2 ) is the o.g.f. of the bivariate row polynomials of this entry. - Tom Copeland, Feb 15 2016 (Instances of the bivariate o.g.f. for this entry are on pp. 5 and 18 of Sunada. - Tom Copeland, Jan 18 2021)

For distinct odd primes p and q the Legendre symbol can be written as Legendre(q,p) = Product_{k=1..P} S(q-1, 2*cos(2*Pi*k/p)), with P = (p-1)/2. See the Lemmermeyer reference, eq. (8.1) on p. 236. Using the zeros of S(q-1, x) (see above) one has S(q-1, x) = Product_{l=1..Q} (x^2 - (2*cos(Pi*l/q))^2), with Q = (q-1)/2. Thus S(q-1, 2*cos(2*Pi*k/p)) = ((-4)^Q)*Product_{l=1..Q} (sin^2(2*Pi*k/p) - sin^2(Pi*l/q)) = ((-4)^Q)*Product_{m=1..Q} (sin^2(2*Pi*k/p) - sin^2(2*Pi*m/q)). For the proof of the last equality see a W. Lang comment on the triangle A057059 for n = Q and an obvious function f. This leads to Eisenstein's proof of the quadratic reciprocity law Legendre(q,p) = ((-1)^(P*Q)) * Legendre(p,q), See the Lemmermeyer reference, pp. 236-237. - Wolfdieter Lang, Aug 28 2016

For connections to generalized Fibonacci polynomials, compare their generating function on p. 5 of the Amdeberhan et al. link with the o.g.f. given above for the bivariate row polynomials of this entry. - Tom Copeland, Jan 08 2017

The formula for Ramanujan's tau function (see A000594) for prime powers is tau(p^k) = p^(11*k/2)*S(k, p^(-11/2)*tau(p)) for k >= 1, and p = A000040(n), n >= 1. See the Hardy reference, p. 164, eqs. (10.3.4) and (10.3.6) rewritten in terms of S. - Wolfdieter Lang, Jan 27 2017

From Wolfdieter Lang, May 08 2017: (Start)

The number of zeros Z(n) of the S(n, x) polynomials in the open interval (-1,+1) is 2*b(n) for even n >= 0 and 1 + 2*b(n) for odd n >= 1, where b(n) = floor(n/2) - floor((n+1)/3). This b(n) is the number of integers k in the interval (n+1)/3 < k <= floor(n/2). See a comment on the zeros of S(n, x) above, and b(n) = A008615(n-2), n >= 0. The numbers Z(n) have been proposed (with a conjecture related to A008611) by Michel Lagneau, as the number of zeros of Fibonacci polynomials on the imaginary axis (-I,+I), with I=sqrt(-1). They are Z(n) = A008611(n-1), n >= 0, with A008611(-1) = 0. Also Z(n) = A194960(n-4), n >= 0. Proof using the A008611 version. A194960 follows from this.

In general the number of zeros Z(a;n) of S(n, x) for n >= 0 in the open interval (-a,+a) for a from the interval (0,2) (x >= 2 never has zeros, and a=0 is trivial: Z(0;n) = 0) is with b(a;n) = floor(n//2) - floor((n+1)*arccos(a/2)/Pi), as above Z(a;n) = 2*b(a;n) for even n >= 0 and 1 + 2*b(a;n) for odd n >= 1. For the closed interval [-a,+a] Z(0;n) = 1 and for a from (0,1) one uses for Z(a;n) the values b(a;n) = floor(n/2) - ceiling((n+1)*arccos(a/2)/Pi) + 1. (End)

The Riordan row polynomials S(n, x) (Chebyshev S) belong to the Boas-Buck class (see a comment and references in A046521), hence they satisfy the Boas-Buck identity: (E_x - n*1)*S(n, x) = (E_x + 1)*Sum_{p=0..n-1} (1 - (-1)^p)*(-1)^((p+1)/2)*S(n-1-p, x), for n >= 0, where E_x = x*d/dx (Euler operator). For the triangle T(n, k) this entails a recurrence for the sequence of column k, given in the formula section. - Wolfdieter Lang, Aug 11 2017

The e.g.f. E(x,t) := Sum_{n>=0} (t^n/n!)*S(n,x) for the row polynomials is obtained via inverse Laplace transformation from the above given o.g.f. as E(x,t) = ((1/xm)*exp(t/xm) - (1/xp)*exp(t/xp) )/(xp - xm) with xp = (x + sqrt(x^2-4))/2 and xm = (x - sqrt(x^2-4))/2. - Wolfdieter Lang, Nov 08 2017

From Wolfdieter Lang, Apr 12 2018: (Start)

Factorization of row polynomials S(n, x), for n >= 1, in terms of C polynomials (not Chebyshev C) with coefficients given in A187360. This is obtained from the factorization into Psi polynomials (see the Jul 12 2011 comment above) but written in terms of minimal polynomials of 2*cos(2*Pi/n) with coefficients in A232624:

S(2*k, x) = Product_{2 <= d | (2*k+1)} C(d, x)*(-1)^deg(d)*C(d, -x), with deg(d) = A055034(d) the degree of C(d, x).

S(2*k+1, x) = Product_{2 <= d | 2*(k+1)} C(d, x) * Product_{3 <= 2*d + 1 | (k+1)} (-1)^(deg(2*d+1))*C(2*d+1, -x).

Note that (-1)^(deg(2*d+1))*C(2*d+1, -x)*C(2*d+1, x) pairs always appear.

The number of C factors of S(2*k, x), for k >= 0, is 2*(tau(2*k+1) - 1) = 2*(A099774(k+1) - 1) = 2*A095374(k), and for S(2*k+1, x), for k >= 0, it is tau(2*(k+1)) + tau_{odd}(k+1) - 2 = A302707(k), with tau(2*k+1) = A099774(k+1), tau(n) = A000005 and tau(2*(k+1)) = A099777(k+1).

For the reverse problem, the factorization of C polynomials into S polynomials, see A255237. (End)

The S polynomials with general initial conditions S(a,b;n,x) = x*S(a,b;n-1,x) - S(a,b;n-2,x), for n >= 1, with S(a,b;-1,x) = a and S(a,b;0,x) = b are S(a,b;n,x) = b*S(n, x) - a*S(n-1, x), for n >= -1. Recall that S(-2, x) = -1 and S(-1, x) = 0. The o.g.f. is G(a,b;z,x) = (b - a*z)/(1 - x*z + z^2). - Wolfdieter Lang, Oct 18 2019

Also the convolution triangle of A101455. - Peter Luschny, Oct 06 2022

From Wolfdieter Lang, Apr 26 2023: (Start)

Multi-section of S-polynomials: S(m*n+k, x) = S(m+k, x)*S(n-1, R(m, x)) - S(k, x)*S(n-2, R(m, x)), with R(n, x) = S(n, x) - S(n-2, x) (see A127672), S(-2, x) = -1, and S(-1, x) = 0, for n >= 0, m >= 1, and k = 0, 1, ..., m-1.

O.g.f. of {S(m*n+k, y)}_{n>=0}: G(m,k,y,x) = (S(k, y) - (S(k, y)*R(m, y) - S(m+k, y))*x)/(1 - R(m,y)*x + x^2).

See eqs. (40) and (49), with r = x or y and s =-1, of the G. Detlefs and W. Lang link at A034807. (End)

S(n, x) for complex n and complex x: S(n, x) = ((-i/2)/sqrt(1 - (x/2)^2))*(q(x/2)*exp(+n*log(q(x/2))) - (1/q(x/2))*exp(-n*log(q(x/2)))), with q(x) = x + sqrt(1 - x^2)*i. Here log(z) = |z| + Arg(z)*i, with Arg(z) from [-Pi,+Pi) (principal branch). This satisfies the recurrence relation for S because it is derived from the Binet - de Moivre formula for S. Examples: S(n/m, 0) = cos((n/m)*Pi/4), for n >= 0 and m >= 1. S(n*i, 0) = (1/2)*(1 + exp(n*Pi))*exp(-(n/2)*Pi), for n >= 0. S(1+i, 2+i) = 0.6397424847... + 1.0355669490...*i. Thanks to Roberto Alfano for asking a question leading to this formula. - Wolfdieter Lang, Jun 05 2023

Lim_{n->oo} S(n, x)/S(n-1, x) = r(x) = (x - sqrt(x^2 -4))/2, for |x| >= 2. For x = +-2, this limit is +-1. - Wolfdieter Lang, Nov 15 2023

Also known as Stirling set numbers.

S(n,k) enumerates partitions of an n-set into k nonempty subsets.

The o.g.f. for the sequence of diagonal k (k=0 for the main diagonal) is G(k,x) = ((x^k)/(1-x)^(2*k+1))*Sum_{m=0..k-1} A008517(k,m+1)*x^m. A008517 is the second-order Eulerian triangle. - Wolfdieter Lang, Oct 14 2005

From Philippe Deléham, Nov 14 2007: (Start)

Sum_{k=0..n} S(n,k)*x^k = B_n(x), where B_n(x) = Bell polynomials.

The first few Bell polynomials are:

B_0(x) = 1;

B_1(x) = 0 + x;

B_2(x) = 0 + x + x^2;

B_3(x) = 0 + x + 3x^2 + x^3;

B_4(x) = 0 + x + 7x^2 + 6x^3 + x^4;

B_5(x) = 0 + x + 15x^2 + 25x^3 + 10x^4 + x^5;

B_6(x) = 0 + x + 31x^2 + 90x^3 + 65x^4 + 15x^5 + x^6;

(End)

This is the Sheffer triangle (1, exp(x) - 1), an exponential (binomial) convolution triangle. The a-sequence is given by A006232/A006233 (Cauchy sequence). The z-sequence is the zero sequence. See the link under A006232 for the definition and use of these sequences. The row sums give A000110 (Bell), and the alternating row sums give A000587 (see the Philippe Deléham formulas and crossreferences below). - Wolfdieter Lang, Oct 16 2014

Also the inverse Bell transform of the factorial numbers (A000142). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015

From Wolfdieter Lang, Feb 21 2017: (Start)

The transposed (trans) of this lower triagonal Sheffer matrix of the associated type S = (1, exp(x) - 1) (taken as N X N matrix for arbitrarily large N) provides the transition matrix from the basis {x^n/n!}, n >= 0, to the basis {y^n/n!}, n >= 0, with y^n/n! = Sum_{m>=n} S^{trans}(n, m) x^m/m! = Sum_{m>=0} x^m/m!*S(m, n).

The Sheffer transform with S = (g, f) of a sequence {a_n} to {b_n} for n >= 0, in matrix notation vec(b) = S vec(a), satisfies, with e.g.f.s A and B, B(x) = g(x)*A(f(x)) and B(x) = A(y(x)) identically, with vec(xhat) = S^{trans,-1} vec(yhat) in symbolic notation with vec(xhat)_n = x^n/n! (similarly for vec(yhat)).

(End)

For k >= 1 S(n, k) = h^{(k)}{n-k}, the complete homogeneous symmetric function of the k symbols 1,2, ..., k, of degree n-k. Thus S(n, k) is for k >= 1 the (dimensionless) volume of the multichoose(k, n-k) = binomial(n-1, k-1) polytopes of dimension n-k with (dimensionless) side lengths from the set {1, 2, ..., k}. See an example below. - _Wolfdieter Lang, May 26 2017

Number of partitions of {1, 2, ..., n+1} into k+1 nonempty subsets such that no subset contains two adjacent numbers. - Thomas Anton, Sep 26 2022

a(n)/A027642(n) (Bernoulli numbers) provide the a-sequence for the Sheffer matrix A094816 (coefficients of orthogonal Poisson-Charlier polynomials). See the W. Lang link under A006232 for a- and z-sequences for Sheffer matrices. The corresponding z-sequence is given by the rationals A130189(n)/A130190(n).

Harvey (2008) describes a new algorithm for computing Bernoulli numbers. His method is to compute B(k) modulo p for many small primes p and then reconstruct B(k) via the Chinese Remainder Theorem. The time complexity is O(k^2 log(k)^(2+eps)). The algorithm is especially well-suited to parallelization. - Jonathan Vos Post, Jul 09 2008

Regard the Bernoulli numbers as forming a vector = B_n, and the variant starting (1, 1/2, 1/6, 0, -1/30, ...), (i.e., the first 1/2 has sign +) as forming a vector Bv_n. The relationship between the Pascal triangle matrix, B_n, and Bv_n is as follows: The binomial transform of B_n = Bv_n. B_n is unchanged when multiplied by the Pascal matrix with rows signed (+-+-, ...), i.e., (1; -1,-1; 1,2,1; ...). Bv_n is unchanged when multiplied by the Pascal matrix with columns signed (+-+-, ...), i.e., (1; 1,-1; 1,-2,1; 1,-3,3,-1; ...). - Gary W. Adamson, Jun 29 2012

The sequence of the Bernoulli numbers B_n = a(n)/A027642(n) is the inverse binomial transform of the sequence {A164555(n)/A027642(n)}, illustrated by the fact that they appear as top row and left column in A190339. - Paul Curtz, May 13 2016

Named by de Moivre (1773; "the numbers of Mr. James Bernoulli") after the Swiss mathematician Jacob Bernoulli (1655-1705). - Amiram Eldar, Oct 02 2023

The unsigned numbers are also called Stirling cycle numbers: |s(n,k)| = number of permutations of n objects with exactly k cycles.

Mirror image of the triangle A054654. - Philippe Deléham, Dec 30 2006

Also the triangle gives coefficients T(n,k) of x^k in the expansion of C(x,n) = (a(k)*x^k)/n!. - Mokhtar Mohamed, Dec 04 2012

From Wolfdieter Lang, Nov 14 2018: (Start)

This is the Sheffer triangle of Jabotinsky type (1, log(1 + x)). See the e.g.f. of the triangle below.

This is the inverse Sheffer triangle of the Stirling2 Sheffer triangle A008275.

The a-sequence of this Sheffer triangle (see a W. Lang link in A006232)

is from the e.g.f. A(x) = x/(exp(x) -1) a(n) = Bernoulli(n) = A027641(n)/A027642(n), for n >= 0. The z-sequence vanishes.

The Boas-Buck sequence for the recurrences of columns has o.g.f. B(x) = Sum_{n>=0} b(n)*x^n = 1/((1 + x)*log(1 + x)) - 1/x. b(n) = (-1)^(n+1)*A002208(n+1)/A002209(n+1), b = {-1/2, 5/12, -3/8, 251/720, -95/288, 19087/60480,...}. For the Boas-Buck recurrence of Riordan and Sheffer triangles see the Aug 10 2017 remark in A046521, adapted to the Sheffer case, also for two references. See the recurrence and example below. (End)

Let G(n,m,k) be the number of simple labeled graphs on [n] with m edges and k components. Then T(n,k) = Sum (-1)^m*G(n,m,k). See the Read link below. Equivalently, T(n,k) = Sum mu(0,p) where the sum is over all set partitions p of [n] containing k blocks and mu is the Moebius function in the incidence algebra associated to the set partition lattice on [n]. - Geoffrey Critzer, May 11 2024

Essentially the same as A001700, which has more information.

Note that the unique rooted tree with no edges has no leaves, so a(0)=1 is by convention. - Michael Somos, Jul 30 2011

Number of ordered partitions of n into n parts, allowing zeros (cf. A097070) is binomial(2*n-1,n) = a(n) = essentially A001700. - Vladeta Jovovic, Sep 15 2004

Hankel transform is A000027; example: Det([1,1,3,10;1,3,10,35;3,10,35,126; 10,35,126,462]) = 4. - Philippe Deléham, Apr 13 2007

a(n) is the number of functions f:[n]->[n] such that for all x,y in [n] if xA045992(n). - Geoffrey Critzer, Apr 02 2009

Hankel transform of the aeration of this sequence is A000027 doubled: 1,1,2,2,3,3,... - Paul Barry, Sep 26 2009

The Fi1 and Fi2 triangle sums of A039599 are given by the terms of this sequence. For the definitions of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011

Alternating row sums of Riordan triangle A094527. See the Philippe Deléham formula. - Wolfdieter Lang, Nov 22 2012

(-2)*a(n) is the Z-sequence for the Riordan triangle A110162. For the notion of Z- and A-sequences for Riordan arrays see the W. Lang link under A006232 with details and references. - Wolfdieter Lang, Nov 22 2012

From Gus Wiseman, Jun 27 2021: (Start)

Also the number of integer compositions of 2n with alternating (or reverse-alternating) sum 0 (ranked by A344619). This is equivalent to Ran Pan's comment at A001700. For example, the a(0) = 1 through a(3) = 10 compositions are:

() (11) (22) (33)

(121) (132)

(1111) (231)

(1122)

(1221)

(2112)

(2211)

(11121)

(12111)

(111111)

For n > 0, a(n) is also the number of integer compositions of 2n with alternating sum 2.

(End)

Number of terms in the expansion of (x_1+x_2+...+x_n)^n. - César Eliud Lozada, Jan 08 2022

In the Formula section, some contributors use T(n,k) = D(n-k, k) (for 0 <= k <= n), which is the triangular version of the square array (D(n,k): n,k >= 0). Conversely, D(n,k) = T(n+k,k) for n,k >= 0. - Petros Hadjicostas, Aug 05 2020

Also called the tribonacci triangle [Alladi and Hoggatt (1977)]. - N. J. A. Sloane, Mar 23 2014

D(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0), (0,1), (1,1). - Joerg Arndt, Jul 01 2011 [Corrected by N. J. A. Sloane, May 30 2020]

Or, triangle read by rows of coefficients of polynomials P[n](x) defined by P[0] = 1, P[1] = x+1; for n >= 2, P[n] = (x+1)*P[n-1] + x*P[n-2].

D(n, k) is the number of k-matchings of a comb-like graph with n+k teeth. Example: D(1, 3) = 7 because the graph consisting of a horizontal path ABCD and the teeth Aa, Bb, Cc, Dd has seven 3-matchings: four triples of three teeth and the three triples {Aa, Bb, CD}, {Aa, Dd, BC}, {Cc, Dd, AB}. Also D(3, 1)=7, the 1-matchings of the same graph being the seven edges: {AB}, {BC}, {CD}, {Aa}, {Bb}, {Cc}, {Dd}. - Emeric Deutsch, Jul 01 2002

Sum of n-th antidiagonal of the array D is A000129(n+1). - Reinhard Zumkeller, Dec 03 2004 [Edited by Petros Hadjicostas, Aug 05 2020 so that the counting of antidiagonals of D starts at n = 0. That is, the sum of the terms in the n-th row of the triangles T is A000129(n+1).]

The A-sequence for this Riordan type triangle (see one of Paul Barry's comments under Formula) is A112478 and the Z-sequence the trivial: {1, 0, 0, 0, ...}. See the W. Lang link under A006232 for Sheffer a- and z-sequences where also Riordan A- and Z-sequences are explained. This leads to the recurrence for the triangle given below. - Wolfdieter Lang, Jan 21 2008

The triangle or chess sums, see A180662 for their definitions, link the Delannoy numbers with twelve different sequences, see the crossrefs. All sums come in pairs due to the symmetrical nature of this triangle. The knight sums Kn14 and Kn15 have been added. It is remarkable that all knight sums are related to the tribonacci numbers, that is, A000073 and A001590, but none of the others. - Johannes W. Meijer, Sep 22 2010

This sequence, A008288, is jointly generated with A035607 as an array of coefficients of polynomials u(n,x): initially, u(1,x) = v(1,x) = 1; for n > 1, u(n,x) = x*u(n-1,x) + v(n-1) and v(n,x) = 2*x*u(n-1,x) + v(n-1,x). See the Mathematica section. - Clark Kimberling, Mar 09 2012

Row n, for n > 0, of Roger L. Bagula's triangle in the Example section shows the coefficients of the polynomial u(n) = c(0) + c(1)*x + ... + c(n)*x^n which is the numerator of the n-th convergent of the continued fraction [k, k, k, ...], where k = sqrt(x) + 1/sqrt(x); see A230000. - Clark Kimberling, Nov 13 2013

In an n-dimensional hypercube lattice, D(n,k) gives the number of nodes situated at a Minkowski (Manhattan) distance of k from a given node. In cellular automata theory, the cells at Manhattan distance k are called the von Neumann neighborhood of radius k. For k=1, see A005843. - Dmitry Zaitsev, Dec 10 2015

These numbers appear as the coefficients of series relating spherical and bispherical harmonics, in the solutions of Laplace's equation in 3D. [Majic 2019, Eq. 22] - Matt Majic, Nov 24 2019

From Peter Bala, Feb 19 2020: (Start)

The following remarks assume an offset of 1 in the row and column indices of the triangle.

The sequence of row polynomials T(n,x), beginning with T(1,x) = x, T(2,x) = x + x^2, T(3,x) = x + 3*x^2 + x^3, ..., is a strong divisibility sequence of polynomials in the ring Z[x]; that is, for all positive integers n and m, poly_gcd(T(n,x), T(m,x)) = T(gcd(n, m), x) - apply Norfleet (2005), Theorem 3. Consequently, the sequence (T(n,x): n >= 1) is a divisibility sequence in the polynomial ring Z[x]; that is, if n divides m then T(n,x) divides T(m,x) in Z[x].

Let S(x) = 1 + 2*x + 6*x^2 + 22*x^3 + ... denote the o.g.f. for the large Schröder numbers A006318. The power series (x*S(x))^n, n = 2, 3, 4, ..., can be expressed as a linear combination with polynomial coefficients of S(x) and 1: (x*S(x))^n = T(n-1,-x) - T(n,-x)*S(x). The result can be extended to negative integer n if we define T(0,x) = 0 and T(-n,x) = (-1)^(n+1) * T(n,x)/x^n. Cf. A115139.

[In the previous two paragraphs, D(n,x) was replaced with T(n,x) because the contributor is referring to the rows of the triangle T(n,k), not the rows of the array D(n,k). - Petros Hadjicostas, Aug 05 2020] (End)

Named after the French amateur mathematician Henri-Auguste Delannoy (1833-1915). - Amiram Eldar, Apr 15 2021

D(i,j) = D(j,i). With this and Dmitry Zaitsev's Dec 10 2015 comment, D(i,j) can be considered the number of points at L1 distance <= i in Z^j or the number of points at L1 distance <= j in Z^i from any given point. The rows and columns of D(i,j) are the crystal ball sequences on cubic lattices. See the first example below. The n-th term in the k-th crystal ball sequence can be considered the number of points at distance <= n from any point in a k-dimensional cubic lattice, or the number of points at distance <= k from any point in an n-dimensional cubic lattice. - Shel Kaphan, Jan 01 2023 and Jan 07 2023

Dimensions of hom spaces Hom(R^{(i)}, R^{(j)}) in the Delannoy category attached to the oligomorphic group of order preserving self-bijections of the real line. - Noah Snyder, Mar 22 2023

Apart from a sign flip in a(1), the same as A027641.

a(n) is also the numerator of the n-th term of the binomial transform of the sequence of Bernoulli numbers, i.e., of the sequence of fractions A027641(n)/A027642(n).

a(n)/A027642(n) with e.g.f. x/(1-exp(-x)) is the a-sequence for the Sheffer matrix A094645, see the W. Lang link under A006232 for Sheffer a- and z-sequences. - Wolfdieter Lang, Jun 20 2011

a(n)/A027642(n) also give the row sums of the rational triangle of the coefficients of the Bernoulli polynomials A053382/A053383 (falling powers) or A196838/A196839 (rising powers). - Wolfdieter Lang, Oct 25 2011

Given M = the beheaded Pascal's triangle, A074909; with B_n as a vector V, with numerators shown: (1, 1, 1, ...). Then M*V = [1, 2, 3, 4, 5, ...]. If the sign in a(1) is negative in V, then M*V = [1, 0, 0, 0, ...]. - Gary W. Adamson, Mar 09 2012

One might interpret the term "'original' Bernoulli numbers" as numbers given by the e.g.f. x/(1-exp(-x)). - Peter Luschny, Jun 17 2012

Let B(n) = a(n)/A027642(n) then B(n) = Integral_{x=0..1} F_n(x) where F_n(x) are the signed Fubini polynomials F_n(x) = Sum_{k=0..n} (-1)^n*Stirling2(n,k)*k!*(-x)^k (see illustration). - Peter Luschny, Jan 09 2017

Another name: Triangle of signless Stirling numbers of the first kind.

Triangle T(n,k), 0<=k<=n, read by rows given by [0,1,1,2,2,3,3,4,4,5,5,...] DELTA [1,0,1,0,1,0,1,0,1,...] where DELTA is the operator defined in A084938.

A094645*A007318 as infinite lower triangular matrices.

Row sums are the factorial numbers. - Roger L. Bagula, Apr 18 2008

Exponential Riordan array [1/(1-x), log(1/(1-x))]. - Ralf Stephan, Feb 07 2014

Also the Bell transform of the factorial numbers (A000142). For the definition of the Bell transform see A264428 and for cross-references A265606. - Peter Luschny, Dec 31 2015

This is the lower triagonal Sheffer matrix of the associated or Jabotinsky type |S1| = (1, -log(1-x)) (see the W. Lang link under A006232 for the notation and references). This implies the e.g.f.s given below. |S1| is the transition matrix from the monomial basis {x^n} to the rising factorial basis {risefac(x,n)}, n >= 0. - Wolfdieter Lang, Feb 21 2017

T(n, k), for n >= k >= 1, is also the total volume of the n-k dimensional cell (polytope) built from the n-k orthogonal vectors of pairwise different lengths chosen from the set {1, 2, ..., n-1}. See the elementary symmetric function formula for T(n, k) and an example below. - Wolfdieter Lang, May 28 2017

From Wolfdieter Lang, Jul 20 2017: (Start)

The compositional inverse w.r.t. x of y = y(t;x) = x*(1 - t(-log(1-x)/x)) = x + t*log(1-x) is x = x(t;y) = ED(y,t) := Sum_{d>=0} D(d,t)*y^(d+1)/(d+1)!, the e.g.f. of the o.g.f.s D(d,t) = Sum_{m>=0} T(d+m, m)*t^m of the diagonal sequences of the present triangle. See the P. Bala link for a proof (there d = n-1, n >= 1, is the label for the diagonals).

This inversion gives D(d,t) = P(d, t)/(1-t)^(2*d+1), with the numerator polynomials P(d, t) = Sum_{m=0..d} A288874(d, m)*t^m. See an example below. See also the P. Bala formula in A112007. (End)

For n > 0, T(n,k) is the number of permutations of the integers from 1 to n which have k visible digits when viewed from a specific end, in the sense that a higher value hides a lower one in a subsequent position. - Ian Duff, Jul 12 2019

This is a binomial convolution triangle (Sheffer triangle) of the Appell type: (exp(-x)/(1-x),x), i.e., the e.g.f. of column k is (exp(-x)/(1-x))*(x^k/k!). See the e.g.f. given by V. Jovovic below. - Wolfdieter Lang, Jan 21 2008

The formula T(n,k) = binomial(n,k)*A000166(n-k), with the derangements numbers (subfactorials) A000166 (see also the Charalambides reference) shows the Appell type of this triangle. - Wolfdieter Lang, Jan 21 2008

T(n,k) is the number of permutations of {1,2,...,n} having k pairs of consecutive right-to-left minima (0 is considered a right-to-left minimum for each permutation). Example: T(4,2)=6 because we have 1243, 1423, 4123, 1324, 3124 and 2134; for example, 1324 has right-to-left minima in positions 0-1,3-4 and 2134 has right-to-left minima in positions 0,2-3-4, the consecutive ones being joined by "-". - Emeric Deutsch, Mar 29 2008

T is an example of the group of matrices outlined in the table in A132382--the associated matrix for the sequence aC(0,1). - Tom Copeland, Sep 10 2008

A refinement of this triangle is given by A036039. - Tom Copeland, Nov 06 2012

This triangle equals (A211229(2*n,2*k)) n,k >= 0. - Peter Bala, Dec 17 2014

Inverse lower triangular matrix of A049310(n,m) (coefficients of Chebyshev's S polynomials).

Walks with a wall: triangle of number of n-step walks from (0,0) to (n,m) where each step goes from (a,b) to (a+1,b+1) or (a+1,b-1) and the path stays in the nonnegative quadrant.

T(n,m) is the number of left factors of Dyck paths of length n ending at height m. Example: T(4,2)=3 because we have UDUU, UUDU, and UUUD, where U=(1,1) and D=(1,-1). (This is basically a different formulation of the previous - walks with a wall - property.) - Emeric Deutsch, Jun 16 2011

"The Catalan triangle is formed in the same manner as Pascal's triangle, except that no number may appear on the left of the vertical bar." [Conway and Smith]

G.f. for row polynomials p(n,x) := Sum_{m=0..n} (a(n,m)*x^m): c(z^2)/(1-x*z*c(z^2)). Row sums (x=1): A001405 (central binomial).

In the language of the Shapiro et al. reference such a lower triangular (ordinary) convolution array, considered as a matrix, belongs to the Bell-subgroup of the Riordan-group. The g.f. Ginv(x) of the m=0 column of the inverse of a given Bell-matrix (here A049310) is obtained from its g.f. of the m=0 column (here G(x)=1/(1+x^2)) by Ginv(x)=(f^{(-1)}(x))/x, with f(x) := x*G(x) and f^{(-1)}is the compositional inverse function of f (here one finds, with Ginv(0)=1, c(x^2)). See the Shapiro et al. reference.

Number of involutions of {1,2,...,n} that avoid the patterns 132 and have exactly k fixed points. Example: T(4,2)=3 because we have 2134, 4231 and 3214. Number of involutions of {1,2,...,n} that avoid the patterns 321 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. Number of involutions of {1,2,...,n} that avoid the patterns 213 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1432 and 4231. - Emeric Deutsch, Oct 12 2006

This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=x*T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+y*T(n-1,k)+T(n-1,k+1) for k>=1 . Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0) -> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007

Riordan array (c(x^2),xc(x^2)), where c(x) is the g.f. of Catalan numbers A000108. - Philippe Deléham, Nov 25 2007

A053121^2 = triangle A145973. Convolved with A001405 = triangle A153585. - Gary W. Adamson, Dec 28 2008

By columns without the zeros, n-th row = A000108 convolved with itself n times; equivalent to A = (1 + x + 2x^2 + 5x^3 + 14x^4 + ...), then n-th row = coefficients of A^(n+1). - Gary W. Adamson, May 13 2009

Triangle read by rows,product of A130595 and A064189 considered as infinite lower triangular arrays; A053121 = A130595*A064189 = B^(-1)*A097609*B where B = A007318. - Philippe Deléham, Dec 07 2009

From Mark Dols, Aug 17 2010: (Start)

As an upper right triangle, rows represent powers of 5-sqrt(24):

5 - sqrt(24)^1 = 0.101020514...

5 - sqrt(24)^2 = 0.010205144...

5 - sqrt(24)^3 = 0.001030928...

(Divided by sqrt(96) these powers give a decimal representation of the columns of A007318, with 1/sqrt(96) being the middle column.) (End)

T(n,k) is the number of dispersed Dyck paths of length n (i.e., Motzkin paths of length n with no (1,0) steps at positive heights) having k (1,0)-steps. Example: T(5,3)=4 because, denoting U=(1,1), D=(1,-1), H=(1,0), we have HHHUD, HHUDH, HUDHH, and UDHHH. - Emeric Deutsch, Jun 01 2011

Let S(N,x) denote the N-th Chebyshev S-polynomial in x (see A049310, cf. [W. Lang]). Then x^n = sum_{k=0..n} T(n,k)*S(k,x). - L. Edson Jeffery, Sep 06 2012

This triangle a(n,m) appears also in the (unreduced) formula for the powers rho(N)^n for the algebraic number over the rationals rho(N) = 2*cos(Pi/N) = R(N, 2), the smallest diagonal/side ratio R in the regular N-gon:

rho(N)^n = sum(a(n,m)*R(N,m+1),m=0..n), n>=0, identical in N >= 1. R(N,j) = S(j-1, x=rho(N)) (Chebyshev S (A049310)). See a comment on this under A039599 (even powers) and A039598 (odd powers). Proof: see the Sep 06 2012 comment by L. Edson Jeffery, which follows from T(n,k) (called here a(n,k)) being the inverse of the Riordan triangle A049310. - Wolfdieter Lang, Sep 21 2013

The so-called A-sequence for this Riordan triangle of the Bell type (c(x^2), x*c(x^2)) (see comments above) is A(x) = 1 + x^2. This proves the recurrence given in the formula section by Henry Bottomley for a(n, m) = a(n-1, m-1) + a(n-1, m+1) for n>=1 and m>=1, with inputs. The Z-sequence for this Riordan triangle is Z(x) = x which proves the recurrence a(n,0) = a(n-1,1), n>=1, a(0,0) = 1. For A- and Z-sequences for Riordan triangles see the W. Lang link under A006232. - Wolfdieter Lang, Sep 22 2013

Rows of the triangle describe decompositions of tensor powers of the standard (2-dimensional) representation of the Lie algebra sl(2) into irreducibles. Thus a(n,m) is the multiplicity of the m-th ((m+1)-dimensional) irreducible representation in the n-th tensor power of the standard one. - Mamuka Jibladze, May 26 2015

The Riordan row polynomials p(n, x) belong to the Boas-Buck class (see a comment and references in A046521), hence they satisfy the Boas-Buck identity: (E_x - n*1)*p(n, x) = (E_x + 1)*Sum_{j=0..n-1} (1/2)*(1 - (-1)^j)*binomial(j+1, (j+1)/2)*p(n-1-j, x), for n >= 0, where E_x = x*d/dx (Euler operator). For the triangle a(n, m) this entails a recurrence for the sequence of column m, given in the formula section. - Wolfdieter Lang, Aug 11 2017

From Roger Ford, Jan 22 2018: (Start)

For row n, the nonzero values represent the odd components (loops) formed by n+1 nonintersecting arches above and below the x-axis with the following constraints: The top has floor((n+3)/2) starting arches at position 1 and the next consecutive odd positions. All other starting top arches are in even positions. The bottom arches are a rainbow of arches. If the component=1 then the arch configuration is a semimeander solution.

Examples: For row 3 {0, 2, 0, 1} there are 3 arch configurations: 2 arch configurations have a component=1; 1 has a component=3. c=components, U=top arch starting in odd position, u=top arch starting in an even position, d=ending top arch:

.

top UuUdUddd c=3 top UdUuUddd c=1 top UdUdUudd c=1

/\ /\

//\\ / \

// \\ / /\ \ /\

// \\ / / \ \ / \

///\ /\\\ /\ / / /\ \ \ /\ /\ / /\ \

\\\ \/ /// \ \ \ \/ / / / \ \ \ \/ / / /

\\\ /// \ \ \ / / / \ \ \ / / /

\\\/// \ \ \/ / / \ \ \/ / /

\\// \ \ / / \ \ / /

\/ \ \/ / \ \/ /

\ / \ /

\/ \/

For row 4 {2, 0, 3, 0, 1} there are 6 arch configurations: 2 have a component=1; 3 have a component=3: 1 has a component=1. (End)