

A034807


Triangle T(n,k) of coefficients of Lucas (or Cardan) polynomials.


53



2, 1, 1, 2, 1, 3, 1, 4, 2, 1, 5, 5, 1, 6, 9, 2, 1, 7, 14, 7, 1, 8, 20, 16, 2, 1, 9, 27, 30, 9, 1, 10, 35, 50, 25, 2, 1, 11, 44, 77, 55, 11, 1, 12, 54, 112, 105, 36, 2, 1, 13, 65, 156, 182, 91, 13, 1, 14, 77, 210, 294, 196, 49, 2, 1, 15, 90, 275, 450, 378, 140, 15, 1, 16, 104
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

These polynomials arise in the following setup. Suppose G and H are power series satisfying G + H = G*H = 1/x. Then G^n + H^n = (1/x^n)*L_n(x).
Apart from signs, triangle of coefficients when 2*cos(nt) is expanded in terms of x = 2*cos(t). For example, 2*cos(2t) = x^2  2, 2*cos(3t) = x^3  3x and 2*cos(4t) = x^4  4x^2 + 2.  Anthony C Robin, Jun 02 2004
Triangle of coefficients of expansion of Z_{nk} in terms of Z_k.
T(n,k) = number of kmatchings of the cycle C_n (n > 1). Example: T(6,2)=9 because the 2matchings of the hexagon with edges a, b, c, d, e, f are ac, ad, ae, bd, be, bf, ce, cf and df.  Emeric Deutsch, Dec 25 2004
An example for the first comment: G=c(x), H=1/(x*c(x)) with c(x) the o.g.f. Catalan numbers A000108: (x*c(x))^n + (1/c(x))^n = L(n,x)= Sum_{k=0..floor(n/2)} T(n,k)*(x)^k.
This triangle also supplies the absolute values of the coefficients in the multiplication formulas for the Lucas numbers A000032.
This sequence is related to rhombus substitution tilings. A signed version of it (see A132460), formed as a triangle with interlaced zeros extending each row to n terms, begins as
{2}
{1, 0}
{1, 0, 2}
{1, 0, 3, 0}
{1, 0, 4, 0, 2}
{1, 0, 5, 0, 5, 0}
....
For the n X n tridiagonal unitprimitive matrix G_(n,1) (n >= 2) (see the L. E. Jeffery link below), defined by
G_(n,1) =
(0 1 0 ... 0)
(1 0 1 0 ... 0)
(0 1 0 1 0 ... 0)
...
(0 ... 0 1 0 1)
(0 ... 0 2 0),
Row n (i.e., {T(n,k)}, k=0..n) of the signed table gives the coefficients of its characteristic function: c_n(x) = Sum_{k=0..n} T(n,k)*x^(nk) = 0. For example, let n=3. Then
G_(3,1) =
(0 1 0)
(1 0 1)
(0 2 0),
and row 3 of the table is {1,0,3,0}. Hence c_3(x) = x^3  3*x = 0. G_(n,1) has n distinct eigenvalues (the solutions of c_n(x) = 0), given by w_j = 2*cos((2*j1)*Pi/(2*n)), j=1..n. (End)
For n > 0, T(n,k) is the number of ksubsets of {1,2,...,n} which contain neither consecutive integers nor both 1 and n. Equivalently, T(n,k) is the number of ksubsets without neighbors of a set of n points on a circle.  José H. Nieto S., Jan 17 2012
The number of necklaces of k black and n  k white beads with no adjacent black beads (Kaplansky 1943). Coefficients of the Dickson polynomials D(n,x,a).  Peter Bala, Mar 09 2014
See also A113279 for another connection to symmetric and Faber polynomials.
The difference of consecutive rows gives the previous row shifted.
For relations among the characteristic polynomials of Cartan matrices of the Coxeter root groups, Chebyshev polynomials, cyclotomic polynomials, and the polynomials of this entry, see Damianou (p. 12, 20, and 21) and Damianou and Evripidou (p. 7). (End)
Diagonals are related to multiplicities of eigenvalues of the Laplacian on hyperspheres through A029635.  Tom Copeland, Jan 10 2016
For n>=3, also the independence and matching polynomials of the ncycle graph C_n. See also A284966.  Eric W. Weisstein, Apr 06 2017
Apparently, with the rows aerated and then the 2s on the diagonal removed, this matrix becomes the reverse, or mirror, of unsigned A117179. See also A114525  Tom Copeland, May 30 2017
Briggs's (1633) table with an additional column of 2s on the right can be used to generate this table. See p. 69 of the Newton reference.  Tom Copeland, Jun 03 2017
For n>3 and k>0, T(n,k) equals the number of Markov equivalence classes with skeleton the cycle on n nodes having exactly k immoralities. See Theorem 2.1 of the article by A. Radhakrishnan et al. below.
For n>2 odd and r = floor(n/2)1, the nth row is the coefficient vector of the Ehrhart h*polynomial of the rstable (n,2)hypersimplex. See Theorem 4.14 in the article by B. Braun and L. Solus below.
(End)
Conjecture: If a(n) = H(a,b,c,d,n) is a secondorder linear recurrence with constant coefficients defined as a(0) = a, a(1)= b, a(n) = c*a(n1) + d*a(n2) then a(m*n) = H(a, H(a,b,c,d,m), Sum_{k=0..floor(m/2)} T(m,k)*c^(m2*k)*d^k, (1)^(m+1)*d^m, n) (Wolfdieter Lang).  Gary Detlefs, Feb 06 2023
For the proof of the preceding conjecture see the Detlefs and Lang link. There also proofs for several properties of this table are found.  Wolfdieter Lang, Apr 25 2023


REFERENCES

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 148.
C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
Thomas Koshy, Fibonacci and Lucas Numbers with Applications. New York, etc.: John Wiley & Sons, 2001. (Chapter 13, "Pascallike Triangles," is devoted to the present triangle.)
The Royal Society Newton Tercentenary Celebrations, Cambridge Univ. Press, 1947.


LINKS

J. Kappraff and G. Adamson, Polygons and Chaos, 5th Interdispl Symm. Congress and Exh. Jul 814, Sydney, 2001  [with commercial popups].


FORMULA

Lucas polynomial coefficients: 1, n, n*(n3)/2!, n*(n4)*(n5)/3!, n*(n5)*(n6)*(n7)/4!,  n*(n6)*(n7)*(n8)*(n9)/5!, ...  Herb Conn and Gary W. Adamson, May 28 2003
T(n, k) = T(n1, k) + T(n2, k1), n>1. T(n, 0) = 1, n>0. T(n, k) = binomial(nk, k) + binomial(nk1, k1) = n*binomial(nk1, k1)/k, 0 <= 2*k <= n except T(0, 0) = 2.  Michael Somos, Apr 02 1999
T(n,k) = (n*(n1k)!)/(k!*(n2*k)!), n>0, k>=0.  Alexander Elkins (alexander_elkins(AT)hotmail.com), Jun 09 2007
L_n(x) = ((x+sqrt(x^2+4))/2)^n + (((x+sqrt(x^2+4))/2))^(n). See metallic means.  William Krier, Sep 01 2023


EXAMPLE

I have seen two versions of these polynomials: One version begins L_0 = 2, L_1 = 1, L_2 = 1 + 2*x, L_3 = 1 + 3*x, L_4 = 1 + 4*x + 2*x^2, L_5 = 1 + 5*x + 5*x^2, L_6 = 1 + 6*x + 9*x^2 + 2*x^3, L_7 = 1 + 7*x + 14*x^2 + 7*x^3, L_8 = 1 + 8*x + 20*x^2 + 16*x^3 + 2*x^4, L_9 = 1 + 9*x + 27*x^2 + 30*x^3 + 9*x^4, ...
The other version (probably the more official one) begins L_0(x) = 2, L_1(x) = x, L_2(x) = 2 + x^2, L_3(x) = 3*x + x^3, L_4(x) = 2 + 4*x^2 + x^4, L_5(x) = 5*x + 5*x^3 + x^5, L_6(x) = 2 + 9*x^2 + 6*x^4 + x^6, L_7(x) = 7*x + 14*x^3 + 7*x^5 + x^7, L_8(x) = 2 + 16*x^2 + 20*x^4 + 8*x^6 + x^8, L_9(x) = 9*x + 30*x^3 + 27*x^5 + 9*x^7 + x^9.
Triangle begins:
2;
1;
1, 2;
1, 3;
1, 4, 2;
1, 5, 5;
1, 6, 9, 2;
1, 7, 14, 7;
1, 8, 20, 16, 2;
1, 9, 27, 30, 9;
1, 10, 35, 50, 25, 2;
1, 11, 44, 77, 55, 11;
1, 12, 54, 112, 105, 36, 2;
1, 13, 65, 156, 182, 91, 13;
1, 14, 77, 210, 294, 196, 49, 2;
1, 15, 90, 275, 450, 378, 140, 15;
(End)


MAPLE

T:= proc(n, k) if n=0 and k=0 then 2 elif k>floor(n/2) then 0 else n*binomial(nk, k)/(nk) fi end: for n from 0 to 15 do seq(T(n, k), k=0..floor(n/2)) od; # yields sequence in triangular form # Emeric Deutsch, Dec 25 2004


MATHEMATICA

t[0, 0] = 2; t[n_, k_] := Binomial[nk, k] + Binomial[nk1, k1]; Table[t[n, k], {n, 0, 16}, {k, 0, Floor[n/2]}] // Flatten (* JeanFrançois Alcover, Dec 30 2013 *)
CoefficientList[Table[x^(n/2) LucasL[n, 1/Sqrt[x]], {n, 0, 15}], x] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)
Table[Select[Reverse[CoefficientList[LucasL[n, x], x]], 0 < # &], {n, 0, 16}] // Flatten (* Robert G. Wilson v, May 03 2017 *)
CoefficientList[FunctionExpand @ Table[2 (x)^(n/2) Cos[n ArcSec[2 Sqrt[x]]], {n, 0, 15}], x] // Flatten (* Eric W. Weisstein, Apr 03 2018 *)
CoefficientList[Table[2 (x)^(n/2) ChebyshevT[n, 1/(2 Sqrt[x])], {n, 0, 15}], x] // Flatten (* Eric W. Weisstein, Apr 03 2018 *)


PROG

(PARI) {T(n, k) = if( k<0  2*k>n, 0, binomial(nk, k) + binomial(nk1, k1) + (n==0))}; /* Michael Somos, Jul 15 2003 */


CROSSREFS



KEYWORD

tabf,easy,nonn


AUTHOR



EXTENSIONS



STATUS

approved



