1. Introduction

Enumerating a finite set of objects is one of the most basic tasks that can be done by any person. Anybody begins to do it at first while learning the basic arithmetic operations at school. In a very general setting, to enumerate a finite set of things is to put in bijective relation a finite subset of the natural numbers with the things to be counted. As simple as it can be at first sight, the enumeration of things can become a very interesting mathematical activity when we start to count, for instance, in how many ways can we dispose or can we select the n elements of set in k places without repeating them, sometimes allowing repetitions of all of them, or just some of them, etc. That is the starting point of the combinatorics subject. Combinatorics is the field of discrete mathematics that allows us, among other things, to calculate in how many ways some objects can be selected or arranged to comply with any given property.

Within the topic of combinatorial analysis, there is a subfield that is interested in accurately predicting large structured configurations under the analytical method approach and that uses the tool known as generating functions. The analytic combinatorics is devoted to the study of finite structures whose construction follows a certain finite number of given rules. On the other hand, the use of generating functions is a tool that allows to relate discrete analysis proper to discrete mathematics with continuous analysis.

One of the most beautiful and ingenious applications of combinatorial enumeration is the probabilistic method. The probabilistic method is intimately related to the important role that randomness plays in the field of theoretical computer science. The utility and beauty of the probabilistic method consists of being an indirect or nonconstructive proof method. This method has been used successfully during the last 60 years and constitutes one of the most important scientific contributions of the great Hungarian mathematician Erdös [1, 2]. Commonly, this method has been used to prove the existence of a certain mathematical object by showing that if we choose some object of a given class in a random way, the probability that this mathematical object complies with certain property is greater than zero.

The probabilistic method has been used with great success to obtain important results in fields as diverse as number theory, combinatorics, graph theory, linear algebra, computational sciences, or information theory.

One aim of combinatorial analysis is to count the different ways of arranging objects under given constraints. Sometimes the structures to be counted are finite and some other times they are infinite. To enumerate is very important in many scientific fields because it allows to evaluate and compare different solutions to a given problem. For example, in computer science, if I want to compare different algorithms that solve a given kind of information processing problem, it is necessary to enumerate the number of steps taken by each one of them in the worst case and to choose the one whose performance is the best. The task of enumerating things can evolve in complexity to some point that the elementary arithmetical operations are not enough to reach the goal. For that reason many enumeration problems have inspired the most talented mathematicians for developing very ingenious methods for solving them. Some of these techniques for solving combinatorics enumeration problems are going to be exposed in the next section. One very interesting subject of the discrete mathematics is the graph theory. It is in the graph theory where many of the most interesting enumerations of graphs arise that have some given structural property that require the utilization of mathematical tools that facilitate the discovery of closed mathematical forms for the calculation of the number of graphs that accomplish some topological property. In this context it can be important to enumerate how many labeled graphs can be constructed with n vertex or how many connected graphs with n vertex exist, etc. For some of these problems, clever methods have been devised for their calculation that lead to closed mathematical forms by the use of generating functions. For other problems, it is very hard to obtain a closed mathematical form solution, and in that case some asymptotic methods have been developed for estimating a bound when the number of vertex is very large by means of the Cauchy theorem. These mathematical tools are going to be covered in the following sections of the present chapter.

2. Body of the manuscript

The chapter will have the following structure. In Section 3, we will make a quick revision of some mathematical tools that are frequently used for solving combinatorial enumeration problems. The first tool described will be the ordinary generating functions as well as the exponential generating functions. These tools are used when a closed form solution for an enumeration problem can be obtained. The second tool that will be described in this section will be the analytic combinatorics method that is normally used for those enumeration problems whose closed mathematical form are hard to be calculated. The analytic combinatorics techniques allow to estimate an upper bound of that kind of enumeration problems. We take the enumeration of labeled trees as an example of combinatorial enumeration problem that can be solved in a closed mathematical form and make an overview of some different methods devised for that end in Section 4. In Section 5, we roughly describe how the generating functions can be used to solve graph enumeration problems. In Section 6, we take the problem of enumerating regular graphs as an example of a problem whose closed mathematical form is hard to obtain and apply the analytic combinatorics techniques for estimating an upper bound. In Section 7, I give an application of the combinatorial enumeration for proving the almost sure applicability of a node selecting criteria for controlling virus spreading in a complex network. Finally in Section 8, we make some comments about the possible future applications of the combinatorial enumeration methods.

3. Generating functions and analytic combinatorics overview

In this section of the chapter, we are going to make a revision of the basic mathematical tools that have been developed and that facilitate the solution of many combinatorial enumeration problems. We are going to start with some basic conceptual definitions that can be found in many textbooks about this topic. In order to be able to clearly expose the mathematical tools used, it will be necessary to make use of some basic concepts about them that can be consulted more widely in texts such as [3]. One of these basic notions that can be found in [3] is the concept of combinatorial class whose definition is as follows:

Definition 1.1 A combinatorial class is a finite or denumerable set in which a size function is defined, satisfying the following conditions:

The size of an element is a nonnegative integer.
The number of elements of any given size is finite.

On the other hand, it is necessary to know if two combinatorial classes are related in any way which can be determined using the concept of isomorphism and that can be defined as follows:

Definition 1.2 The combinatorial classes A and B are said to be (combinatorially) isomorphic which is written A ≅ B if and only if their counting sequences are identical. This condition is equivalent to the existence of a bijection from A to B that preserves size, and one also says that A and B are bijectively equivalent.

The notion of ordinary generating functions (OGF) as ∑ i = 0 ∞ a i x i where the coefficients a i are elements of the sequence A = a 0 a 1 … or combinatorial class A . This function is also the generating function of the numbers A n whose sizes a n = card A n such that the OGF of class A admits the combinatorial form

A x = ∑ α ∈ A x ∣ α ∣ . E1

This means that the variable x marks size in the generating function. The OGF form (1) can be easily interpreted by observing that the term xⁿ occurs as many times as there are objects in A of size n . A basic operation that can be defined is the one that allows to extract the coefficient of the term x n in the power series A x = ∑ a n x n as follows:

x n ∑ n ≥ 0 a n x n = a n . E2

The concept of generating function can then be defined as:

Definition 1.3 Let be a 0 , a 0 , … a succession of real numbers. The function

f x = a 0 + a 1 x + a 2 x 2 + … = ∑ i = 0 ∞ a i x i E3

is the generating function of the given succession.

The idea comes from the development of Newton’s binomial that con be defined as:

Definition 1.4

1 + x n = n 0 + n 1 x + n 2 x 2 + ⋯ + n n x n E4

which is the generating function of the succession

n 0 , n 1 , n 2 , n 3 , … , n n , 0,0,0 , … E5

We can say, for example, that

∑ i = 0 n x i = 1 + x + x 2 + x 3 + … + x n = 1 + x n + 1 1 − x E6

is the generating function of the succession 1,1,1 , … , 1,0,0,0 , … where the first n + 1 terms are equal to 1. The upper limit of the generating function 6 can be extended to ∞ which is known as geometric series. This series is known to be convergent if x < 1 and that case can be defined as

∑ i = 0 ∞ x i = 1 + x + x 2 + x 3 + … + = 1 1 − x E7

which is the geometric series of the succession 1,1,1 , … . One of the nice properties of the generating functions is that they can be easily manipulated due to the fact that they are infinite polynomials.

For instance, if we take the first derivative of the generating function 7, we get

d dx 1 1 − x = d dx 1 + x + x 2 + x 3 + … = 1 + 2 x + 3 x 2 + 4 x 3 + … = 1 1 − x 2 E8

then 1 1 − x 2 is the generating function of the succession 1,2,3,4 , … , while x 1 − x 2 is the generating function of the succession 0,1,2,3,4 , … . Similarly if we take the first derivative of the generating function x 1 − x 2 , we get

d dx x 1 − x 2 = d dx 0 + x + 2 x 2 + 3 x 3 + 4 x 4 + … = x + 1 1 − x 3 E9

then x + 1 1 − x 3 is the generating function of the succession 1 2 , 2 2 , 3 2 , … , and x x + 1 1 − x 3 is the generating function of the succession 0 2 , 1 2 , 2 2 , 3 2 , … Other simple manipulations that can be done with the generating functions allow us to cancel some element of an associated succession. For example, if g x = 1 1 − x and h x = g x − x 2 = 1 1 − x − x 2 , then h x becomes the generating function of the succession 1,1,0,1,1,1 , … . By the other side, if we know that x x + 1 1 − x 3 is the generating function of the succession 0 2 , 1 2 , 2 2 , 3 2 , … and that x 1 − x 2 is the generating function of the succession 0,1,2,3,4 , … , then if we add these two generating functions, we get

x x + 1 1 − x 3 + x 1 − x 2 = 2 x 1 − x 3 E10

where 2 x 1 − x 3 becomes the generating function of the succession 0,2,6,12,20,30,42 , … whose nth element can be expressed as a n = n 2 + n . If we use the coefficient extracting operator defined by 2, we can say that

x n 2 x 1 − x 3 = n 2 + n E11

As an example, let us take the sequence 0,1,1,2,3,5,8,13,21,34,55 , … know as Fibonacci numbers. This succession can be generated by applying the recurrence relation

F n + 1 = F n + F n − 1 where n ≥ 1 , F 0 = 0 , F 1 = 1 . E12

The goal is to obtain nth element of the succession of numbers generated by 12 that is the coefficient of xⁿ in the expansion of the function

x 1 − x − x 2 E13

as a power series about the origin. The roots of 1 − x − x 2 are x 1 = 1 + 5 2 and x 2 = 1 − 5 2 . Given that the generating function of the Fibonacci succession is 13, we have that

f x = x 1 − x − x 2 = 1 5 1 1 − 1 + 5 2 x − 1 1 − 1 − 5 2 x E14

and the nth term of the Fibonacci succession is expressed in closed form as

F n = 1 5 1 − 1 + 5 2 n − 1 − 1 − 5 2 n E15

The calculation of the n-th term of the Fibonacci sequence by using power series allows us to obtain a mathematical closed formula. Because of that we can calculate the n-th term of the Fibonacci sequence in a more efficient way given that the computer program to do it will consist in the direct application of the closed mathematical expression obtained, which is much more efficient than using a computer program based on the application of the Fibonacci recurrence.

In [4] the problem of the various results that can be obtained using generating functions is addressed. The authors of [4] say that by using the tool of generating functions for obtaining the nth element of a succession, sometimes an exact formula can be obtained easily, and if it is not the case, a good estimation of the nth element can be obtained. It can happen also that we get a recurrence formula from where a generating function can be obtained, or it can happen that from the generating function a new recurrence is obtained giving us a deeper understanding about the succession. The use of generating functions provides statistical information about the succession. The authors of [4] also point out that when it is very difficult to mathematically obtain the n-th term of a given sequence as a closed mathematical expression, a good option is to use asymptotic methods to obtain an estimate of that term. For example, the nth prime number is approximately n log n when n is very big. The authors of [4] also also point out that using generating functions some properties of a succession such as unimodality or convexity can be proven. Another advantage of using generating functions is that some identities as, for example,

∑ j = 0 n n j 2 = 2 n n n = 0,1,2 … , E16

are easy to obtain. Finally, the authors of [4] pointed out that by using generating function, the relationship between problems that have similar generating functions can be discovered.

As was mentioned in the last paragraph, sometimes it is hard to obtain mathematically closed formulas when using generating functions, and in that case, a good alternative is to the use asymptotic formulas. The mathematical tools used for this purpose are part of the field known as analytic combinatorics, and a good reference of this topic is [3]. The main objective of analytic combinatorics is to estimate with a high level of precision the properties of large structured combinatorial configurations by the use of mathematical analysis tools [3].Under this approach, we begin with an exact enumerative description of the combinatorial structure using the generating functions. This description is considered as an algebraic object. The next step is to take the generating function as an analytical object which is a mapping from the complex plane to itself. The singularities found in such a mapping allow to obtain the coefficients of the function in its asymptotic form, resulting in an excellent estimate on the count of the sequences. With this purpose, the authors of [3] classify the analytic combinatorics in the next three topics:

Symbolic methods that establish systematically relations of discrete mathematics constructions and operations on generating functions that encode counting sequences
Complex asymptotics that allow for extracting asymptotic counting information from the generating functions by the mapping to the complex plane mentioned above
Random structures concerning the probabilistic properties accomplished by large random structures

A large material concerning the subject of complex asymptotic analysis is addressed in [5]. A highly recommended text to consult because it covers the applications of the combinatorial tools enumerative to the analysis of algorithms is [6]. In this chapter, there will be a particular interest in the application of generating functions tool for the enumeration of graphs that have some given properties.

Let us start with the definition of a graph. A graph G = V E is a structure with a set of vertices V = v 1 v 2 … v p whose size ∣ V ∣ = p it is called the order of G and a set of unordered pairs of adjacent vertices, called edges, E = v i 1 v j 1 v i 2 v j 2 … v i q v j q if G is undirected or a set of ordered pairs of adjacent vertices E = v i 1 v j 1 v i 2 v j 2 … v i q v j q , if G is a directed graph, whose edge set size is ∣ E ∣ = q , that has no loops and that has no loops multiple edges. A graph G with p vertices and q edges is called a p q graph. In a labeled graph of order p , each vertex has a label that is an integer from 1 to p. Typical questions such as how many graphs can be constructed with n vertices, how many trees with n vertices can be obtained, and how many of these trees are binary can be answered using the generating functions, and a mathematically closed formula can be obtained. In the case that a closed mathematical formula is very hard to be obtained, an accurate asymptotic estimation formula can be a good option.

There are two commonly used generating functions: the first is the ordinary generating functions (OFG) and the other is the exponential generating functions (EGF).

An ordinary generating function is a mathematical function defined by the following expression:

a x = ∑ k = 0 ∞ a k x k , E17

where the coefficients are elements of the succession of numbers a 0 , a 1 , a 2 , … . The ordinary generating functions are used for enumeration problems where the order of the objects is not important. An exponential generating function is a mathematical function defined by the following expression:

b x = ∑ k = 0 ∞ b k x k k ! , E18

where the coefficients are elements of the succession of numbers b 0 , b 1 , b 2 , … . The exponential generating function are used for enumeration problems where the order of the objects matter. Graphs, words, trees, or integer partitions are some of the kinds of objects with which combinatorics deals. Combinatorics deals with discrete objects as, for example, graphs, words, trees, and integer partitions. Counting such objects is one of the most interesting tasks. Enumeration of graphs that have some structural property is the main purpose of the present chapter.

The great mathematician George Pólya made huge contributions to the field of graph enumeration graphs. He obtained closed mathematical expressions for the enumeration of graphs with a given number of vertices and edges for many graph counting problems using group theory [7]. Pólya’s formulas greatly facilitated the enumeration of rooted graphs, connected graphs, etc. The enumeration of number of triangulations of certain plane polygons was one of the first problems of enumeration that attracted the attention of the great mathematician Leonhard Euler [8] in the eighteenth century. Some years later, Kirchhoff in [9] discovered a method for enumerating spanning trees in a connected graph. After that, Arthur Cayley obtained a closed mathematical formula that enumerates labeled trees, rooted trees, and ordinary trees in [10]. The Cayley discovery will be covered with more detail in Section 4. The brilliant and unknown mathematician John Howard Redfield [11] discovered many enumeration formulas anticipating some of Pólya’s contributions.

Some enumeration problems of objects that are not graphs (automata, Boolean functions, or chemical isomers) can be solved by cleverly transforming them to graphs. The generating functions are the tool used for enumerating graphs. There are two types of graphs associated with combinatorial graph enumeration problems:

Labeled graph problems
Unlabeled graph problems

Some enumeration problems of labeled graphs are normally addressed by applying the exponential generating functions tool. The enumeration problems of unlabeled graphs are normally addressed by applying the ordinary generating functions but require the application of Pólya’s theorem.

One of the first problems of enumerating labeled graphs that may arise is that of how many graphs with p vertices and q edges can be obtained.

To solve this enumeration problem, let G p x be the polynomial or ordinary generating function whose coefficient of the term x k represents the number of labeled graphs with p vertices and k edges. If V is the set of vertices of cardinality p , there are q = p 2 pairs of these vertices. In every vertex set V , each pair is adjacent or not adjacent. The number of labeled graphs with k edges is therefore q k = p 2 k . Thus, the ordinary generating function G p x for labeled graphs with p vertices is given by

G p x = ∑ k = 0 m m k x k = 1 + x m , E19

where m = p 2 . Then, the number of labeled graphs with p vertices is G p 1 ; so we have:

G p = 2 m = 2 p 2 . E20

For example, if we want to know how many labeled graphs with p = 3 vertices can be obtained, we apply Formula (20), and we get:

G 3 = 2 3 2 = 2 3 ! 2 ! 1 ! = 2 3 = 8 . E21

If we want to know how many labeled graphs with p = 4 vertices and exactly q = 5 edges exist, before expression (19), we use the coefficient of the term x ⁵

x 5 G p x = x 5 ∑ k = 0 6 6 k x k = 6 5 = 6 ! 5 ! 1 ! = 6 . E22

A question that arises naturally when working with labeled graphs is in how many ways can this be constructed from a certain number of vertices and edges. In order to give a possible answer, the number of symmetries or automorphisms must be taken into account. It is said that there is isomorphism between two graphs G and G ₁ if there is a one-to-one map A : V G ↦ V G 1 between them that preserve adjacency. When G 1 = G , then the mapping A is called automorphism of G . The set of all the automorphisms of G , represented by Γ G , is called the group of G . The elements of Γ G are permutations over V . Let s G = ∣ Γ G ∣ be the order of the group or number of symmetries of G . Therefore, the number of ways in which a graph G of order p can be labeled is

l G = p ! s G . E23

Another example of graph enumeration problem is to count the number of differently labeled connected graphs. The notion of path of length n is defined as a sequence of vertices v 0 v 1 … v n where the edges v i v i + 1 for i = 0 , … n that belong to the path are distinct. It is said that a graph is connected if for any pair of vertices there is a path between them. To obtain the formula that counts all the connected graphs C p of order p , it will be necessary to make use of the concept of subgraph. It is said that a H is a subgraph of a graph G if V H ⊂ V G and E H ⊂ E G . A subgraph that is maximally connected is called component. A rooted graph is a graph that has a distinguished vertex called root. When there exists an injective mapping f : V H 1 ↦ V H 2 between two rooted graphs H 1 and H 2 that preserves the adjacency among vertices as well as the roots, it is said that the two rooted graphs are isomorphic. Let us make the assumption that a k for k = 1,2,3 , … represents the number of ways in which we can label all graphs of order that accomplish the property P a and whose exponential generating function is

a x = ∑ k = 1 ∞ a k x k k ! . E24

Let us also assume that b k for k = 1,2,3 , … is the number of ways of labeling all graphs of order that accomplish the property P b and whose exponential generating function is

b x = ∑ k = 1 ∞ b k x k k ! . E25

If we make the product of series (24) and (25), the coefficients of x k k ! in a x b x is the number of ordered pairs G 1 G 2 of two disjoint graphs, where G 1 meets the property P a , G 2 fulfills the property P b , k is the number of vertices in G 1 ∪ G 2 , and the labels from 1 to k have been distributed over G 1 ∪ G 2 . If C x is the exponential generating function for labeled connected graphs

C x = ∑ k = 1 ∞ C k x k k ! , E26

then C x C x becomes the generating function that counts all the ordered pairs of connected graphs with labels. If you divide by 2, equation (26) that is, we divide it by 2, we get the generating function for labeled graphs that have exactly two components.

By applying this operation n times, the coefficient of x k k ! that corresponds to the number of labeled graphs of order k is obtained with exact n components

G x = ∑ n = 1 ∞ C n x n ! . E27

From (27), we obtain the following relation

1 + G x = e C x . E28

Riordan in [12] obtained the relation C p = J p 2 , where J p x enumerates the trees by inversions, and then deduced

C p = ∑ k = 1 p − 1 p − 2 k − 1 2 k − 1 C k C p − k . E29

From (29), it should be noted that if the exponential generating function for the graph class is known in advance, then the exponential generating function for the class of graphs will be the logarithm of the first series, just as in (28). It should also be mentioned that another equivalent recurrence function can be obtained for the enumeration of the connected graphs that have order tags p (p. 7 in [13]) and that can be expressed mathematically as

C p = 2 p 2 − 1 p ∑ k = 1 p − 1 k p k 2 p − k 2 C k . E30

From (30), the following MATLAB code can be implemented for calculating the number of connected graphs C_p of orders going from p = 1 to p = 20 .

function y = CuentaGrafConnEtiq( p )

% recurrence satisfied by the number of connected graphs

% Harary Graph Enumeration pag. 7

% C_p= 2ˆ{combinations(p,2)}-1/p* \sum_{k=1}ˆ{p-1} k*

% combinations(p,k)*2ˆ{combinations(p-k,2)}*C_{k}

C(1:p)=0;

C(1,1)=1;

for k=2:p

acum=0;

for j=1:k

acum = acum + j * combinaciones(k,j) * CuentaGrafEtiq(k-j) * C(1,j);

end

C(1,k) = CuentaGrafEtiq(k)-(1/k)*acum;

end

y=C(1,p);

sprintf(‘end function z=combinaciones(n,k) z= factorial(n)/(factorial(k)*factorial(n-k));

end

function z=combinaciones(n,k)

z= factorial(n)/(factorial(k)*factorial(n-k));

end

%% calling the function from the matlab prompt for the calculation of the

%% evaluation from graphs of order 1 to 20

>> for i=1:20

R(1,i)=CuentaGrafConnEtiq( i );

end

The calculations obtained by the execution of MATLAB code are shown in Table 1.

p	C_p
1	1
2	1
3	4
4	38
5	728
6	26,704
7	1,866,256
8	251,548,592
9	66,296,291,072
10	34,496,488,594,816
11	35,641,657,548,953,344
12	7.335460 × 10 19
13	3.012722 × 10 23
14	2.471649 × 10 27
15	4.052768 × 10 31
16	1.328579 × 10 36
17	8.708969 × 10 40
18	1.41641 × 10 46
19	2.992930 × 10 51
20	1.569216 × 10 57

Table 1.

Order 1–20.

From the results of 1, it can be observed that the number of possible connected graphs C_p grows very fast in terms of the number p of vertices. It should be mentioned that (29) and (30) are recurrence relations instead of a closed formula. The recurrences (29) or (30) can be used for the calculation of C_p with a computer program. The generating functions can be used to solve recurrences and obtain a closed mathematical expression for the nth term of the succession associated with the recurrence. It can happen that calculation of the solution of some recurrences becomes very hard to be solved and in the worst cannot be solved at all. An alternative method for obtaining an approximate value for big values of p is to recur to the application of methods used in analytic combinatorics and calculate accurate approximations of the pth coefficient of the generating function. The generating functions algebraic structure allows to reflect the structure of combinatorial classes. The analytic combinatorics method consists in examining the generating functions from the point of view of the mathematical analysis by giving not only real value values to its variables but also values in the complex plane. When complex values are assigned to the variables of the generating functions, the function is converted in a geometric transformation of the complex plane. This kind of geometrical mapping is said to be regular (holomorphic) near the origin of the complex plane. When we move away from the origin of the complex plane, some singularities appear that are related with the absence of smoothness of the function and give a lot of information about the function coefficients and their asymptotic growth. It can happen that elementary real analysis is enough for estimating asymptotically enumerative successions. If this is not the case, the generating functions are still explicit, but its form does not allow the easy calculation of the coefficients of the series. The complex plane analysis however is a good option for asymptotic estimation of these coefficients. In order to give an example of the use of the notion of singularities, let us take the ordinary generating function of the Catalan numbers

f x = 1 2 1 − 1 − 4 x . E31

Eq. (31) expresses in a compact way the power series of the form

1 − y 1 / 2 = 1 − 1 2 y − 1 8 y 2 − … . E32

The generating function (31) coefficients can be explicitly expressed as

f n = x n f x = 1 n 2 n − 2 n − 1 . E33

Using the Stirling formula, we can get the asymptotic approximation of (33) that is expressed as

f n ∼ lim n → ∞ 4 n π n 3 . E34

If the generating function is used as an analytic object, the approximation (34) can be obtained.

In order to do it, we substitute in the power series expansion of the generating function f(x) any real or complex value ρ f whose modulus is small enough, for example, ρ f = 4 . The graph that we get by the use of (31) is smooth and differentiable in the real plane and tends to the limit 1 2 as x → 1 4 − , but, if we calculate its derivative, we obtain the following function

f x = 1 1 − 1 − 4 x , E35

and it can be noticed that the derivative (35) becomes infinite in ρ f = 1 4 . The singularities will correspond to those points where the graph is not smooth.

It should be pointed out that that the region where function (31) is still being continuous can be extended. Let us take for example the value x = − 1

f − 1 = 1 2 1 − 5 . E36

We can evaluate in the same manner (31) giving to x values in the complex plane whose modulus is less than the radius of convergence of the series defined by (31) and realize that the orthogonal and regular grid in it transforms the real plane in a grid on the complex plane that preserves the angles of the curves of the grid. This property corresponds to the complex differentiability property, which also is equivalent to the property of analyticity. Concerning the asymptotic behavior of the coefficients f_n of the generating function, it should be observed that it has a general asymptotic pattern composed by an exponential growth factor A n and a subexponential factor θ n .

For the case of the expression (34) A = 4 and θ n ∼ 1 4 π n 3 − 1 , the exponential growth factor can be put in relation with the radius of convergence of the series by A = 1 ρ f that is the singularity that can be observed along the positive real axis of the complex plane that normally corresponds to the pole of the generating function, and the subexponential part θ n = O n − 3 2 arises from the singularity of the square root type. This asymptotic behavior can be compactly expressed as

x n f x = A n θ n . E37

The exponential growth part of (37) is known as first principle of coefficient asymptotics and the subexponential growth part as second principle of coefficient asymptotics. By recalling to the results that can be found in the field complex variable theory, more general generating functions can be obtained. One of those results is the Cauchy residue theorem that relates global properties of a meromorphic function (its integral along closed curves) to purely local characteristics at the residues poles. An important application of the Cauchy residue theorem concerns a coefficient of analytic functions. This is stated in the following theorem [3]:

Theorem 1.5 (Cauchy’s coefficient formula). Let f z be analytic in a region containing 0, and let λ be a simple loop around 0 that is positively oriented. Then, the coefficient z n f z admits the integral representation:

f n ≡ z n f z = 1 2 iπ ∫ λ f z dz z n + 1 . E38

For more details about analytic combinatorics, we recommend to consult [3] as well as [5].

4. Enumeration of trees

A graph is a structure composed by a set of vertices V = v 1 v 1 … v n and a set of pairs of connected vertices E = e 1 e 2 … e m called edges where E ⊂ V × V and each edge e k ∈ E is composed as pair of vertices e k = v i v j . A tree is a special type of graph that do not have cycles. A tree have no loops or edges that connect a vertex with himself. The subject of combinatorial graph enumeration has been the center of interest of many mathematicians a long time ago. The enumeration of total possible labeled trees with n nodes being n n − 2 was one of first results obtained by Cayley in [10]. Cayley’s formula for enumerating trees is one of the simple and elegant mathematical results in enumeration of graphs. He detected that from n + 1 vertices, the number of possible trees that can be built is equal to n + 1 n − 1 . Cayley [10] gives an example for the case of four vertices 4 = n + 1 then n = 3 , and the total number of possible trees calculated using his formula gives 4 2 = 16 . In this same publication, Cayley gives another example having n + 1 = 6 vertices (he used the term knots in his publication) with labels a , b , c , d , e , f and related the concatenation of vertices given by the edges for obtaining sequences of labels representing a given tree. For instance, if the tree is a chain of vertices connected by edges starting with the vertex a and ending with the vertex f and having as connecting edges a b , b c , c d , d e , e f , the corresponding label sequence is abcdef as shown in Figure 1. As another example of sequence of vertex labels, if the root of the tree is α and it is connected directly with the other five vertices, then the connecting edges will be a b , a c , a d , a e , a f , and the corresponding sequence of vertex labels will be in that case a 5 bcdef as shown in Figure 2. As can be noticed, the exponent of a is 5 that represents the number of occurrences of this label in the set of connecting edges.

Figure 1.
Example of tree of one branch.

Figure 2.
Example of tree with more branches.

After that Cayley states the theorem for this particular case as follows:

Theorem 1.6 The total number of trees T n + 1 that can be built with n + 1 = 6 vertices can be calculated as follows

T n + 1 = a + b + c + d + e + f 4 abcdef = 6 4 = 1296 E39

This calculation relates the sum of the products of the coefficients of the multinomial a + b + c + d + e + f 4 with the number of terms of its corresponding type. Each term obtained by multiplying abcdef with the vertex label inside a + b + c + d + e + f 4 corresponds to different trees.

At the end of [10], Cayley generalizes his theorem by recalling a result obtained by C.W. Borchardt in [14] that relates some particular kind of determinants that represent spanning trees and whose product represents the branches of those spanning trees. Given that the number of terms of these determinants is n + 1 n − 1 , Cayley can conclude that the number of spanning trees is the same. Since these first results, many other methods have been proposed for obtaining the same result. One way to enumerate a collection of objects is to find a bijection between a set of objects whose enumeration is known and the set of objects that we want to enumerate. This was the method used by Prüfer in [15] for enumerating the set of possible spanning trees with n vertices. The set whose number was known beforehand was a sequence of length n − 2 of numbers from 1 to n. For this end the autor of article [15] encoded the trees as Prüfer sequences. In [16] Moon generalized the result derived by Clarke in [17] by induction on d the degree, making induction on n, and the number of vertices and obtains a new enumeration method for n-labeled k trees.

5. Enumeration and generating functions

The field of combinatorial enumeration has aroused enormous interest among mathematicians who have worked in the area of discrete mathematics during the last decades [18, 19, 20, 21]. Combinatorial enumerative technique developed by these brilliant researchers have allowed us to count words, permutations, partitions, sequences, and graphs. As was mentioned in Section 3, the mathematical tool frequently used for this purpose is the generating functions or formal power series.

The generating functions allow to connect discrete mathematics and continuous analysis in a very special way with complex variable theory. The typical situation that someone faces when trying to solve an enumeration problem is that you want to know the mathematically closed form that has the nth term of a given sequence of numbers a 0 , a 1 , a 2 , … For some sequences, we can do by inspection. For example, if the numerical sequence 1,3,5,7,9 , … , it is easy to see that it is a sequence of odd numbers whose nth element is a n = 2 n − 1 .

A more complicated sequence is the set of prime numbers 2,3,5,7,11,13,17,19 , … , whose a_n is the nth prime number. A closed mathematical formula for nth prime number is not known, and it seems impossible to obtain in general.

In many cases it is very hard to get a simple formula just by inspection. However it can be very useful to use the generating functions whose coefficients are the elements of that sequence transforming it as follows:

∑ i = 0 ∞ a i x i . E40

Eq. (40) defines an ordinary generating function. As mentioned in Section 3, since they are infinite polynomials, they can be algebraically manipulated easily.

In this chapter, the main interest will be the application of the generating functions tool as well as the analytic asymptotic methods for the enumeration of graphs accomplishing some given properties. Many questions about the number of graphs that have some specified property can be answered by the use of generating functions. Some typical questions about the number of graphs that fulfill a given property are, for example: How many different graphs can I build with n vertices? How many different connected graphs with n vertices exist? How many binary trees can be constructed with n vertices? [18, 19], etc. For some of these questions, the application of generating functions allows us to easily obtain a simple formula. For some other questions, the answer is an asymptotic estimation formula. The most commonly used generating functions are the ordinary generating functions and the exponential generating functions. The generating functions are the tool used for enumerating graphs. From the point of view of the generating functions, there are two types of graph enumerating problems:

Labeled graph problems
Unlabeled graph problems

The labeled graph problems can be easily solved with the direct application of the exponential generating functions. The case of the unlabeled enumeration problems can be solved by using ordinary generating functions but require the use of more combinatorial theory and the application of Pólya’s theorem.

6. Enumerating regular graphs

As we mentioned in Section 6, some enumerating problems can be solved easily using generating tools for obtaining a closed formula. Some other problems are more hard to deal with for obtaining a closed mathematical expression, but we can resort in such a case to the asymptotic approximation of the coefficients of the power series [22, 23, 24, 25]. It was also mentioned in Section 6 that there are some graph enumerating problems where the nodes are labeled, and in such a case the use of the exponential generating functions is well adapted for these kinds of problems. The other case of graph enumerating problems is when we are dealing with graphs whose nodes do not have an assigned label. Then, we can resort in such case to Pólya’s enumerating method [7, 13], and the best choice is to use ordinary generating functions. It should also be mentioned that the edges of the graphs to be enumerated can be directed or undirected.

One of the seminal articles of enumerating graphs is [26], where a fundamental theorem was proven in the theory of random graphs on n unlabeled nodes and with a given number q of edges.

In [26], the authors obtained a necessary and sufficient condition for relating asymptotically the number of unlabeled graphs with n nodes and q edges with the number of labeled graphs with n nodes and q edges. Let T_nq be the number of different graphs with n nodes and q edges, F_nq the corresponding to number of labeled graphs, N = n n − 1 2 the possible edges, and F nq = N q = N ! q ! N − q ! . The result obtained in [26] can be stated as the following theorem:

Theorem 1.7 The necessary and sufficient conditions that

T nq ∼ F nq n ! E41

as n → ∞ is that

min q N − q / n − log n / 2 → ∞ . E42

The formal result expressed in Theorem 1.7 for unlabeled graphs is a starting point on the enumeration of regular graphs because it allows for enumerating those unlabeled graphs that have some number of edges. In fact, the author of [26] proved that if a graph with ∣ E ∣ = E n edges, where n is the number of vertices or order of such a graph, has no isolated vertices or two vertices of degree n − 1, then the number of unlabeled graphs of order n and number of edges ∣ E ∣ divided by the number unlabeled graphs is asymptotic to n ! .

Another interesting article on asymptotic enumeration of labeled graphs having a given degree sequence was [27]. The authors of [27] obtained their asymptotic result for n × n symmetric matrices subject to the following constraints:

Each row sum is specified and bounded.
The entries are bounded.
A specified sparse set of entries must be zero.

The authors of [27] mentioned that their results can be interpreted in terms of incidence matrices for labeled graphs. The results of [27] can be stated as follows. Let M n z be the set of all n × n symmetric 0 1 matrices with at most z zeroes in each row, r a vector over d = 0 1 … d , and G M r t the number of n × n symmetric matrices g ij over t = 0 1 … t such that

g ij = 0 if m ij = 0 .
∑ j g ij = r i .

Theorem 1.8 For given d , t and z ,

G M r t ∼ T f δ e εa − b ∏ r i ! . E43

Uniformly, for M r ∈ ∪ n = 1 ∞ M n z × 0 d n as f → ∞ , where f = ∑ i r i , ε = − 1 if t = 1 and + 1 if t > 1 , for a = ∑ i r i 2 f 2 + ∑ m ij r i 2 f , b = ∑ m ij = 0 , i < j r i r j + ∑ i r i 2 f , δ = ∑ m ij = 0 r i and T f δ being the number of involutions on [1, f] such that no element in some specified set of size δ is fixed.

Three years later, the article [28] appeared giving a different approach of [27] allowing for obtaining a more general asymptotic formula without reference to an exact formula. The asymptotic result obtained by Bela Bollobás in [28] for enumerating labeled regular graphs is proven by a probabilistic method. This result can be stated as follows. Let Δ and n be natural numbers such that Δ n = 2 m is even and Δ ≤ 2 log n 1 2 , where n is the number of vertices and m is the number of edges of the graph G. Then, as n → ∞ , the number of labeled Δ -regular graphs on n vertices is asymptotic to

e − λ − λ 2 2 m ! m ! 2 m Δ ! m , E44

where λ = Δ − 1 2 .

The authors of [27] affirm that the asymptotic Formula (44) holds not only for Δ constant but also for Δ growing slowly as n → ∞ and summarized this in the following theorem.

Theorem 1.9 Let d 1 ≥ d 2 ≥ … d n be natural numbers with ∑ i = 1 n d i = 2 m even. Suppose Δ = d 1 ≤ 2 log n 1 2 − 1 and m ≥ max ε Δ n 1 + ε n for some ε > 0 . Then, the number L d of labeled graphs with degree sequence d = d i 1 n satisfies

L d ∼ e − λ − λ 2 2 m m 2 m ∏ i = 1 n d i ! , E45

where λ = 1 2 m ∑ i = 1 n d i 2 .

In the next year, the author on [27] extended this result to the case of unlabeled graphs in [29]. The result of Theorem 1.9 extended for the case of unlabeled graphs can be summarized in the following theorem.

Theorem 1.10 If Δ ≥ 3 and L Δ = e − λ − λ 2 2 m ! m ! 2 m Δ ! m , then

U Δ ∼ L Δ n ! ∼ e − Δ 2 − 1 4 2 m ! 2 m m ! Δ ! − n n ! , E46

where m = Δ n 2 .

For the details of the proof of Theorems 1. 9 and 1.10, see [28, 29], respectively.

7. Example of proof of a result on control using combinatorial enumeration

In [30] I used the combinatorial enumeration methods and probability for showing the applicability of the selection node criteria in a virus spreading control problem in complex networks. The main purpose of this section is to illustrate how the enumerative combinatorics in combination with probability theory can be used for demonstrating mathematically a result in an application field. We can mention that the case of homogeneity in the behavior of the nodes and their interaction cannot be discarded given what has been observed in the reaction of the agents in the context of social networks is that they try to minimize the conflict. Many successful models can, for example [30, 31, 32, 33], base their predicting effectiveness on the homogeneity of the behavior of the nodes and their interaction. By the other side, in [30] we have obtained a criteria for selecting the nodes to be controlled, but such criteria fail if we have homogeneity in the behavior of the nodes and, at the same time, the topology of the network is regular. Then, what we want to do here is to justify the applicability of node selection criteria, keeping the homogeneity of the nodes and trying to compare the number of regular graphs with n vertices with the total of graphs that can be constructed with n vertices. For this end, based on the results on combinatorial graph enumeration mentioned on Theorems 1.9 and 1.10, we can state our main result as follows. First of all, we suppose that our graph is labeled, G = V E is r-regular with r ≥ 3 constant and rn = 2 m , where n = ∣ V ∣ corresponds to the number of vertices and m = ∣ E ∣ corresponds to the number of edges. Let L_r the number of labeled regular graphs of degree r whose asymptotic value is [28]

L r ∼ e − r 2 − 1 4 2 m ! 2 m m ! r ! n . E47

Let G_n be the number of all possible graphs with n vertices whose value is

G n = 2 n 2 . E48

Theorem 1.11 If r ≥ 3 and nr = 2 m , then

lim n → ∞ L r G n = 0 . E49

Proof of Theorem 1.11. If nr = 2 m and r is constant of value c ₁, then we can deduce that m = r 2 n = c 1 2 n , and this implies that m = O n so let us say that m = c 2 n ; then,

lim n → ∞ L r G n = lim n → ∞ e − c 1 2 − 1 4 2 c 2 n ! c 1 ! − n 2 c 2 n c 2 n ! 2 n 2 E50

= lim n → ∞ e − c 1 2 − 1 4 c 1 ! n 2 c 2 n ! 2 c 2 n c 2 n ! 2 n n − 1 2 , E51

applying the approximation Stirling formula n ! ∼ 2 πn n e n

c 1 ! n = 2 π c 1 c 1 e c 1 n E52

then

= lim n → ∞ e − c 1 2 − 1 4 2 π c 1 c 1 e c 1 n 2 c 2 n ! 2 c 2 n c 2 n ! 2 n n − 1 2 E53

simplifying

= lim n → ∞ 1 2 π c 1 n c 1 c 1 n e c 1 2 + 4 c 1 n + 1 4 2 c 2 n ! 2 c 2 n c 2 n ! 2 n n − 1 2 E54

applying the approximation Stirling formula

2 c 2 n ! = 2 π 2 c 2 n 2 c 2 n e 2 c 2 n E55

and

c 2 n ! = 2 π c 2 n c 2 n e c 2 n E56

we get

= lim n → ∞ 1 2 π c 1 n c 1 c 1 n e c 1 2 + 4 c 1 n + 1 4 2 π 2 c 2 n 2 c 2 n e 2 c 2 n 2 c 2 n 2 π c 2 n c 2 n e c 2 n 2 n n − 1 2 , E57

simplifying

= lim n → ∞ 2 2 π c 1 n c 1 c 1 n e c 1 2 + 4 c 1 n + 1 / 4 c 2 n e c 2 n 2 n n − 1 2 E58

given that r ≥ 3 , for which we assumed that r is a constant c 1 , and that nr = 2 m , then we have that c 1 = 2 c 2 , and replacing that, in (58), we can express it in terms of c 1 , which is the regular degree r assumed as fixed; then, we get

lim n → ∞ 2 2 π c 1 n c 1 c 1 n e c 1 2 + 4 c 1 n + 1 / 4 c 1 n / 2 e c 1 n / 2 2 n n − 1 2 , E59

and, replacing c ₁ by r in (59), we get

lim n → ∞ 2 2 πr n r rn e r 2 + 4 rn + 1 / 4 rn / 2 e rn / 2 2 n n − 1 2 . E60

Therefore, if the degree r is constant, the lim n → ∞ L r G n = 0 .

Now, our main result can be stated as a consequence of Theorem 1.11.

Theorem 1.12 If we assume that all graphs are uniformly distributed and that the nodes have homogeneous behavior, then the criteria for selecting nodes to be controlled are almost always applicable.

Proof of Theorem 1.11. As a consequence of Theorem 11, we know that the probability that a regular graph appears tends to zero as n → ∞ . Then, the mentioned criteria are almost always applicable.

8. Conclusions

In the present chapter, some problems of combinatorial graph enumeration as well as some useful techniques for obtaining a closed mathematical expression were addressed. When it is not possible to obtain a closed expression, asymptotic estimations of the kind used in analytic combinatorics can be used. In Section 10 the use of these techniques for proving a result in the field of virus spreading control was illustrated [31, 32, 33, 34].

This allowed to explore the application of combinatorial techniques to control problems in networks and thus verify the goodness of said methods for network analysis and the control of virus propagation in them. This still needs to be studied by applying the combinatorial methods discussed above, if there are any other types of topologies that prevent the application of the selection criteria of nodes to be controlled under the hypothesis of behavior of partially heterogeneous nodes, that is, if in the network we have subsets of nodes with the same behavioral parameters. The selecting node criteria described in [30] are based on the combination of the parameter values of the selected nodes as well as their degrees. In many recent publications [35, 36, 37, 38, 39, 40, 41, 42], interesting and elaborated methods for detecting the influencer nodes in complex networks have been proposed that I will try to apply in combination with the mentioned criteria in the future in order to reduce the number of nodes to be controlled.

Dima Ioan Constantin

Chapters authored

Related collaborators

Philemon Mzee

James Campbell

Gabriel Awuah

Delia Popescu

Constanta Popescu

Ana Lucia Ristea

Richard Vahrenkamp

Daniel Dumitru Stan

Mariana Man

Ştefan Vlăduţescu