Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets

Zdzisław Skupień

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 217-229
  • ISSN: 2083-5892

Abstract

top
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: coreciprocal) polynomials. Also the power sums of roots (i.e., moments) of a polynomial have the OGF expressed in terms of the co-reciprocal polynomial.

How to cite

top

Zdzisław Skupień. "Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets." Discussiones Mathematicae Graph Theory 33.1 (2013): 217-229. <http://eudml.org/doc/268282>.

@article{ZdzisławSkupień2013,
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, 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: coreciprocal) polynomials. Also the power sums of roots (i.e., moments) of a polynomial have the OGF expressed in terms of the co-reciprocal polynomial.},
author = {Zdzisław Skupień},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance independent set; Lucas numbers; Pisot numbers; power sums; generating functions; (co-) reciprocal polynomials; co-reciprocal polynomials},
language = {eng},
number = {1},
pages = {217-229},
title = {Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets},
url = {http://eudml.org/doc/268282},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Zdzisław Skupień
TI - Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 217
EP - 229
AB - 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: coreciprocal) polynomials. Also the power sums of roots (i.e., moments) of a polynomial have the OGF expressed in terms of the co-reciprocal polynomial.
LA - eng
KW - distance independent set; Lucas numbers; Pisot numbers; power sums; generating functions; (co-) reciprocal polynomials; co-reciprocal polynomials
UR - http://eudml.org/doc/268282
ER -

References

top
  1. [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[Crossref] 
  2. [2] C. Berge, Principes de combinatoire (Dunod, Paris, 1968). (English transl.: Principles of Combinatorics (Acad. Press, New York and London, 1971). Zbl0227.05001
  3. [3] M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse, and J.P. Schreiber, Pisot and Salem Numbers (Birkhauser, Basel, 1992).[WoS] 
  4. [4] L. Comtet, Advanced Combinatorics. The art of Finite and Infinite Expansions (D. Reidel, Dordrecht, 1974). (French original: Analyse combinatoire, vol. I, II (Presses Univ. France, Paris, 1970). 
  5. [5] Ph. Flajolet and R. Sedgewick, Analytic Combinatorics (Cambridge Univ. Press, 2009). http://algo.inria.fr/flajolet/Publications/books.html Zbl1165.05001
  6. [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[Crossref] Zbl0060.02904
  7. [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. [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. [9] T. Muir, Note on selected combinations, Proc. Roy. Soc. Edinburgh 24 (1901-2) 102-104. Zbl33.0229.01
  10. [10] H. Prodinger and R.F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart. 20 (1982) 16-21. Zbl0475.05046
  11. [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[Crossref] Zbl1202.05085
  12. [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[WoS][Crossref] Zbl1184.05078
  13. [13] Z. Skupień, Multi-compositions in exponential counting of hypohamiltonian graphs and/or snarks, manuscript (2009). 
  14. [14] Z. Skupień, Generating Girard-Newton-Waring’s moments of mutually reciprocal polynomials, manuscript (2012). 
  15. [15] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, OEIS (2007). www.research.att.com/~njas/sequences/ Zbl1159.11327
  16. [16] R.P. Stanley, Enumerative Combinatorics, vol. 1 (Cambridge Univ. Press, 1997). doi:10.1017/CBO9780511805967[Crossref] Zbl0889.05001
  17. [17] Wikipedia, Pisot-Vijayaraghavan number, (2012). http://en.wikipedia.org/wiki/Pisot-Vijayaraghavan_number (as of 2012.03.30) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.