Discussiones Mathematicae Graph Theory 33(1) (2013) 217-229
doi: 10.7151/dmgt.1658

Dedicated to Mieczysław Borowiecki on the occasion of his 70th birthday

[BIBTex] [PDF] [PS]

Sums of powered characteristic roots count distance-independent circular sets

Zdzisław Skupień

AGH Kraków
al. Mickiewicza 30, 30--059 Kraków, Poland


Significant values of a combinatorial count need not fit the recurrence for the count. Consequently, initial values of the count can much outnumber those for the recurrence. So is the case of the count, Gl(n), of distance-l independent sets on the cycle Cn, studied by Comtet for l ≥ 0 and n ≥ 1 [sic]. We prove that values of Gl(n) are nth power sums of the characteristic roots of the corresponding recurrence unless 2 ≤ n ≤ l. Lucas numbers L(n) are thus generalized since L(n) is the count in question if l = 1. Asymptotics of the count for 1 ≤ l ≤ 4 involves the golden ratio (if l = 1) and three of the four smallest Pisot numbers inclusive of the smallest of them, plastic number, if l = 4. It is shown that the transition from a recurrence to an OGF, or back, is best presented in terms of mutually reciprocal (shortly: co-reciprocal) polynomials. Also the power sums of roots (i.e., moments) of a polynomial have the OGF expressed in terms of the co-reciprocal polynomial.

Keywords: distance independent set, Lucas numbers, Pisot numbers, power sums, generating functions, (co-) reciprocal polynomials

2010 Mathematics Subject Classification: 05C69, 05A15, 11B37, 11R06.


[1]G.E. Andrews, A theorem on reciprocal polynomials with applications to permutations and compositions, Amer. Math. Monthly 82 (1975) 830--833, doi: 10.2307/2319803.
[2]C. Berge, Principes de combinatoire (Dunod, Paris, 1968).
[3]M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse, and J.P. Schreiber , Pisot and Salem Numbers (Birkhäuser, Basel, 1992).
[4]L. Comtet, Advanced Combinatorics. The art of Finite and Infinite Expansions (D. Reidel, Dordrecht, 1974).
[5]Ph. Flajolet and R. Sedgewick, Analytic Combinatorics (Cambridge Univ. Press, 2009).
[6]I. Kaplansky, Solution of the ?Probleme des ménages?, Bull. Amer. Math. Soc. 49 (1943) 784--785, doi: 10.1090/S0002-9904-1943-08035-4.
[7]M. Kwaśnik and I. Włoch, The total number of generalized stable sets and kernels of graphs, Ars Combin. 55 (2000) 139--146.
[8]W. Lang, A196837: Ordinary generating functions for sums of powers of the first n positive integers, (2011)
[9]T. Muir, Note on selected combinations, Proc. Roy. Soc. Edinburgh 24 (1901-2) 102--104.
[10]H. Prodinger and R.F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart. 20 (1982) 16--21.
[11]Z. Skupień, On sparse hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles, Electron. Notes Discrete Math. 24 (2006) 231--235, doi: 10.1016/j.endm.2006.06.032.
[12]Z. Skupień, Sparse hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles, Discrete Math. 309 (2009) 6382--6390, doi: 10.1016/j.disc.2008.11.003.
[13]Z. Skupień, Multi-compositions in exponential counting of hypohamiltonian graphs and/or snarks, manuscript {2009}{}} ().
[14]Z. Skupień, Generating Girard-Newton-Waring's moments of mutually reciprocal polynomials, manuscript {2012}{}} ().
[15]N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, OEIS (2007)
[16]R.P. Stanley, Enumerative Combinatorics, vol. 1 (Cambridge Univ. Press, 1997).
[17]Wikipedia, Pisot-Vijayaraghavan number,(2012)
http://en.wikipedia.org/wiki/Pisot-Vijayaraghavan_number (as of 2012.03.30)

Received 11 April 2012
Revised 19 November 2012
Accepted 19 November 2012