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

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 (a_i, b_j) is said to be admissible if given any a ∈ A and b ∈ B, there exist elements (a_i, b_j) and (a_k, b_l) (they may be the same) in S such that a_i = a and b_l = 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.