An operator approach to the principle of inclusion and exclusion

Liu, C. J.

doi:10.1090/S0002-9939-1986-0822454-1

An operator approach to the principle of inclusion and exclusion
HTML articles powered by AMS MathViewer

by C. J. Liu PDF

Proc. Amer. Math. Soc. 96 (1986), 528-536 Request permission

Abstract:

Using an operator approach we derive Sylvester-Whitworth formulae for sets $A$’s. By the same token we treat the problem where both sets of $A$’s and $B$’s are involved. Our result extends the Sylvester-Whitworth inclusion and exclusion formula to the resolution of the number of elements in exactly ${m_1}$ sets of $A$’s and ${m_2}$ sets of $B$’s respectively. The formula are applied to the complete graph and complete bipartite graph. The enumeration of spanning subgraphs with any preassigned number of disconnected cycles is solved, together with the case where any preassigned number of vertices have degree one.

References

C. J. Liu and Yutze Chow, Enumeration of forests in a graph, Proc. Amer. Math. Soc. 83 (1981), no. 3, 659–662. MR 627715, DOI 10.1090/S0002-9939-1981-0627715-2
C. I. Liu and Y. Chow, Enumeration of connected spanning subgraphs of a planar graph, Acta Math. Hungar. 41 (1983), no. 1-2, 27–36. MR 704520, DOI 10.1007/BF01994058
C. J. Liu and Yutze Chow, An operator approach to some graph enumeration problems, Discrete Math. 44 (1983), no. 3, 285–291. MR 696290, DOI 10.1016/0012-365X(83)90193-0
C. J. Liu and Yutze Chow, On operator and formal sum methods for graph enumeration problems, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 384–406. MR 752043, DOI 10.1137/0605038
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
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 174487, DOI 10.1007/BF00531932
Doron Zeilberger, A short hook-lengths bijection inspired by the Greene-Nijenhuis-Wilf proof, Discrete Math. 51 (1984), no. 1, 101–108. MR 755045, DOI 10.1016/0012-365X(84)90027-X
Herbert S. Wilf, Averages by the sieve method, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 256–260. MR 485425, DOI 10.1016/0097-3165(78)90056-0
T. L. Austin, R. E. Fagen, W. F. Penney, and John Riordan, The number of components in random linear graphs, Ann. Math. Statist. 30 (1959), 747–754. MR 115939, DOI 10.1214/aoms/1177706204
S. Chaiken and D. J. Kleitman, Matrix tree theorems, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 377–381. MR 480115, DOI 10.1016/0097-3165(78)90067-5
Alfréd Rényi, Some remarks on the theory of trees, Magyar Tud. Akad. Mat. Kutató Int. Közl. 4 (1959), 73–85 (English, with Russian and Hungarian summaries). MR 115938

A general formula in the principle of inclusion and exclusion