Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-22T09:04:58.600Z Has data issue: false hasContentIssue false

An Enumeration Problem Related to the Number of Labelled Bi-Coloured Graphs

Published online by Cambridge University Press:  20 November 2018

C. Y. Lee*
Affiliation:
Bell Telephone Labs., Inc. , Whip party, N.J.
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.

We will consider the following enumeration problem. Let A and B be finite sets with α and β elements in each set respectively. Let n be some positive integer such that nαβ. A subset S of the product set A × B of exactly n distinct ordered pairs (ai, bj) is said to be admissible if given any aA and bB, there exist elements (ai, bj) and (ak, bl) (they may be the same) in S such that ai = a and bl = b. We shall find here a generating function for the number N(α, β n) of distinct admissible subsets of A × B and from this generating function, an explicit expression for N(α, β n). In obtaining this result, the idea of a cut probability is used. This approach in a problem of enumeration may be of interest.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1961

References

1. Polya, G., Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen, una chemishe Verbindungen, Acta Math., 68 (1937), 145-254.Google Scholar
2. Harary, F., On the number of bi-colored graphs, Pac. J. Math., 8 (1958), 743-755.Google Scholar