Umbral calculus, binomial enumeration and chromatic polynomials

Ray, Nigel

doi:10.1090/S0002-9947-1988-0957067-0

Umbral calculus, binomial enumeration and chromatic polynomials

Author: Nigel Ray
Journal: Trans. Amer. Math. Soc. 309 (1988), 191-213
MSC: Primary 05A40; Secondary 05C15
DOI: https://doi.org/10.1090/S0002-9947-1988-0957067-0
MathSciNet review: 957067
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We develop the concept of partition categories, in order to extend the Mullin-Rota theory of binomial enumeration, and simultaneously to provide a natural setting for recent applications of the Roman-Rota umbral calculus to computations in algebraic topology. As a further application, we describe a generalisation of the chromatic polynomial of a graph.

[1] Martin Aigner, Combinatorial theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 234, Springer-Verlag, Berlin-New York, 1979. MR 542445
[2] C. Berge, Principles of combinatorics, Translated from the French. Mathematics in Science and Engineering, Vol. 72, Academic Press, New York-London, 1971. MR 0270922
[3] J. Blissard, Theory of generic equations, Quart. J. Pure Appl. Math. 4 (1861), 279-305.
[4] Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR 0460128
[5] Mireille Content, François Lemay, and Pierre Leroux, Catégories de Möbius et fonctorialités: un cadre général pour l’inversion de Möbius, J. Combin. Theory Ser. A 28 (1980), no. 2, 169–190 (French, with English summary). MR 563554, https://doi.org/10.1016/0097-3165(80)90083-7
[6] P. Hall, A contribution to the theory of groups of prime power order, Proc. London Math. Soc. 36 (1932), 39-95.
[7] Michael Henle, Binomial enumeration on dissects, Trans. Amer. Math. Soc. 202 (1975), 1–39. MR 0357133, https://doi.org/10.1090/S0002-9947-1975-0357133-8
[8] S. A. Joni and G.-C. Rota, Coalgebras and bialgebras in combinatorics, Stud. Appl. Math. 61 (1979), no. 2, 93–139. MR 544721, https://doi.org/10.1002/sapm197961293
[9] André Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), no. 1, 1–82 (French, with English summary). MR 633783, https://doi.org/10.1016/0001-8708(81)90052-9
[10] Gilbert Labelle, Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange, Adv. in Math. 42 (1981), no. 3, 217–247 (French). MR 642392, https://doi.org/10.1016/0001-8708(81)90041-4
[11] E. K. Lloyd, Enumeration, Handbook of Applicable Mathematics 5, Wiley, 1985, pp. 531-621.
[12] Saunders Mac Lane, Categories for the working mathematician, 2nd ed., Graduate Texts in Mathematics, vol. 5, Springer-Verlag, New York, 1998. MR 1712872
[13] Ronald Mullin and Gian-Carlo Rota, On the foundations of combinatorial theory. III. Theory of binomial enumeration, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969) Academic Press, New York, 1970, pp. 167–213 (loose errata). MR 0274300
[14] Oscar Nava and Gian-Carlo Rota, Plethysm, categories, and combinatorics, Adv. in Math. 58 (1985), no. 1, 61–88. MR 812935, https://doi.org/10.1016/0001-8708(85)90049-0
[15] Nigel Ray, Extensions of umbral calculus: penumbral coalgebras and generalised Bernoulli numbers, Adv. in Math. 61 (1986), no. 1, 49–100. MR 847728, https://doi.org/10.1016/0001-8708(86)90065-4
[16] -, Symbolic calculus: a 19th century approach to and , Proc. 1985 Durham Sympos. on Homotopy Theory, London Math. Soc. Lecture Note Ser. 117, Cambridge Univ. Press, 1987, pp. 195-238.
[17] N. Ray and C. Wright, Umbral calculus and a new chromatic polynomial, Ars Combinatoria (to appear).
[18] John Riordan, An introduction to combinatorial analysis, Wiley Publications in Mathematical Statistics, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0096594
[19] Steven Roman, The umbral calculus, Pure and Applied Mathematics, vol. 111, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1984. MR 741185
[20] Gian-Carlo Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964). MR 0174487, https://doi.org/10.1007/BF00531932
[21] P. J. Webb, A local method in group cohomology, Comment. Math. Helv. 62 (1987), no. 1, 135–167. MR 882969, https://doi.org/10.1007/BF02564442
[22] E. T. Whittaker and G. N. Watson, A course of modern analysis, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1996. An introduction to the general theory of infinite processes and of analytic functions; with an account of the principal transcendental functions; Reprint of the fourth (1927) edition. MR 1424469