cp's OEIS Frontend

Also the q-Stirling2 numbers at q = -1. - Peter Luschny, Mar 09 2020

Row sums give the Fibonacci sequence. So do the alternating row sums.

Triangle of coefficients of polynomials defined by p(-1,x) = p(0,x) = 1, p(n, x) = x*p(n-1, x) + p(n-2, x), for n >= 1. - Benoit Cloitre, May 08 2005 [rewritten with correct offset. - Wolfdieter Lang, Feb 18 2020]

Another version of triangle in A103631. - Philippe Deléham, Jan 01 2009

The T(n,k) coefficients appear in appendix 2 of Parks's remarkable article "A new proof of the Routh-Hurwitz stability criterion using the second method of Liapunov" if we assume that the b(n) coefficients are all equal to 1 and ignore the first column. The complete version of this triangle including the first column is A103631. - Johannes W. Meijer, Aug 11 2011

Signed ++--++..., the roots are chaotic using f(x) --> x^2 - 2 with cycle lengths shown in A003558 by n-th rows. Example: given row 3, x^3 + x^2 - 2x - 1; the roots are (a = 1.24697, ...; b = -0.445041, ...; c = -1.802937, ...). Then (say using seed b with x^2 - 2) we obtain the trajectory -0.445041, ... -> -1.80193, ... -> 1.24697, ...; matching the entry "3" in A003558(3). - Gary W. Adamson, Sep 06 2011

From Gary W. Adamson, Aug 25 2019: (Start)

Roots to the polynomials and terms in A003558 can all be obtained from the numbers below using a doubling series mod N procedure as follows: (more than one row may result). Any row ends when the trajectory produces a term already used. Then try the next higher odd term not used as the leftmost term, then repeat.

For example, for N = 11, we get: (1, 2, 4, 3, 5), showing that when confronted with two choices after the 4: (8 and -3), pick the smaller (abs) term, = 3. Then for the next row pick 7 (not used) and repeat the algorithm; succeeding only if the trajectory produces new terms. But 7 is also (-4) mod 11 and 4 was used. Therefore what I call the "r-t table" (for roots trajectory) has only one row: (1, 2, 4, 3, 5). Conjecture: The numbers of terms in the first row is equal to A003558 corresponding to N, i.e., 5 in this case with period 2.

Now for the roots to the polynomials. Pick N = 7. The polynomial is x^3 - x^2 - 2x + 1 = 0, with roots 1.8019..., -1.2469... and 0.445... corresponding to 2*cos(j*Pi/N), N = 7, and j = (1, 2, and 3). The terms (1, 2, 3) are the r-t terms for N = 7. For 11, the r-t terms are (1, 2, 4, 3, 5). This implies that given any roots of the corresponding polynomial, they are cyclic using f(x) --> x^2 - 2 with cycle lengths shown in A003558. The terms thus generated are 2*cos(j*Pi), with j = (1, 2, 4, 3, 5). Check: Begin with 2*j*Pi/N, with j = 1 (1.9189...). The other trajectory terms are: --> 1.6825..., --> 0.83083..., -1.3097...; 545...; (a 5 period and cyclic since we can begin with any of the constants). The r-t table for odd N begins as follows:

3...............1

5...............1, 2

7...............1, 2, 3

9...............1, 2, 4

...............3 (singleton terms reduce to "1") (9 has two rows)

11...............1, 2, 4, 3, 5

13...............1, 2, 4, 5, 3, 6

15...............1, 2, 4, 7

................3, 6 (dividing through by the gcd gives (1, 2))

................5. (singleton terms reduce to "1")

The result is that 15 has 3 factors (since 3 rows), and the values of those factors are the previous terms "N", corresponding to the r-t terms in each row. Thus, the first row is new, the second (1, 2), corresponds to N = 5, and the "1" in row 3 corresponds to N = 3. The factors are those values apart from 15 and 1. Note that all of the unreduced r-t terms in all rows for N form a complete set of the terms 1 through (N-1)/2 without duplication. (End)

From Gary W. Adamson, Sep 30 2019: (Start)

The 3 factors of the 7th degree polynomial for 15: (x^7 - x^6 - 6x^5 + 5x^4 + 10x^3 - 6x^2 - 4x + 1) can be determined by getting the roots for 2*cos(j*Pi/1), j = (1, 2, 4, 7) and finding the corresponding polynomial, which is x^4 + x^3 - 4x^2 - 4x + 1. This is the minimal polynomial for N = 15 as shown in Table 2, p. 46 of (Lang). The degree of this polynomial is 4, corresponding to the entry in A003558 for 15, = 4. The trajectories (3, 6) and (5) are j values for 2*cos(j*Pi/15) which are roots to x^2 - x - 1 (relating to the pentagon), and (x - 1), relating to the triangle. (End)

From Gary W. Adamson, Aug 21 2019: (Start)

Matrices M of the form: (1's in the main diagonal, -1's in the subdiagonal, and the rest zeros) are chaotic if we replace (f(x) --> x^2 - 2) with f(x) --> M^2 - 2I, where I is the Identity matrix [1, 0, 0; 0, 1, 0; 0, 0, 1]. For example, with the 3 X 3 matrix M: [0, 0, 1; 0, 1, -1; 1, -1, 0]; the f(x) trajectory is:

....M^2 - 2I: [-1, -1, 0; -1, 0, -1; 0, -1, 0], then for the latter,

....M^2 - 2I: [0, 1, 1; 1, 0, 0; 1, 0, -1]. The cycle ends with period 3 since the next matrix is (-1) * the seed matrix. As in the case with f(x) --> x^2 - 2, the eigenvalues of the 3 chaotic matrices are (abs) 1.24697, 0.44504... and 1.80193, ... Also, the characteristic equations of the 3 matrices are the same as or variants of row 4 of the triangle below: (x^3 + x - 2x - 1) with different signs. (End)

Received from Herb Conn, Jan 2004: (Start)

Let x = 2*cos(2A) (A = Angle); then

sin(A)/sin A = 1

sin(3A)/sin A = x + 1

sin(5A)/sin A = x^2 + x - 1

sin(7A)/sin A = x^3 + x - 2x - 1

sin(9A)/sin A = x^4 + x^3 - 3x^2 - 2x + 1

... (signed ++--++...). (End)

Or Pascal's triangle (A007318) with duplicated diagonals. Also triangle of coefficients of polynomials defined by P_0(x) = 1 and for n>=1, P_n(x) = F_n(x) + F_(n+1)(x), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} C(n-i-1,i)*x^(n-2*i-1). - Vladimir Shevelev, Apr 12 2012

The matrix inverse is given by

1;

1, 1;

0, -1, 1;

0, 1, -2, 1;

0, 0, 1, -2, 1;

0, 0, -1, 3, -3, 1;

0, 0, 0, -1, 3, -3, 1;

0, 0, 0, 1, -4, 6, -4, 1;

0, 0, 0, 0, 1, -4, 6, -4, 1;

... apart from signs the same as A124645. - R. J. Mathar, Mar 12 2013

The coefficients of the matrix inverse are apparently given by T^(-1)(n,k) = (-1)^n*A157783(n,k). - R. J. Mathar, Mar 12 2013

There are several versions of Lucas and Fibonacci polynomials in this database. Our naming follows the convention of calling polynomials after the values of the polynomials at x = 1. This assumes a regular sequence of polynomials, that is, a sequence of polynomials where degree(p(n)) = n. This view makes the coefficients of the polynomials (the terms of a row) a refinement of the values at the unity.

A remarkable property of the polynomials under consideration is that they are dual in this respect. This means they give the Lucas numbers at x = 1 and the Fibonacci numbers at x = -1 (except for the sign). See the example section.

The Pell numbers and the dual Pell numbers are also values of the polynomials, at the points x = -1/2 and x = 1/2 (up to the normalization factor 2^n). This suggests a harmonized terminology: To call 2^n*P(n, -1/2) = 1, 0, 1, 2, 5, ... the Pell numbers (A000129) and 2^n*P(n, 1/2) = 1, 4, 9, 22, ... the dual Pell numbers (A048654).

Based on our naming convention one could call A162515 (without the prepended 0) the Fibonacci polynomials. In the definition above only the initial values would change to: T(n, k) = k + 1 for k < 1. To extend this line of thought we introduce A374438 as the third triangle of this family.

The triangle is closely related to the qStirling2 numbers at q = -1. For the definition of these numbers see A333143. This relates the triangle to A065941 and A103631.

Row sums = A135922 starting with offset 1: (1, 2, 6, 26, 158, 1330, ...).

This triangle is the q-analog of A008277 (Stirling numbers of the 2nd kind) for q=2 (see Cai et al. link). - Werner Schulte, Apr 04 2019

T(n,k) is the number of naturally labeled posets on [n] with height at most one containing exactly k minimal elements. See link by David Bevan and others below. - Geoffrey Critzer, May 03 2025

This triangle appears to be the q-analog of A008275 (Stirling numbers of the first kind) for q=2. However, A333142 has a similar definition.

Row sums of unsigned triangle are A006125 with offset 1.

|T(n,k)| is the number of descent free digraphs on [n] containing exactly k source nodes. A descent in a digraph is a pair of vertices s->t such that s>t. A descent free digraph is necessarily acyclic. A source in an acyclic digraph is a node with indegree 0. - Geoffrey Critzer, Mar 05 2025

We aim at a q-generalization of the Comtet-Lehmer numbers A354794, which are the case q = 1. Here we consider the case q = 2. The generalization is based on the qStirling numbers, for qStirling1 see A342186 and for qStirling2 see A139382. The general construction is as follows:

Let q <> 1 be a fixed integer and f_q(k) = (q^k - 1)/(q - 1) for k >= 0. Define triangle M(q; n, k) for 0 <= k <= n by M(q; n, 0) = 0^n for n >= 0, and M(q; n, k) = 0 for k > n, and M(q; n, k) = M(q; n-1, k-1) + M(q; n-1, k) * f_q(k) for 0 < k <= n. Then M(q; n, n) = 1 for n >= 0 and the matrix inverse I_q = M_q^(-1) exists. Next define the triangle T(q; n, k) for 0 <= k <= n by T(q; n, 0) = 0^n for n >= 0 and T(q; n, k) = Sum_{i=0..n-k} I(q; n-k, i) * M(q; n-1+i, n-1) for 0 < k <= n. Take account of lim_{q->1} (q^n - 1)/(q - 1) = n for n >= 0.

Conjecture: T(q; n+1, 1) = Sum_{i=0..n} I(q; n, i) * M(q; n+i, n) = (f_q(n))^n = ((q^n - 1)/(q - 1))^n for n >= 0.

Conjecture: T(q; n, k) = (Sum_{i=0..n-k} (-1)^i * q-binomial(n-1-i, k-1) * binomial(n-1, i) * q^((n-k)*(n-k-i))) / (q - 1)^(n-k) for 0 < k <= n.

The idea behind the Fibonacci and Lucas sequences is simple: Put the '2' in the middle of a band and place a '1' to the left and a '-1' to the right. Now add the sum of the two immediate numbers with higher indexes on the left side and on the right side the sum of the two with lower indexes. Schematically, after a few steps, it looks like this:

..., 18, 11, 7, 4, 3, 1, <-- + [2] + --> -1, 1, 0, 1, 1, 2, 3, 5, ...

This generates the Lucas sequence on the left (with a descending index) and the Fibonacci sequence on the right (with an ascending index). The fact that the first two terms (-1, 1) of the Fibonacci sequence were 'forgotten' in A000045 is from our point of view only a difference in the choice of the offset of the central term. Our choice is, in any case, consistent with Knuth's continuation of the Fibonacci numbers into the negative range (A039834).

This construction is to be captured in a family of polynomials. The idea is that the two sequences are the values of the polynomials at the points x = -1 and x = 1. This continues from A374439. Here we choose signed coefficients and shift the powers up by one.

This approach also reveals that another important sequence follows the same logic: the Pell numbers (A000129). These, and their dual counterpart A048654, are interpolated by the polynomials at the points x = 1/2 and x = -1/2 (up to the normalization factor 2^n). The table in the example section gives an overview.

The formal representation is based on the qStirling2 numbers in the version defined in SageMath (see also A065941 and A333143).