

A034807


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


52



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.
Row n has 1 + floor(n/2) terms.  Emeric Deutsch, Dec 25 2004
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.
From L. Edson Jeffery, Mar 19 2011: (Start)
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
With the first column omitted, this gives A157000.  Philippe Deléham, Mar 17 2013
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
From Tom Copeland, Nov 07 2015: (Start)
This triangular array is composed of interleaved rows of reversed, unsigned A127677 (cf. A156308, A217476, A263916) and reversed A111125 (cf. A127672).
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
From Liam Solus, Aug 23 2018: (Start)
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)


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

T. D. Noe, Rows n = 0..100 of triangle, flattened
Moussa Benoumhani, A Sequence of Binomial Coefficients Related to Lucas and Fibonacci Numbers, J. Integer Seqs., Vol. 6, 2003.
B. Braun and L. Solus, rstable hypersimplices, Journal of Combinatorial Theory, Series A 157 (2018): 349388.
Tom Copeland, Addendum to Elliptic Lie Triad
P. Damianou, On the characteristic polynomials of Cartan matrices and Chebyshev polynomials, arXiv preprint arXiv:1110.6620 [math.RT], 2014.
P. Damianou and C. Evripidou, Characteristic and Coxeter polynomials for affine Lie algebras, arXiv preprint arXiv:1409.3956 [math.RT], 2014.
Joseph Doolittle, Lukas Katthän, Benjamin Nill, and Francisco Santos, Empty simplices of large width, arXiv:2103.14925 [math.CO], 2021.
S. Falcon, On the Lucas triangle and its relationship with the kLucas numbers, Journal of Mathematical and Computational Science, 2 (2012), No. 3, 425434.
E. J. Farrell, An introduction to matching polynomials, J. Combin. Theory B 27 (1) (1979), 7586, Table 2.
Heidi Goodson, An Identity for Vertically Aligned Entries in Pascal's Triangle, arXiv:1901.08653 [math.CO], 2019.
G. Hetyei, Hurwitzian continued fractions containing a repeated constant and an arithmetic progression, arXiv preprint arXiv:1211.2494 [math.CO], 2012.  From N. J. A. Sloane, Jan 02 2013
L. E. Jeffery, Unitprimitive matrices
I. Kaplansky, Solution of the "probleme des menages", Bull. Amer. Math. Soc. 49, (1943). 784785.
J. Kappraff and G. Adamson, Polygons and Chaos, 5th Interdispl Symm. Congress and Exh. Jul 814, Sydney, 2001  [with commercial popups].
Emrah Kilic and Elif Tan Kilic, Some subsequences of the generalized Fibonacci and Lucas sequences, Preprint, 2011.
Eric Marberg, On some actions of the 0Hecke monoids of affine symmetric groups, arXiv:1709.07996 [math.CO], 2017.
T. J. Osler, Cardan polynomials and the reduction of radicals, Math. Mag., 74 (No. 1, 2001), 2632.
A. Radhakrishnan, L. Solus, and C. Uhler, Counting Markov equivalence classes for DAG models on trees, Discrete Applied Mathematics 244 (2018): 170185.
Lorenzo Venturello, Koszul Gorenstein algebras from CohenMacaulay simplicial complexes, arXiv:2106.05051 [math.AC], 2021.
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Lucas Polynomial
Eric Weisstein's World of Mathematics, MatchingGenerating Polynomial
Wikipedia, Dickson polynomial


FORMULA

Row sums = A000032. T(2n, n1) = A000290(n), T(2n+1, n1) = A000330(n), T(2n, n2) = A002415(n). T(n, k) = A029635(nk, k), if n>0.  Michael Somos, Apr 02 1999
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
G.f.: (2x)/(1xx^2*y).  Vladeta Jovovic, May 31 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
O.g.f.: 2(2xt+1)xt/(t+xt+(xt)^2). (Cf. A113279.)  Tom Copeland, Nov 07 2015
T(n,k) = A011973(n1,k) + A011973(n3,k1) = A011973(n,k)  A011973(n4,k2) except for T(0,0)=T(2,1)=2.  Xiangyu Chen, Dec 24 2020


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, L5 = x^5  5x^3 + 5x = 1, 5, 5 = 1, n, n*(n3)/2.
From John Blythe Dobson, Oct 11 2007: (Start)
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

Cf. A029635, A061896, A111125, A113279, A114525, A127672, A127677, A156308, A217476, A263916.
Cf. A117179.
Sequence in context: A213235 A113279 A213234 * A275111 A182961 A339814
Adjacent sequences: A034804 A034805 A034806 * A034808 A034809 A034810


KEYWORD

tabf,easy,nonn


AUTHOR

N. J. A. Sloane


EXTENSIONS

Improved description, more terms, etc., from Michael Somos


STATUS

approved



