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

Publisher Website
Google Scholar
Abstract
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.

This publication has 2 references indexed in Scilit: