DMGT

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

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

Sums of powered characteristic roots count distance-independent circular sets

Zdzisław Skupień

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

Abstract

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, G_l(n), of distance-l independent sets on the cycle C_n, studied by Comtet for l ≥ 0 and n ≥ 1 [sic]. We prove that values of G_l(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.

References

[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) http://www-itp.particle.uni-karlsruhe.de/~wl/.
[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) www.research.att.com/~njas/sequences/.
[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