|
%I #216 Sep 25 2023 20:01:49
%S 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,
%T 10,35,50,25,2,1,11,44,77,55,11,1,12,54,112,105,36,2,1,13,65,156,182,
%U 91,13,1,14,77,210,294,196,49,2,1,15,90,275,450,378,140,15,1,16,104
%N Triangle T(n,k) of coefficients of Lucas (or Cardan) polynomials.
%C 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).
%C 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
%C Triangle of coefficients of expansion of Z_{nk} in terms of Z_k.
%C Row n has 1 + floor(n/2) terms. - _Emeric Deutsch_, Dec 25 2004
%C T(n,k) = number of k-matchings of the cycle C_n (n > 1). Example: T(6,2)=9 because the 2-matchings 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
%C 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.
%C This triangle also supplies the absolute values of the coefficients in the multiplication formulas for the Lucas numbers A000032.
%C From _L. Edson Jeffery_, Mar 19 2011: (Start)
%C 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
%C {2}
%C {1, 0}
%C {1, 0, -2}
%C {1, 0, -3, 0}
%C {1, 0, -4, 0, 2}
%C {1, 0, -5, 0, 5, 0}
%C ....
%C For the n X n tridiagonal unit-primitive matrix G_(n,1) (n >= 2) (see the L. E. Jeffery link below), defined by
%C G_(n,1) =
%C (0 1 0 ... 0)
%C (1 0 1 0 ... 0)
%C (0 1 0 1 0 ... 0)
%C ...
%C (0 ... 0 1 0 1)
%C (0 ... 0 2 0),
%C 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^(n-k) = 0. For example, let n=3. Then
%C G_(3,1) =
%C (0 1 0)
%C (1 0 1)
%C (0 2 0),
%C 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*j-1)*Pi/(2*n)), j=1..n. (End)
%C For n > 0, T(n,k) is the number of k-subsets of {1,2,...,n} which contain neither consecutive integers nor both 1 and n. Equivalently, T(n,k) is the number of k-subsets without neighbors of a set of n points on a circle. - _José H. Nieto S._, Jan 17 2012
%C With the first column omitted, this gives A157000. - _Philippe Deléham_, Mar 17 2013
%C 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
%C From _Tom Copeland_, Nov 07 2015: (Start)
%C This triangular array is composed of interleaved rows of reversed, unsigned A127677 (cf. A156308, A217476, A263916) and reversed A111125 (cf. A127672).
%C See also A113279 for another connection to symmetric and Faber polynomials.
%C The difference of consecutive rows gives the previous row shifted.
%C 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)
%C Diagonals are related to multiplicities of eigenvalues of the Laplacian on hyperspheres through A029635. - _Tom Copeland_, Jan 10 2016
%C For n>=3, also the independence and matching polynomials of the n-cycle graph C_n. See also A284966. - _Eric W. Weisstein_, Apr 06 2017
%C 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
%C 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
%C From _Liam Solus_, Aug 23 2018: (Start)
%C 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.
%C For n>2 odd and r = floor(n/2)-1, the n-th row is the coefficient vector of the Ehrhart h*-polynomial of the r-stable (n,2)-hypersimplex. See Theorem 4.14 in the article by B. Braun and L. Solus below.
%C (End)
%C Conjecture: If a(n) = H(a,b,c,d,n) is a second-order linear recurrence with constant coefficients defined as a(0) = a, a(1)= b, a(n) = c*a(n-1) + d*a(n-2) then a(m*n) = H(a, H(a,b,c,d,m), Sum_{k=0..floor(m/2)} T(m,k)*c^(m-2*k)*d^k, (-1)^(m+1)*d^m, n) (Wolfdieter Lang). - _Gary Detlefs_, Feb 06 2023
%C 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
%D A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 148.
%D C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
%D Thomas Koshy, Fibonacci and Lucas Numbers with Applications. New York, etc.: John Wiley & Sons, 2001. (Chapter 13, "Pascal-like Triangles," is devoted to the present triangle.)
%D The Royal Society Newton Tercentenary Celebrations, Cambridge Univ. Press, 1947.
%H T. D. Noe, <a href="/A034807/b034807.txt">Rows n = 0..100 of triangle, flattened</a>
%H Moussa Benoumhani, <a href="http://www.cs.uwaterloo.ca/journals/JIS//VOL6/Benoumhani/benoumhani8.html">A Sequence of Binomial Coefficients Related to Lucas and Fibonacci Numbers</a>, J. Integer Seqs., Vol. 6, 2003.
%H B. Braun and L. Solus, <a href="https://arxiv.org/abs/1408.4713">r-stable hypersimplices</a>, Journal of Combinatorial Theory, Series A 157 (2018): 349-388.
%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2015/10/12/the-elliptic-lie-triad-kdv-and-ricattt-equations-infinigens-and-elliptic-genera/">Addendum to Elliptic Lie Triad</a>
%H P. Damianou, <a href="http://arxiv.org/abs/1110.6620">On the characteristic polynomials of Cartan matrices and Chebyshev polynomials</a>, arXiv preprint arXiv:1110.6620 [math.RT], 2014.
%H P. Damianou and C. Evripidou, <a href="http://arxiv.org/abs/1409.3956">Characteristic and Coxeter polynomials for affine Lie algebras</a>, arXiv preprint arXiv:1409.3956 [math.RT], 2014.
%H Gary Detlefs and Wolfdieter Lang, <a href="https://arxiv.org/abs/2304.12937">Improved Formula for the Multi-Section of the Linear Three-Term Rcurrence Sequence<</a>, arXiv:2304.12937[nath.CO], 2023.
%H Joseph Doolittle, Lukas Katthän, Benjamin Nill, and Francisco Santos, <a href="https://arxiv.org/abs/2103.14925">Empty simplices of large width</a>, arXiv:2103.14925 [math.CO], 2021.
%H S. Falcon, <a href="http://scik.org/index.php/jmcs/article/view/102">On the Lucas triangle and its relationship with the k-Lucas numbers</a>, Journal of Mathematical and Computational Science, 2 (2012), No. 3, 425-434.
%H E. J. Farrell, <a href="http://dx.doi.org/10.1016/0095-8956(79)90070-4">An introduction to matching polynomials</a>, J. Combin. Theory B 27 (1) (1979), 75-86, Table 2.
%H Heidi Goodson, <a href="https://arxiv.org/abs/1901.08653">An Identity for Vertically Aligned Entries in Pascal's Triangle</a>, arXiv:1901.08653 [math.CO], 2019.
%H G. Hetyei, <a href="http://arxiv.org/abs/1211.2494">Hurwitzian continued fractions containing a repeated constant and an arithmetic progression</a>, arXiv preprint arXiv:1211.2494 [math.CO], 2012. - From _N. J. A. Sloane_, Jan 02 2013
%H L. E. Jeffery, <a href="https://oeis.org/wiki/User:L._Edson_Jeffery/Unit-Primitive_Matrices">Unit-primitive matrices</a>
%H I. Kaplansky, <a href="http://projecteuclid.org/euclid.bams/1183505432">Solution of the "probleme des menages"</a>, Bull. Amer. Math. Soc. 49, (1943). 784-785.
%H J. Kappraff and G. Adamson, <a href="http://vismath7.tripod.com/proceedings/kappraff.htm">Polygons and Chaos</a>, 5th Interdispl Symm. Congress and Exh. Jul 8-14, Sydney, 2001 - [with commercial pop-ups].
%H Emrah Kilic and Elif Tan Kilic, <a href="http://ekilic.etu.edu.tr/list/62Subseq.pdf">Some subsequences of the generalized Fibonacci and Lucas sequences</a>, Preprint, 2011.
%H Eric Marberg, <a href="https://arxiv.org/abs/1709.07446">On some actions of the 0-Hecke monoids of affine symmetric groups</a>, arXiv:1709.07996 [math.CO], 2017.
%H T. J. Osler, <a href="http://www.jstor.org/stable/2691150">Cardan polynomials and the reduction of radicals</a>, Math. Mag., 74 (No. 1, 2001), 26-32.
%H A. Radhakrishnan, L. Solus, and C. Uhler, <a href="https://arxiv.org/abs/1706.06091">Counting Markov equivalence classes for DAG models on trees</a>, Discrete Applied Mathematics 244 (2018): 170-185.
%H Lorenzo Venturello, <a href="https://arxiv.org/abs/2106.05051">Koszul Gorenstein algebras from Cohen-Macaulay simplicial complexes</a>, arXiv:2106.05051 [math.AC], 2021.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LucasPolynomial.html">Lucas Polynomial</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching-GeneratingPolynomial.html">Matching-Generating Polynomial</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Dickson_polynomial">Dickson polynomial</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Metallic_mean">Metallic mean</a>.
%F Row sums = A000032. T(2n, n-1) = A000290(n), T(2n+1, n-1) = A000330(n), T(2n, n-2) = A002415(n). T(n, k) = A029635(n-k, k), if n>0. - _Michael Somos_, Apr 02 1999
%F Lucas polynomial coefficients: 1, -n, n*(n-3)/2!, -n*(n-4)*(n-5)/3!, n*(n-5)*(n-6)*(n-7)/4!, - n*(n-6)*(n-7)*(n-8)*(n-9)/5!, ... - _Herb Conn_ and _Gary W. Adamson_, May 28 2003
%F G.f.: (2-x)/(1-x-x^2*y). - _Vladeta Jovovic_, May 31 2003
%F T(n, k) = T(n-1, k) + T(n-2, k-1), n>1. T(n, 0) = 1, n>0. T(n, k) = binomial(n-k, k) + binomial(n-k-1, k-1) = n*binomial(n-k-1, k-1)/k, 0 <= 2*k <= n except T(0, 0) = 2. - _Michael Somos_, Apr 02 1999
%F T(n,k) = (n*(n-1-k)!)/(k!*(n-2*k)!), n>0, k>=0. - Alexander Elkins (alexander_elkins(AT)hotmail.com), Jun 09 2007
%F O.g.f.: 2-(2xt+1)xt/(-t+xt+(xt)^2). (Cf. A113279.) - _Tom Copeland_, Nov 07 2015
%F T(n,k) = A011973(n-1,k) + A011973(n-3,k-1) = A011973(n,k) - A011973(n-4,k-2) except for T(0,0)=T(2,1)=2. - _Xiangyu Chen_, Dec 24 2020
%F 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
%e 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, ...
%e 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.
%e From _John Blythe Dobson_, Oct 11 2007: (Start)
%e Triangle begins:
%e 2;
%e 1;
%e 1, 2;
%e 1, 3;
%e 1, 4, 2;
%e 1, 5, 5;
%e 1, 6, 9, 2;
%e 1, 7, 14, 7;
%e 1, 8, 20, 16, 2;
%e 1, 9, 27, 30, 9;
%e 1, 10, 35, 50, 25, 2;
%e 1, 11, 44, 77, 55, 11;
%e 1, 12, 54, 112, 105, 36, 2;
%e 1, 13, 65, 156, 182, 91, 13;
%e 1, 14, 77, 210, 294, 196, 49, 2;
%e 1, 15, 90, 275, 450, 378, 140, 15;
%e (End)
%p T:= proc(n,k) if n=0 and k=0 then 2 elif k>floor(n/2) then 0 else n*binomial(n-k,k)/(n-k) 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
%t t[0, 0] = 2; t[n_, k_] := Binomial[n-k, k] + Binomial[n-k-1, k-1]; Table[t[n, k], {n, 0, 16}, {k, 0, Floor[n/2]}] // Flatten (* _Jean-François Alcover_, Dec 30 2013 *)
%t CoefficientList[Table[x^(n/2) LucasL[n, 1/Sqrt[x]], {n, 0, 15}], x] // Flatten (* _Eric W. Weisstein_, Apr 06 2017 *)
%t Table[Select[Reverse[CoefficientList[LucasL[n, x], x]], 0 < # &], {n, 0, 16}] // Flatten (* _Robert G. Wilson v_, May 03 2017 *)
%t CoefficientList[FunctionExpand @ Table[2 (-x)^(n/2) Cos[n ArcSec[2 Sqrt[-x]]], {n, 0, 15}], x] // Flatten (* _Eric W. Weisstein_, Apr 03 2018 *)
%t CoefficientList[Table[2 (-x)^(n/2) ChebyshevT[n, 1/(2 Sqrt[-x])], {n, 0, 15}], x] // Flatten (* _Eric W. Weisstein_, Apr 03 2018 *)
%o (PARI) {T(n, k) = if( k<0 || 2*k>n, 0, binomial(n-k, k) + binomial(n-k-1, k-1) + (n==0))}; /* _Michael Somos_, Jul 15 2003 */
%Y Cf. A029635, A061896, A111125, A113279, A114525, A127672, A127677, A156308, A217476, A263916.
%Y Cf. A117179.
%K tabf,easy,nonn
%O 0,1
%A _N. J. A. Sloane_
%E Improved description, more terms, etc., from _Michael Somos_
|
