1 - The generalized scheme of allocation and the components of random graphs

Summary

The probabilistic approach to enumerative combinatorial problems

The solution to enumerative combinatorial problems consists in finding an exact or approximate expression for the number of combinatorial objects possessing the property under investigation. In this book, the probabilistic approach to enumerative combinatorial problems is adopted.

The fundamental notion of probability theory is the probability space (Ω, A, P), where Ω, is a set of arbitrary elements, A is a set of subsets of Ω forming a σ-algebra of events with the operations of union and intersection of sets, and P is a nonnegative countably additive function defined for each event A ∈ A so that P(Ω) = 1. The set Ω is called the space of elementary events and P is a probability. A random variable is a real-valued measurable function ξ = ξ(ω) defined for all ω ∈ Ω.

Suppose Ω consists of finitely many elements. Then the probability P is defined on all subsets of Ω if it is defined for each elementary event ω ∈ Ω. In this case, any real-valued function ξ = ξ(ω) on such a space of elementary events is a random variable.

Instead of a real-valued function, one may consider a function f(ω) taking values from some set Y of arbitrary elements. Such a function f(ω) may be considered a generalization of a random variable and is called a random element of the set Y.

In studying combinatorial objects, we consider probability spaces that have a natural combinatorial interpretation: For the space of elementary events Ω, we take the set of combinatorial objects under investigation and assign the same probability to all the elements of the set.