login
Triangle read by rows, giving the numbers T(n,m) = binomial(n+1, m+1); or, Pascal's triangle A007318 with its left-hand edge removed.
48

%I #184 Oct 14 2024 12:17:39

%S 1,2,1,3,3,1,4,6,4,1,5,10,10,5,1,6,15,20,15,6,1,7,21,35,35,21,7,1,8,

%T 28,56,70,56,28,8,1,9,36,84,126,126,84,36,9,1,10,45,120,210,252,210,

%U 120,45,10,1,11,55,165,330,462,462,330,165,55,11,1,12,66,220,495,792,924,792

%N Triangle read by rows, giving the numbers T(n,m) = binomial(n+1, m+1); or, Pascal's triangle A007318 with its left-hand edge removed.

%C T(n,m) is the number of m-faces of a regular n-simplex.

%C An n-simplex is the n-dimensional analog of a triangle. Specifically, a simplex is the convex hull of a set of (n + 1) affinely independent points in some Euclidean space of dimension n or higher, i.e., a set of points such that no m-plane contains more than (m + 1) of them. Such points are said to be in general position.

%C Reversing the rows gives A074909, which as a linear sequence is essentially the same as this.

%C From _Tom Copeland_, Dec 07 2007: (Start)

%C T(n,k) * (k+1)! = A068424. The comment on permuted words in A068424 shows that T is related to combinations of letters defined by connectivity of regular polytope simplexes.

%C If T is the diagonally-shifted Pascal matrix, binomial(n+m, k+m), for m=1, then T is a fundamental type of matrix that is discussed in A133314 and the following hold.

%C The infinitesimal matrix generator is given by A132681, so T = LM(1) of A132681 with inverse LM(-1).

%C With a(k) = (-x)^k / k!, T * a = [ Laguerre(n,x,1) ], a vector array with index n for the Laguerre polynomials of order 1. Other formulas for the action of T are given in A132681.

%C T(n,k) = (1/n!) (D_x)^n (D_t)^k Gf(x,t) evaluated at x=t=0 with Gf(x,t) = exp[ t * x/(1-x) ] / (1-x)^2.

%C [O.g.f. for T ] = 1 / { [ 1 - t * x/(1-x) ] * (1-x)^2 }. [ O.g.f. for row sums ] = 1 / { (1-x) * (1-2x) }, giving A000225 (without a leading zero) for the row sums. Alternating sign row sums are all 1. [Sign correction noted by _Vincent J. Matsko_, Jul 19 2015]

%C O.g.f. for row polynomials = [ (1+q)**(n+1) - 1 ] / [ (1+q) -1 ] = A(1,n+1,q) on page 15 of reference on Grassmann cells in A008292. (End)

%C Given matrices A and B with A(n,k) = T(n,k)*a(n-k) and B(n,k) = T(n,k)*b(n-k), then A*B = C where C(n,k) = T(n,k)*[a(.)+b(.)]^(n-k), umbrally. The e.g.f. for the row polynomials of A is {(a+t) exp[(a+t)x] - a exp(a x)}/t, umbrally. - _Tom Copeland_, Aug 21 2008

%C A007318*A097806 as infinite lower triangular matrices. - _Philippe Deléham_, Feb 08 2009

%C Riordan array (1/(1-x)^2, x/(1-x)). - _Philippe Deléham_, Feb 22 2012

%C The elements of the matrix inverse are T^(-1)(n,k)=(-1)^(n+k)*T(n,k). - _R. J. Mathar_, Mar 12 2013

%C Relation to K-theory: T acting on the column vector (-0,d,-d^2,d^3,...) generates the Euler classes for a hypersurface of degree d in CP^n. Cf. Dugger p. 168 and also A104712, A111492, and A238363. - _Tom Copeland_, Apr 11 2014

%C Number of walks of length p>0 between any two distinct vertices of the complete graph K_(n+2) is W(n+2,p)=(-1)^(p-1)*Sum_{k=0..p-1} T(p-1,k)*(-n-2)^k = ((n+1)^p - (-1)^p)/(n+2) = (-1)^(p-1)*Sum_{k=0..p-1} (-n-1)^k. This is equal to (-1)^(p-1)*Phi(p,-n-1), where Phi is the cyclotomic polynomial when p is an odd prime. For K_3, see A001045; for K_4, A015518; for K_5, A015521; for K_6, A015531; for K_7, A015540. - _Tom Copeland_, Apr 14 2014

%C Consider the transformation 1 + x + x^2 + x^3 + ... + x^n = A_0*(x-1)^0 + A_1*(x-1)^1 + A_2*(x-1)^2 + ... + A_n*(x-1)^n. This sequence gives A_0, ..., A_n as the entries in the n-th row of this triangle, starting at n = 0. - _Derek Orr_, Oct 14 2014

%C See A074909 for associations among this array, the Bernoulli polynomials and their umbral compositional inverses, and the face polynomials of permutahedra and their duals (cf. A019538). - _Tom Copeland_, Nov 14 2014

%C From _Wolfdieter Lang_, Dec 10 2015: (Start)

%C A(r, n) = T(n+r-2, r-1) = risefac(n,r)/r! = binomial(n+r-1, r), for n >= 1 and r >= 1, gives the array with the number of independent components of a symmetric tensors of rank r (number of indices) and dimension n (indices run from 1 to n). Here risefac(n, k) is the rising factorial.

%C As(r, n) = T(n+1, r+1) = fallfac(n, r)/r! = binomial(n, r), r >= 1 and n >= 1 (with the triangle entries T(n, k) = 0 for n < k) gives the array with the number of independent components of an antisymmetric tensor of rank r and dimension n. Here fallfac is the falling factorial. (End)

%C The h-vectors associated to these f-vectors are given by A000012 regarded as a lower triangular matrix. Read as bivariate polynomials, the h-polynomials are the complete homogeneous symmetric polynomials in two variables, found in the compositional inverse of an e.g.f. for A008292, the h-vectors of the permutahedra. - _Tom Copeland_, Jan 10 2017

%C For a correlation between the states of a quantum system and the combinatorics of the n-simplex, see Boya and Dixit. - _Tom Copeland_, Jul 24 2017

%H G. C. Greubel, <a href="/A135278/b135278.txt">Table of n, a(n) for the first 101 rows, flattened</a>

%H Paul Barry, <a href="https://arxiv.org/abs/1805.02274">On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays</a>, arXiv:1805.02274 [math.CO], 2018.

%H L. Boya and K. Dixit, <a href="https://arxiv.org/abs/0808.1930">Geometry of density states</a>, arXiv:808.1930 [quant-phy], 2017.

%H V. Buchstaber, <a href="http://www.mathnet.or.kr/mathnet/thesis_file/kaist-book-updated.pdf">Lectures on Toric Topology</a>, Trends in Mathematics - New Series, Information Center for Mathematical Sciences, Vol. 10, No. 1, 2008. p. 7.

%H Tom Copeland, <a href="http://mathoverflow.net/questions/82560/cyclotomic-polynomials-in-combinatorics">Cyclotomic polynomials in combinatorics</a>

%H Tom Copeland, <a href="https://tcjpn.files.wordpress.com">Goin' with the Flow: Logarithm of the Derivative Operator</a> Part VI on simplices

%H D. Dugger, <a href="http://math.uoregon.edu/~ddugger/kgeom.pdf">A Geometric Introduction to K-Theory</a> [From _Tom Copeland_, Apr 11 2014]

%H Atli Fannar Franklín, <a href="https://arxiv.org/abs/2410.07467">Pattern avoidance enumerated by inversions</a>, arXiv:2410.07467 [math.CO], 2024. See pp. 2, 12.

%H Atli Fannar Franklín, Anders Claesson, Christian Bean, Henning Úlfarsson, and Jay Pantone, <a href="https://arxiv.org/abs/2406.16403">Restricted Permutations Enumerated by Inversions</a>, arXiv:2406.16403 [cs.DM], 2024. See p. 4.

%H B. Grünbaum and G. C. Shephard, <a href="http://dx.doi.org/10.1112/blms/1.3.257">Convex polytopes</a>, Bull. London Math. Soc. (1969) 1 (3): 257-300.

%H G. Hetyei, <a href="http://arxiv.org/abs/0909.4352">Meixner polynomials of the second kind and quantum algebras representing su(1,1)</a>, arXiv preprint arXiv:0909.4352 [math.QA], 2009, p. 4 (Added by _Tom Copeland_, Oct 01 2015).

%H Justin Hughes, <a href="http://www.groupsstandrews.org/2013/slides/Hughes.pdf ">Representations Arising from an Action on D-neighborhoods of Cayley Graphs</a>, 2013; slides from a talk.

%H Wolfdieter Lang, <a href="https://arxiv.org/abs/1708.01421">On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles</a>, arXiv:1708.01421 [math.NT], August 2017.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Simplex">Simplex</a>

%F T(n, k) = Sum_{j=k..n} binomial(j,k) = binomial(n+1, k+1), n >= k >= 0, else 0. (Partial sum of column k of A007318 (Pascal), or summation on the upper binomial index (Graham et al. (GKP), eq. (5.10). For the GKP reference see A007318.) - _Wolfdieter Lang_, Aug 22 2012

%F E.g.f.: 1/x*((1 + x)*exp(t*(1 + x)) - exp(t)) = 1 + (2 + x)*t + (3 + 3*x + x^2)*t^2/2! + .... The infinitesimal generator for this triangle has the sequence [2,3,4,...] on the main subdiagonal and 0's elsewhere. - _Peter Bala_, Jul 16 2013

%F T(n,k) = 2*T(n-1,k) + T(n-1,k-1) - T(n-2,k) - T(n-2,k-1), T(0,0)=1, T(1,0)=2, T(1,1)=1, T(n,k)=0 if k<0 or if k>n. - _Philippe Deléham_, Dec 27 2013

%F T(n,k) = A193862(n,k)/2^k. - _Philippe Deléham_, Jan 29 2014

%F G.f.: 1/((1-x)*(1-x-x*y)). - _Philippe Deléham_, Mar 13 2014

%F From _Tom Copeland_, Mar 26 2014: (Start)

%F [From Copeland's 2007 and 2008 comments]

%F A) O.g.f.: 1 / { [ 1 - t * x/(1-x) ] * (1-x)^2 } (same as Deleham's).

%F B) The infinitesimal generator for T is given in A132681 with m=1 (same as Bala's), which makes connections to the ubiquitous associated Laguerre polynomials of integer orders, for this case the Laguerre polynomials of order one L(n,-t,1).

%F C) O.g.f. of row e.g.f.s: Sum_{n>=0} L(n,-t,1) x^n = exp[t*x/(1-x)]/(1-x)^2 = 1 + (2+t)x + (3+3*t+t^2/2!)x^2 + (4+6*t+4*t^2/2!+t^3/3!)x^3+ ... .

%F D) E.g.f. of row o.g.f.s: ((1+t)*exp((1+t)*x)-exp(x))/t (same as Bala's).

%F E) E.g.f. for T(n,k)*a(n-k): {(a+t) exp[(a+t)x] - a exp(a x)}/t, umbrally. For example, for a(k)=2^k, the e.g.f. for the row o.g.f.s is {(2+t) exp[(2+t)x] - 2 exp(2x)}/t.

%F (End)

%F From _Tom Copeland_, Apr 28 2014: (Start)

%F With different indexing

%F A) O.g.f. by row: [(1+t)^n-1]/t.

%F B) O.g.f. of row o.g.f.s: {1/[1-(1+t)*x] - 1/(1-x)}/t.

%F C) E.g.f. of row o.g.f.s: {exp[(1+t)*x]-exp(x)}/t.

%F These generating functions are related to row e.g.f.s of A111492. (End)

%F From _Tom Copeland_, Sep 17 2014: (Start)

%F A) U(x,s,t)= x^2/[(1-t*x)(1-(s+t)x)] = Sum_{n >= 0} F(n,s,t)x^(n+2) is a generating function for bivariate row polynomials of T, e.g., F(2,s,t)= s^2 + 3s*t + 3t^2 (Buchstaber, 2008).

%F B) dU/dt=x^2 dU/dx with U(x,s,0)= x^2/(1-s*x) (Buchstaber, 2008).

%F C) U(x,s,t) = exp(t*x^2*d/dx)U(x,s,0) = U(x/(1-t*x),s,0).

%F D) U(x,s,t) = Sum[n >= 0, (t*x)^n L(n,-:xD:,-1)] U(x,s,0), where (:xD:)^k=x^k*(d/dx)^k and L(n,x,-1) are the Laguerre polynomials of order -1, related to normalized Lah numbers. (End)

%F E.g.f. satisfies the differential equation d/dt(e.g.f.(x,t)) = (x+1)*e.g.f.(x,t) + exp(t). - _Vincent J. Matsko_, Jul 18 2015

%F The e.g.f. of the Norlund generalized Bernoulli (Appell) polynomials of order m, NB(n,x;m), is given by exponentiation of the e.g.f. of the Bernoulli numbers, i.e., multiple binomial self-convolutions of the Bernoulli numbers, through the e.g.f. exp[NB(.,x;m)t] = (t/(e^t - 1))^(m+1) * e^(xt). Norlund gave the relation to the factorials (x-1)!/(x-1-n)! = (x-1) ... (x-n) = NB(n,x;n), so T(n,m) = NB(m+1,n+2;m+1)/(m+1)!. - _Tom Copeland_, Oct 01 2015

%F From _Wolfdieter Lang_, Nov 08 2018: (Start)

%F Recurrences from the A- and Z- sequences for the Riordan triangle (see the W. Lang link under A006232 with references), which are A(n) = A019590(n+1), [1, 1, repeat (0)] and Z(n) = (-1)^(n+1)*A054977(n), [2, repeat(-1, 1)]:

%F T(0, 0) = 1, T(n, k) = 0 for n < k, and T(n, 0) = Sum_{j=0..n-1} Z(j)*T(n-1, j), for n >= 1, and T(n, k) = T(n-1, k-1) + T(n-1, k), for n >= m >= 1.

%F Boas-Buck recurrence for columns (see the Aug 10 2017 remark in A036521 also for references):

%F T(n, k) = ((2 + k)/(n - k))*Sum_{j=k..n-1} T(j, k), for n >= 1, k = 0, 1, ..., n-1, and input T(n, n) = 1, for n >= 0, (the BB-sequences are alpha(n) = 2 and beta(n) = 1). (End)

%F T(n, k) = [x^k] Sum_{j=0..n} (x+1)^j. - _Peter Luschny_, Jul 09 2019

%e The triangle T(n, k) begins:

%e n\k 0 1 2 3 4 5 6 7 8 9 10 11 ...

%e 0: 1

%e 1: 2 1

%e 2: 3 3 1

%e 3: 4 6 4 1

%e 4: 5 10 10 5 1

%e 5: 6 15 20 15 6 1

%e 6: 7 21 35 35 21 7 1

%e 7: 8 28 56 70 56 28 8 1

%e 8: 9 36 84 126 126 84 36 9 1

%e 9: 10 45 120 210 252 210 120 45 10 1

%e 10: 11 55 165 330 462 462 330 165 55 11 1

%e 11: 12 66 220 495 792 924 792 495 220 66 12 1

%e ... reformatted by _Wolfdieter Lang_, Mar 23 2015

%e Production matrix begins

%e 2 1

%e -1 1 1

%e 1 0 1 1

%e -1 0 0 1 1

%e 1 0 0 0 1 1

%e -1 0 0 0 0 1 1

%e 1 0 0 0 0 0 1 1

%e -1 0 0 0 0 0 0 1 1

%e 1 0 0 0 0 0 0 0 1 1

%e - _Philippe Deléham_, Jan 29 2014

%e From _Wolfdieter Lang_, Nov 08 2018: (Start)

%e Recurrence [_Philippe Deléham_]: T(7, 3) = 2*35 + 35 - 15 - 20 = 70.

%e Recurrence from Riordan A- and Z-sequences: [1,1,repeat(0)] and [2, repeat(-1, +1)]: From Z: T(5, 0) = 2*5 - 10 + 10 - 5 + 1 = 6. From A: T(7, 3) = 35 + 35 = 70.

%e Boas-Buck column k=3 recurrence: T(7, 3) = (5/4)*(1 + 5 + 15 + 35) = 70. (End)

%p for i from 0 to 12 do seq(binomial(i, j)*1^(i-j), j = 1 .. i) od;

%t Flatten[Table[CoefficientList[D[1/x ((x + 1) Exp[(x + 1) z] - Exp[z]), {z, k}] /. z -> 0, x], {k, 0, 11}]]

%t CoefficientList[CoefficientList[Series[1/((1 - x)*(1 - x - x*y)), {x, 0, 10}, {y, 0, 10}], x], y] // Flatten (* _G. C. Greubel_, Nov 22 2017 *)

%o (PARI) for(n=0, 20, for(k=0, n, print1(1/k!*sum(i=0, n, (prod(j=0, k-1, i-j))), ", "))) \\ _Derek Orr_, Oct 14 2014

%o (Sage)

%o Trow = lambda n: sum((x+1)^j for j in (0..n)).list()

%o for n in (0..10): print(Trow(n)) # _Peter Luschny_, Jul 09 2019

%Y Cf. A007318, A014410, A228196.

%Y Cf. Column sequences: A000027, A000217, A000292, A000332, A000389, A000579 - A000582, A001287, A001288, A010965 - A011001, A017713 - A017764.

%Y Cf. A000012, A008292.

%K easy,nonn,tabl

%O 0,2

%A _Zerinvary Lajos_, Dec 02 2007

%E Edited by _Tom Copeland_ and _N. J. A. Sloane_, Dec 11 2007