Decomposition Based Generating Functions for Sequences

Jackson, D. M. ; Aleliunas, R.

Canadian journal of mathematics, Tome 29 (1977) no. 5, pp. 971-1009

Résumé

Numerous combinatorial enumeration problems may be reduced to equivalent problems of enumerating sequences with prescribed restrictions. For example, the expression, given by Tutte [38], for the number of planar maps may be derived (see Cori and Richard [12]) by essentially a sequence enumeration technique. The correspondence between a set of configurations which are to be enumerated and an appropriate set of sequences is often complicated. Indeed, the existence of such a correspondence has occasionally only been discovered fortuitously by observing the equality of two counting series (see, for example, Klarner [25]).

Détail

DOI : 10.4153/CJM-1977-098-3

Bibliographie

[1] 1. Abramson, M. and Moser, W. O. J., Permutations without rising or falling w-sequences, Ann. Math. Statist. 38 (1967), 1245–1254. Google Scholar

[2] 2. André, D., Développements des secx et de tangx, C. R. Acad. Sci. Paris, 88 (1879), 965–967. Google Scholar

[3] 3. André, D. Mémoire sur le nombre des permutations alternées, J. Math. 7 (1881), 167. Google Scholar

[4] 4. Andrews, G. E., The theory of composition (II): Simon Newcomb's problem, Utilitas Math. 7 (1975), 33–54. Google Scholar

[5] 5. Andrews, G. E. The theory of compositions (I): The ordered factorizations of n and a conjecture of C. Long, Can. Math. Bull. 18 (1975), 479–484. Google Scholar

[6] 6. Bender, E. A. and Goldman, J. R., Enumerative uses of generating functions, Indiana University Math. J. 20 (1971), 753–764. Google Scholar

[7] 7. Carlitz, L., Enumeration of sequences by rises and falls: a refinement of the Simon Newcomb problem, Duke J. Math. 39 (1972), 267–280. Google Scholar

[8] 8. Carlitz, L., Roselle, D. P. and Scoville, R. A., Permutations and sequences with repetitions by number of increases, J. Combinatorial Theory, 3 (1966), 350–374. Google Scholar

[9] 9. Carlitz, L., Enumeration of up-down sequences, Discrete Math. 4 (1973), 273–286. Google Scholar

[10] 10. Carlitz, L. and Scoville, R., Generalized Eulerian numbers: combinatorial applications, J. reine angew. Math. 265 (1975), 110–133. Google Scholar

[11] 11. Carlitz, L. and Vaughan, T., Enumeration of sequences of given specification according to rises, falls and maxima, Discrete Math. 8 (1974), 147–167. Google Scholar

[12] 12. Cori, R. and Richard, J., Enumeration des graphes planaires a l'aide des series formelle en variables non commutatives, Discrete Math. 2 (1972), 115–162. Google Scholar

[13] 13. Davenport, H. and Shinzel, A., A combinatorial problem connected with differential equations, Amer. J. Math. 87 (1965), 684–694. Google Scholar

[14] 14. Dillon, J. F. and Roselle, D. P., Simon NewcomVs problem, SIAM J. Appl. Math. 17 (1969), 1086–1093. Google Scholar

[15] 15. Eifler, L. Q., K. B. Reid and Roselle, D. P., Sequences with adjacent elements unequal, Aeq. Math. 6 (1971), 256–262. Google Scholar

[16] 16. Even, S. and Gillis, J., Derangements and Laguerre polynomials, Math. Proc. Cambridge Philos. Soc. 79 (1976), 135–143. Google Scholar

[17] 17. Erdôs, P. and Szekeres, G., A combinatorial problem in geometry, Composite Mathematica, 2 (1935), 463–470. Google Scholar

[18] 18. Foata, D. and Schùtzenberger, M. P., Théorie géométrique des polynômes Euleriens, Lecture notes in Mathematics, 138 (Springer Verlag, New York, 1970). Google Scholar

[19] 19. Henle, M., Dissection of generating functions, Studies in Appl. Math. 51 (1972), 397–410. Google Scholar

[20] 20. Jackson, D. M., The combinatorial interpretation of the Jacobi identity from Lie algebras, J. Combinatorial Theory (A), to appear. Google Scholar

[21] 21. Jackson, D. M. The unification of certain enumeration problems for sequences, J. Combinatorial Theory (A) 22 (1976), 92–96. Google Scholar

[22] 22. Jackson, D. M. Laguerre polynomials and derangements, Math. Proc. Cambridge Philos. Soc. 80 (1976), 213–214. Google Scholar

[23] 23. Jackson, D. M. and Reilly, J. W., Permutations with a prescribed number of p-runs, Ars Combinatoria 1 (1976), 297–305. Google Scholar

[24] 24. Klarner, D. A., The number of hamiltonian paths and cycles on k-coloured graphs, Kon. Nederl. Akad. Wetesch. 72 (1969), 384–387. Google Scholar

[25] 25. Klarner, D. A. Correspondences between plane trees and binary sequences, J. Combinatorial Theory 9 (1970), 401–411. Google Scholar

[26] 26. Long, C. T., Addition theorems for sets of integers, Pacific J. Math. 23 (1967), 107–112. Google Scholar

[27] 27.. On a problem in partial difference equations, Canad. Math. Bull. 13 (1970), 333–335. Google Scholar

[28] 28. Moser, W. O. J. and Abramson, M., Generalisations of Terquem's problem, J. Combinatorial Theory, 7 (1969), 171–180. Google Scholar

[29] 29. Mullin, R. C. and Rota, G. C., On the foundations of combinatorial theory, III; Theory of binomial enumeration, in Graph theory and its applications (Academic Press, New York, 1970), 167–213. Google Scholar

[30] 30. Riordan, J., Permutations without C-sequences, Bull. Amer. Math. Soc. 51 (1945), 745–748. Google Scholar

[31] 31. Riordan, J. An introduction to combinatorial analysis (Wiley, New York, 1958). Google Scholar

[32] 32. Roselle, D. P., Graphs, quasisymmetry and permutations with restricted positions, Duke Math. J. 41 (1974), 41–50. Google Scholar

[33] 33. Schenstead, C., Longest increasing and decreasing subsequences, Can. J. Math. 13 (1961), 179–191. Google Scholar

[34] 34. Smirnov, N. V., Sarmanov, O. V. and Zaharov, V. K., A local limit theorem for the number of transitions in a Markov chain and its applications (Russian). Dokl, Akad. Nauk. SSR, 167 (1966), 1238-1241. (English translation: Soviet Math. Dokl. 7 (1966), 563–566.) Google Scholar

[35] 35. Stanley, R. P., Theory and application of plane partitions, II, Studies in Appl. Math. 50 (1967), 259–279. Google Scholar

[36] 36. Stanley, R. P. Binomial posets, Mbbius inversion and permutation enumeration, J. Combinatorial Theory (A) 20 (1967), 336–356. Google Scholar

[37] 37. Szegô, G., Tiber gewisse Potenzreihen mit lauter positiven Koeffizienten, Math. Z. 87 (1933), 674–688. Google Scholar

[38] 38. Tutte, W. T., A census of planar maps, Canad. J. Math. 15 (1963), 249–271. Google Scholar

[39] 39. Whitworth, W. A., Choice and chance (Deighton Bell, Cambridge, 1901). Google Scholar