Article contents
An Enumeration Problem Related to the Number of Labelled Bi-Coloured Graphs
Published online by Cambridge University Press: 20 November 2018
Extract
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 a ∈ A and b ∈ B, 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
- Information
- Copyright
- Copyright © Canadian Mathematical Society 1961
References
- 2
- Cited by