cp's OEIS Frontend

T(n,k) is the number of subsets of {1,2,...,n-1} of size k and containing no consecutive integers. Example: T(6,2)=6 because the subsets of size 2 of {1,2,3,4,5} with no consecutive integers are {1,3},{1,4},{1,5},{2,4},{2,5} and {3,5}. Equivalently, T(n,k) is the number of k-matchings of the path graph P_n. - Emeric Deutsch, Dec 10 2003

T(n,k) = number of compositions of n+2 into k+1 parts, all >= 2. Example: T(6,2)=6 because we have (2,2,4),(2,4,2),(4,2,2),(2,3,3),(3,2,3) and (3,3,2). - Emeric Deutsch, Apr 09 2005

Given any recurrence sequence S(k) = x*a(k-1) + a(k-2), starting (1, x, x^2+1, ...); the (k+1)-th term of the series = f(x) in the k-th degree polynomial: (1, (x), (x^2 + 1), (x^3 + 2x), (x^4 + 3x^2 + 1), (x^5 + 4x^3 + 3x), (x^6 + 5x^4 + 6x^2 + 1), ...). Example: let x = 2, then S(k) = 1, 2, 5, 12, 29, 70, 169, ... such that A000129(7) = 169 = f(x), x^6 + 5x^4 + 6x^2 + 1 = (64 + 80 + 24 + 1). - Gary W. Adamson, Apr 16 2008

Row k gives the nonzero coefficients of U(k,x/2) where U is the Chebyshev polynomial of the second kind. For example, row 6 is 1,5,6,1 and U(6,x/2) = x^6 - 5x^4 + 6x^2 - 1. - David Callan, Jul 22 2008

T(n,k) is the number of nodes at level k in the Fibonacci tree f(k-1). The Fibonacci trees f(k) of order k are defined as follows: 1. f(-1) and f(0) each consist of a single node. 2. For k >= 1, to the root of f(k-1), taken as the root of f(k), we attach with a rightmost edge the tree f(k-2). See the Iyer and Reddy references. These trees are not the same as the Fibonacci trees in A180566. Example: T(3,0)=1 and T(3,1)=2 because in f(2) = /\ we have 1 node at level 0 and 2 nodes at level 1. - Emeric Deutsch, Jun 21 2011

Triangle, with zeros omitted, given by (1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2011

Riordan array (1/(1-x),x^2/(1-x). - Philippe Deléham, Dec 12 2011

This sequence is the elements on the rising diagonals of the Pascal triangle, where the sum of the elements in each rising diagonal represents a Fibonacci number. - Mohammad K. Azarian, Mar 08 2012

If we set F(0;x) = 0, F(1;x) = 1, F(n+1;x) = x*F(n;x) + F(n-1;x), then we obtain the sequence of Vieta-Fibonacci polynomials discussed by Gary W. Adamson above. We note that F(n;x) = (-i)^n * U(n;i*x/2), where U denotes the respective Chebyshev polynomial of the second kind (see David Callan's remark above). Let us fix a,b,f(0),f(1) in C, b is not the zero, and set f(n) = a*f(n-1) + b*f(n-2). Then we deduce the relation: f(n) = b^((n-1)/2) * F(n;a/sqrt(b))*f(1) + b^(n/2) * F(n-1;a/sqrt(b))*f(0), where for a given value of the complex root sqrt(b) we set b^(n/2) = (sqrt(b))^n. Moreover, if b=1 then we get f(n+k) + (-1)^k * f(n-k) = L(k;a)*f(n), for every k=0,1,...,n, and where L(0;a)=2, L(1;a)=a, L(n+1;a)=a*L(n;a) + L(n-1;a) are the Vieta-Lucas polynomials. Let us observe that L(n+2;a) = F(n+2;a) + F(n;a), L(m+n;a) = L(m;a)*F(n;a) + L(m-1;a)*F(n-1;a), which implies also L(n+1;a) = a*F(n;a) + 2*F(n-1;a). Further we have L(n;a) = 2*(-i)^n * T(n;i*x/2), where T(n;x) denotes the n-th Chebyshev polynomial of the first kind. For the proofs, other relations and facts - see Witula-Slota's papers. - Roman Witula, Oct 12 2012

The diagonal sums of this triangle are A000930. - John Molokach, Jul 04 2013

Aside from signs and index shift, the coefficients of the characteristic polynomial of the Coxeter adjacency matrix for the Coxeter group A_n related to the Chebyshev polynomial of the second kind (cf. Damianou link p. 19). - Tom Copeland, Oct 11 2014

For a mirrored, shifted version showing the relation of these coefficients to the Pascal triangle, Fibonacci, and other number triangles, see A030528. See also A053122 for a relation to Cartan matrices. - Tom Copeland, Nov 04 2014

For a relation to a formulation for a universal Lie Weyl algebra for su(1,1), see page 16 of Durov et al. - Tom Copeland, Nov 29 2014

A reversed, signed and aerated version is given by A049310, related to Chebyshev polynomials. - Tom Copeland, Dec 06 2015

For n >= 3, the n-th row gives the coefficients of the independence polynomial of the (n-2)-path graph P_{n-2}. - Eric W. Weisstein, Apr 07 2017

For n >= 2, the n-th row gives the coefficients of the matching-generating polynomial of the (n-1)-path graph P_{n-1}. - Eric W. Weisstein, Apr 10 2017

Antidiagonals of the Pascal matrix A007318 read bottom to top. These are also the antidiagonals read from top to bottom of the numerical coefficients of the Maurer-Cartan form matrix of the Leibniz group L^(n)(1,1) presented on p. 9 of the Olver paper), which is generated as exp[c. * M] with (c.)^n = c_n and M the Lie infinitesimal generator A218272. Reverse is A102426. - Tom Copeland, Jul 02 2018

T(n,k) is the number of Markov equivalence classes with skeleton the path on n+1 nodes having exactly k immoralities. See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - Liam Solus, Aug 23 2018

T(n, k) = number of compositions of n+1 into n+1-2*k odd parts. For example, T(6,2) = 6 because 7 = 5+1+1 = 3+3+1 = 3+1+3 = 1+1+5 = 1+3+3 = 1+1+5. - Michael Somos, Sep 19 2019

From Gary W. Adamson, Apr 25 2022: (Start)

Alternate rows can be parsed into those with odd integer coefficients to the right of the leftmost 1, and those with even integer coefficients to the right of the leftmost 1. The first set is shown in A054142 and are characteristic polynomials of submatrices of an infinite tridiagonal matrix (A332602) with all -1's in the super and subdiagonals and (1,2,2,2,...) as the main diagonal. For example, the characteristic equation of the 3 X 3 submatrix (1,-1,0; -1,2,-1; 0,-1,2) is x^3 - 5x^2 + 6x - 1. The roots are the Beraha constants B(7,1) = 3.24697...; B(7,2) = 1.55495...; and B(7,3) = 0.198062.... For n X n matrices of this form, the largest eigenvalue is B(2n+1, 1). The 3 X 3 matrix has an eigenvalue of 3.24697... = B(7,1).

Polynomials with even integer coefficients to the right of the leftmost 1 are in A053123 with roots being the even-indexed Beraha constants. The generating Cartan matrices are those with (2,2,2,...) as the main diagonal and -1's as the sub- and superdiagonals. The largest eigenvalue of n X n matrices of this form are B(2n+2,1). For example, the largest eigenvalue of (2,-1,0; -1,2,-1; 0,-1,2) is 3.414... = B(8,1) = a root to x^3 - 6x^2 + 10x - 4. (End)

T(n,k) is the number of edge covers of P_(n+2) with (n-k) edges. For example, T(6,2)=6 because among edges 1, 2, ..., 7 of P_8, we can eliminate any two non-consecutive edges among 2-6. These numbers can be found using the recurrence relation for the edge cover polynomial of P_n, which is E(P_n,x) = xE(P_(n-1),x)+xE(P_(n-2),x) and E(P_1,x)=0, E(P_2,x)=x (ref. Akbari and Oboudi). - Feryal Alayont, Jun 03 2022

T(n,k) is the number of ways to tile an n-board (an n X 1 array of 1 X 1 cells) using k dominoes and n-2*k squares. - Michael A. Allen, Dec 28 2022

T(n,k) is the number of positive integer sequences (s(1),s(2),...,s(n-2k)) such that s(i) < s(i+1), s(1) is odd, s(n-2k) <= n, and s(i) and s(i+1) have opposite parity (ref. Donnelly, Dunkum, and McCoy). Example: T(6,0)=1 corresponds to 123456; T(6,1)=5 corresponds to 1234, 1236, 1256, 1456, 3456; T(6,2)=6 corresponds to 12, 14, 16, 34, 36; and T(6,3)=1 corresponds to the empty sequence () with length 0. - Molly W. Dunkum, Jun 27 2023

Partial sums of signed sequence is shifted unsigned one: |a(n+2)| = A011655(n+1).

With interpolated zeros, a(n) = sin(5*Pi*n/6 + Pi/3)/sqrt(3) + cos(Pi*n/6 + Pi/6)/sqrt(3); this gives the diagonal sums of the Riordan array (1-x^2, x(1-x^2)). - Paul Barry, Feb 02 2005

From Tom Copeland, Nov 02 2014: (Start)

With a shift and a sign change the o.g.f. of this array becomes the compositional inverse of the shifted Motzkin or Riordan numbers A005043,

(x - x^2) / (1 - x + x^2) = x*(1-x) / (1 - x*(1-x)) = x*(1-x) + [x*(1-x)]^2 + ... . Expanding each term of this series and arranging like powers of x in columns gives skewed rows of the Pascal triangle and reading along the columns gives (mod-signs and indexing) A011973, A169803, and A115139 (see also A091867, A092865, A098925, and A102426 for these term-by-term expansions and A030528). (End)

Also triangle of numbers of n-sequences of 0,1 with k subsequences of consecutive 01 because this number is C(n+1,2*k+1). - Roger Cuculiere (cuculier(AT)imaginet.fr), Nov 16 2002

From Gary W. Adamson, Oct 17 2008: (Start)

Received from Herb Conn:

Let T = tan x, then

tan x = T

tan 2x = 2T / (1 - T^2)

tan 3x = (3T - T^3) / (1 - 3T^2)

tan 4x = (4T - 4T^3) / (1 - 6T^2 + T^4)

tan 5x = (5T - 10T^3 + T^5) / (1 - 10T^2 + 5T^4)

tan 6x = (6T - 20T^3 + 6T^5) / (1 - 15T^2 + 15T^4 - T^6)

tan 7x = (7T - 35T^3 + 21T^5 - T^7) / (1 - 21T^2 + 35T^4 - 7T^6)

tan 8x = (8T - 56T^3 + 56T^5 - 8T^7) / (1 - 28T^2 + 70T^4 - 28T^6 + T^8)

tan 9x = (9T - 84T^3 + 126T^5 - 36T^7 + T^9) / (1 - 36 T^2 + 126T^4 - 84T^6 + 9T^8)

... To get the next one in the series, (tan 10x), for the numerator add:

9....84....126....36....1 previous numerator +

1....36....126....84....9 previous denominator =

10..120....252...120...10 = new numerator

For the denominator add:

......9.....84...126...36...1 = previous numerator +

1....36....126....84....9.... = previous denominator =

1....45....210...210...45...1 = new denominator

...where numerators = A034867, denominators = A034839

(End)

Column k is the sum of columns 2k and 2k+1 of A007318. - Philippe Deléham, Nov 12 2008

Triangle, with zeros omitted, given by (2, -1/2, 1/2, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1/2, -1/2, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2011

The row polynomials N(n,x) = Sum_{k=0..floor((n-1)/2)} T(n-1,k)*x^k, and D(n,x) = Sum_{k=0..floor(n/2)} A034839(n,k)*x^k, n >= 1, satisfy the recurrences N(n,x) = D(n-1,x) + N(n-1,x), D(n,x) = D(n-1,x) + x*N(n-1,x), with inputs N(1,x) = 1 = D(1,x). This is due to the Pascal triangle A007318 recurrence. Q(n,x) := tan(n*x)/tan(x) satisfies the recurrence Q(n,x) = (1 + Q(n-1,x))/(1 - v(x)*Q(n-1,x)) with input Q(1,x) = 1 and v = v(x) := (tan(x))^2. This recurrence is obtained from the addition theorem for tan(n*x) using n = 1 + (n-1). Therefore Q(n,x) = N(n,-v(x))/D(n,-v(x)). This proves the Gary W. Adamson contribution from above. See also A220673. This calculation was motivated by an e-mail of Thomas Olsen. The Oliver/Prodinger and Ma references resort to HAKEM Al Memo 239, Item 16, for the tan(n*x) formula in terms of tan(x). - Wolfdieter Lang, Jan 17 2013

The infinitesimal generator (infinigen) for the Narayana polynomials A090181/A001263 can be formed from the row polynomials P(n,y) of this entry. The resulting matrix is an instance of a matrix representation of the analytic infinigens presented in A145271 for general sets of binomial Sheffer polynomials and in A001263 and A119900 specifically for the Narayana polynomials. Given the column vector of row polynomials V = (1, P(1,x) = 2x, P(2,y) = 3x + x^2, P(3,y) = 4x + 4x^2, ...), form the lower triangular matrix M(n,k) = V(n-k,n-k), i.e., diagonally multiply the matrix with all ones on the diagonal and below by the components of V. Form the matrix MD by multiplying A132440^Transpose = A218272 = D (representing derivation of o.g.f.s) by M, i.e., MD = M*D. The non-vanishing component of the first row of (MD)^n * V / (n+1)! is the n-th Narayana polynomial. - Tom Copeland, Dec 09 2015

The diagonals of this entry are A078812 (also shifted A128908 and unsigned A053122, which are embedded in A030528, A102426, A098925, A109466, A092865). Equivalently, the antidiagonals of A078812 are the rows of A034867. - Tom Copeland, Dec 12 2015

Binomial(n,2k+1) is also the number of permutations avoiding both 132 and 213 with k peaks, i.e., positions with w[i]w[i+2]. - Lara Pudwell, Dec 19 2018

Binomial(n,2k+1) is also the number of permutations avoiding both 123 and 132 with k peaks, i.e., positions with w[i]w[i+2]. - Lara Pudwell, Dec 19 2018

The row polynomial P(n, x) = Sum_{0..floor(n/2)} T(n, k)*x^k appears as numerator polynomial of the diagonal sequence m of triangle A104698 as follows. G(m, x) = P(m, x^2)/(1 - x)^(m+1), for m >= 0. - Wolfdieter Lang, May 14 2025

Number of acyclic orientations of the path graph on n+1 vertices, with k-1 sinks. - Per W. Alexandersson, Aug 15 2025

Entries are Bessel polynomial coefficients. Row sums are A000085. Diagonal sums are A122849. Inverse is A122850. Product of A007318 and A122848 gives A100862.

T(n,k) is the number of self-inverse permutations of {1,2,...,n} having exactly k cycles. - Geoffrey Critzer, May 08 2012

Bessel numbers of the second kind. For relations to the Hermite polynomials and the Catalan (A033184 and A009766) and Fibonacci (A011973, A098925, and A092865) matrices, see Yang and Qiao. - Tom Copeland, Dec 18 2013.

Also the inverse Bell transform of the double factorial of odd numbers Product_{k= 0..n-1} (2*k+1) (A001147). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015

This is a signed version of A011973 (Fibonacci polynomials) with different offset.

The sequence of row lengths is [1,1,2,2,3,3,4,4,5,5,6,6,...] = A008619(n-1), n>=1.

The row sums give the period 6 sequence [1,1,0,-1,-1,0,...] = A010892(n-1), n>=1.

The o.g.f. for the column m sequence (with leading zeros) is ((-1)^m)*x^(2*m+1)/(1-x)^(m+1).

The unsigned row sums give the Fibonacci numbers A000045(n-1), n>=1.

The row polynomial are P(n,x):= Sum_{m=0..ceiling(n/2)-1} a(n,m)*x^m = (sqrt(x)^(n-1))*S(n-1,1/sqrt(x)), n>=1, with Chebyshev's S(n,x) polynomials A049310.

These polynomials appear in the formula 1/c(x)^n = P(n+1,x) - x*P(n,x)*c(x), n>=1, with the o.g.f. c(x):=(1-sqrt(1-4*x))/(2*x) of A000108 (Catalan numbers). See the W. Lang reference, eqs. (1) and (2), p. 408, with P(n,x):=p(-n,x).

These polynomials also appear in the formula c(x)^n = (-P(n-1,x) + P(n,x)*c(x))/x^(n-1), n>=1, with the above given o.g.f. c(x) of A000108 (Catalan numbers). See the W. Lang reference, eq. (1), with P(n,x):=p(-n,x).

With offset n>=0 this array a(n,m) coincides with the row reversed coefficient table of Chebyshev's S-polynomials without interspersed zeros. See A049310 for the S(n,x) coefficient table with increasing powers of x.

The polynomials with this sequence as coefficients form the set of so-called "Catalan polynomials", having arisen from computations in looking at the problem of 'fitting' iterated generating function schemes to the Catalan sequence. A neighboring pair forms the basis of a first-order linear recurrence that generates, through a succession of iterated generating functions (polynomials in Z[x]), a predetermined number of Catalan numbers before 'failing' - see the Clapperton et al. 2008 reference in Utilitas Mathematica, where some of the essential mathematical properties of the Catalan polynomials are also listed (based mainly on existing results for Dickson and Chebyshev polynomials, to which they are related). - Peter J Larcombe, Sep 16 2008

In the Clapperton et al. 2008 Congressus Numerantium paper, a new class of nonlinear identities satisfied by Catalan polynomials are presented. They arise from the algebraic implementation of particular cases of a general root finding formulation due to Householder, of which the classic O(2) Newton-Raphson and O(3) Halley algorithms are special cases. The role of Catalan polynomials in forming Padé approximants to the Catalan sequence o.g.f. is also discussed. - Peter J Larcombe, Nov 02 2008

These polynomials appear in the following statements: (i) P(k+1,x)/P(k+2,x) is the g.f. of all ordered trees (Dyck paths) of height at most k; (ii) x^k/(P(k+1,x)*P(k+2,x)) is the g.f. of all ordered trees (Dyck paths) of height k. See the de Bruijn et al., the Kreweras, the Sedgewick and Flajolet (p. 258), and the Flajolet and Sedgewick (p. 326) references. - Emeric Deutsch, Jun 16 2011

For a mirrored, shifted version showing the relation of these coefficients to the Pascal triangle, Fibonacci, and other number triangles, see A030528. See also A053122 for a relation to Cartan matrices. (Cf. A011973, A169803, A115139, A092865, A098925, and A102426.) - Tom Copeland, Nov 04 2014

M. Sinan Kul, Dec 09 2015, observed that (in a rewritten form) Chebyshev's S polynomials A049310 are given by S(n, x) = Sum_{m=0..floor(n/2)} a(n+1, m)*x^(n-2*m), n >= 0. This formula is well known and can be proved from the S recurrence by induction using the recurrence for the binomial coefficients. - Wolfdieter Lang, Feb 01 2016

These are the coefficients of generalized Fibonacci polynomials (see link bellow). - Rigoberto Florez, Aug 28 2022

Essentially the same as A098925: a(0)=0 followed by A098925. - R. J. Mathar, Aug 30 2008

F(n) + 2x * F(n-1) gives Lucas polynomials (cf. A034807). - Maxim Krikun (krikun(AT)iecn.u-nancy.fr), Jun 24 2007

After the initial 0, these are the nonzero coefficients of the Fibonacci polynomials; see the Mathematica section. - Clark Kimberling, Oct 10 2013

Aside from signs and index shift, the coefficients of the characteristic polynomial of the Coxeter adjacency matrix for the Coxeter group A_n related to the Chebyshev polynomial of the second kind (cf. Damianou link p. 19). - Tom Copeland, Oct 11 2014

Aside from the initial zeros, these are the antidiagonals read from bottom to top of the numerical coefficients of the Maurer-Cartan form matrix of the Leibniz group L^(n)(1,1) presented on p. 9 of the Olver paper, which is generated as exp[c. * M] with (c.)^n = c_n and M the Lie infinitesimal generator A218272. Reverse of A011973. - Tom Copeland, Jul 02 2018

T(n,k) = 0 if k <0 or k > n+1-k.

T(n,k) is the number of binary vectors of length n and weight k containing no pair of adjacent 1's.

Take Pascal's triangle A007318 and push the k-th column downwards by 2k-1 places (k>=1).

Row sums are A000045.

From Emanuele Munarini, May 24 2011: (Start)

Diagonal sums are A000930(n+1).

A sparse subset (or scattered subset) of {1,2,...,n} is a subset never containing two consecutive elements. T(n,k) is the number of sparse subsets of {1,2,...,n} having size k. For instance, for n=4 and k=2 we have the 3 sparse 2-subsets of {1,2,3,4}: 13, 14, 24. (End)

As a triangle, row 2*n-1 consists of the coefficients of Morgan-Voyce polynomial B(n,x), A172431, and row 2*n to the coefficients of Morgan-Voyce polynomial b(n,x), A054142.

Aside from signs and index shift, the coefficients of the characteristic polynomial of the Coxeter adjacency matrix for the Coxeter group A_n related to the Chebyshev polynomial of the second kind (cf. Damianou link p. 19). - Tom Copeland, Oct 11 2014

Antidiagonals of the Pascal matrix A007318 read bottom to top, omitting the first antidiagonal. These are also the antidiagonals (omitting the first antidiagonal) read from top to bottom of the numerical coefficients of the Maurer-Cartan form matrix of the Leibniz group L^(n)(1,1) presented on p. 9 of the Olver paper, which is generated as exp[c. * M] with (c.)^n = c_n and M the Lie infinitesimal generator A218272. Reverse is embedded in A102426. - Tom Copeland, Jul 02 2018

Triangle, with zeros omitted, given by (0, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (-1, 0, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 26 2011

Aside from signs and index shift, the coefficients of the characteristic polynomial of the Coxeter adjacency matrix for the Coxeter group A_n related to the Chebyshev polynomial of the second kind (cf. Damianou link p. 19). - Tom Copeland, Oct 11 2014