Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T01:00:34.741Z Has data issue: false hasContentIssue false
  • English
  • Français

Decomposition Based Generating Functions for Sequences

Published online by Cambridge University Press:  20 November 2018

D. M. Jackson  and
R. Aleliunas
D. M. Jackson
Affiliation:
University of Waterloo, Waterloo, Ontario
R. Aleliunas
Affiliation:
University of Waterloo, Waterloo, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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]).

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 29 , Issue 5 , 01 October 1977 , pp. 971 - 1009
Copyright
Copyright © Canadian Mathematical Society 1977

References

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. André, D., Développements des secx et de tangx, C. R. Acad. Sci. Paris, 88 (1879), 965–967.Google Scholar
3. André, D. Mémoire sur le nombre des permutations alternées, J. Math. 7 (1881), 167.Google Scholar
4. Andrews, G. E., The theory of composition (II): Simon Newcomb's problem, Utilitas Math. 7 (1975), 33–54.Google Scholar
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. Bender, E. A. and Goldman, J. R., Enumerative uses of generating functions, Indiana University Math. J. 20 (1971), 753–764.Google Scholar
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. 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. Carlitz, L., Enumeration of up-down sequences, Discrete Math. 4 (1973), 273–286.Google Scholar
10. Carlitz, L. and Scoville, R., Generalized Eulerian numbers: combinatorial applications, J. reine angew. Math. 265 (1975), 110–133.Google Scholar
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. 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. Davenport, H. and Shinzel, A., A combinatorial problem connected with differential equations, Amer. J. Math. 87 (1965), 684–694.Google Scholar
14. Dillon, J. F. and Roselle, D. P., Simon NewcomVs problem, SIAM J. Appl. Math. 17 (1969), 1086–1093.Google Scholar
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. Even, S. and Gillis, J., Derangements and Laguerre polynomials, Math. Proc. Cambridge Philos. Soc. 79 (1976), 135–143.Google Scholar
17. Erdôs, P. and Szekeres, G., A combinatorial problem in geometry, Composite Mathematica, 2 (1935), 463–470.Google Scholar
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. Henle, M., Dissection of generating functions, Studies in Appl. Math. 51 (1972), 397–410.Google Scholar
20. Jackson, D. M., The combinatorial interpretation of the Jacobi identity from Lie algebras, J. Combinatorial Theory (A), to appear.Google Scholar
21. Jackson, D. M. The unification of certain enumeration problems for sequences, J. Combinatorial Theory (A) 22 (1976), 92–96.Google Scholar
22. Jackson, D. M. Laguerre polynomials and derangements, Math. Proc. Cambridge Philos. Soc. 80 (1976), 213–214.Google Scholar
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. 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. Klarner, D. A. Correspondences between plane trees and binary sequences, J. Combinatorial Theory 9 (1970), 401–411.Google Scholar
26. Long, C. T., Addition theorems for sets of integers, Pacific J. Math. 23 (1967), 107–112.Google Scholar
27.. On a problem in partial difference equations, Canad. Math. Bull. 13 (1970), 333–335.Google Scholar
28. Moser, W. O. J. and Abramson, M., Generalisations of Terquem's problem, J. Combinatorial Theory, 7 (1969), 171–180.Google Scholar
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. Riordan, J., Permutations without C-sequences, Bull. Amer. Math. Soc. 51 (1945), 745–748.Google Scholar
31. Riordan, J. An introduction to combinatorial analysis (Wiley, New York, 1958).Google Scholar
32. Roselle, D. P., Graphs, quasisymmetry and permutations with restricted positions, Duke Math. J. 41 (1974), 41–50.Google Scholar
33. Schenstead, C., Longest increasing and decreasing subsequences, Can. J. Math. 13 (1961), 179–191.Google Scholar
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. Stanley, R. P., Theory and application of plane partitions, II, Studies in Appl. Math. 50 (1967), 259–279.Google Scholar
36. Stanley, R. P. Binomial posets, Mbbius inversion and permutation enumeration, J. Combinatorial Theory (A) 20 (1967), 336–356.Google Scholar
37. Szegô, G., Tiber gewisse Potenzreihen mit lauter positiven Koeffizienten, Math. Z. 87 (1933), 674–688.Google Scholar
38. Tutte, W. T., A census of planar maps, Canad. J. Math. 15 (1963), 249–271.Google Scholar
39. Whitworth, W. A., Choice and chance (Deighton Bell, Cambridge, 1901).Google Scholar