arXiv:1512.06355v3 [math.CO] 20 Jan 2016

A NEW FORMULA FOR THE GENERATING FUNCTION OF THE
NUMBERS OF SIMPLE GRAPHS
LEONID BEDRATYUK AND ANNA BEDRATYUK
Abstract. By using an approach of the invariant theory we obtain a new formula for the
ordinary generating function of the numbers of the simple graphs with n nodes.

Keywords: Invariant theory; simple graph; graph invariants; generating functions
2000 MSC: 13A50; 05C30
1. Introduction. Let an,i be the number of simple graphs with n vertices and k edges. Let
 
m
X
n
i
,
gn (z) =
an, i z , m =
2
i=0
be the ordinary generating function for the sequence {an,i }, the OIES sequence A008406. For
the small n we have
g1 (z) = 1,
g2 (z) = 1 + z,
g3 (z) = 1 + z + z 2 + z 3 ,
g4 (z) = 1 + z + 2z 2 + 3z 3 + 2z 4 + z 5 + z 6 .
An expression for gn (z) in terms of group cycle index was found by Harary in [1]. The result is
based on Polya’s efficient method for counting graphs, see [2] and [3]. Let G be a permutation
group acting on the set [n] := {1, 2, . . . , n}. It is well known that each permutation α in G
can be written uniquely as a product of disjoint cycles. Let ji (α) be the number of cycles of
length i, 1 ≤ i ≤ n in the disjoint cycle decomposition of α. Then the cycle index of G denoted
Z(G, s1 , s2 , . . . , sn ), is the polynomial in the variables s1 , s2 , . . . , sn defined by
n

1 X Y ji (α)
Z(G, s1 , s2 , . . . , sn ) =
s
.
|G| α∈G i=0 i
Denote by [n](2) the set of 2-subsets of [n]. Let Sn be a permutation group on the set [n]. The
(2)
pair group of Sn , denoted Sn is the permutation group induced by Sn which acts on [n](2) .
(2)
Specifically, each permutation σ ∈ Sn induces a permutation σ ′ ∈ Sn such that for every
element {i, j} ∈ [n](2) we have σ ′ {i, j} = {σi, σj}.
In [1] F. Harary proved that the generating function gn (z) is determined by substituting
(2)
1 + z k for each variable sk in the cycle index Z(Sn , s1 , s2 , . . . , sn ). Symbolically
gn (z) = Z(Sn(2) , 1 + z),
1

2

LEONID BEDRATYUK AND ANNA BEDRATYUK

where
Z(Sn(2) ) =

1
n! j

X

n!

1 +2j2 +···+njn =n

n
Q

k jk jk !

k=1

Y
k

kj

2k+1
s2k+1

jk Y
Y
(r,t)j j
k−1 j2k k ( 2 )
s[r,t] r r .
(sk s2k
) sk

k

r<t

In the paper by an approach of the invariant theory we derive another formula for the
generating function gn (z).
Let Vn be a vector space of weighted graphs on n vertices over the field K, dim Vn = m. The
(2)
group Sn acts naturally on Vn by permutations of the basic vectors. Consider the corresponding
(2)
(2)
action of the group Sn on the algebra of polynomial functions K[Vn ] and let K[Vn ]Sn be the
corresponding algebra of invariants. Let Vn0 be the set of simple graphs. The corresponding
(2)
algebra of invariants k[Vn0 ]Sn is a finite-dimensional vector space and can be expanded into the
direct sum of its subspaces:
K[Vn0 ] = (K[Vn0 ])0 + (K[Vn0 ])1 + · · · + (K[Vn0 ])m .
In the paper we have proved that dim(K[Vn0 ])i = an,i . Thus the generating function gn (z)
(2)
(2)
coincides with the Poincaré series P(K[Vn0 ]Sn , z) of the algebra invariants K[Vn0 ]Sn .
(2)
Let us identify the elements of the group Sn with permutation m × m matrices and denote
1m the identity m × m matrix. In the paper we offer the following formula for the generating
function gn (z):
gn (z) =

1 X det(1m − α · z 2 )
.
n!
det(1m − α · z)
(2)
α∈Sn

Also for the generating function mn (z) of multigraphs on n vertices we prove that
mn (z) =

1 X
1
.
n!
det(1
−
α
·
z)
m
(2)
α∈Sn

2. Algebra of invariants of simple graphs. Let K be a field of characteristic zero. Denote
by Vn the set of undirected graphs on the vertices {1, ..., n} and whose edges are weighted in K.
A simple graph is a graph with weights in {0, 1} and a multigraph is a graph with weights in
K. For any pair {i, j} let e{i,j} be the simple graph with one single edge {i, j} and let g{i,j} e{i,j}
be the graph with one single edge {i, j} and with the weight g{i,j} 
∈ K.
 The set Vn is the vector
n
. Indeed, any graph can
space with the basis e{1,2} , e{1,3} , . . . e{n−1,n} of dimension m =
2
P
be written uniquely as a sum
g{i,j}e{i,j} . Let Vn∗ be the dual space with dual basis generated
by the linear functions x{i,j} for which x{i,j} (e{k,l} ) = δik δjl . The symmetric group Sn acts on
Vn and on Vn∗ by
σ e{i,j} = e{σ(i),σ(j)} , σ −1 x{i,j} = x{σ(i),σ(j)} .
Let us expand the action on the algebra of polynomial functions K[Vn ] = K[{x{i,j} }].
We say that a polynomial function f ∈ K[x{i,j} ] of m variables x{i,j} is a Sn -invariant if
σf = f for all σ ∈ Sn . The Sn -invariants form a subalgebra K[Vn ]Sn which is called the algebra
of invariants of the vector space of the weighted graphs in n vertices. It is clear that there is
an isomorphism K[Vn ]Sn ∼
= K[x{i,j} ]Sn .
For convenience, we introduce a new set of variables:
{x1 , x2 , . . . , xm } = {x{1,2} , x{1,3} , . . . , x{n−1,n} }.

A NEW FORMULA FOR THE GENERATING FUNCTION OF THE NUMBERS OF SIMPLE GRAPHS

3

Then the action of Sn on the set {x{1,2} , x{1,3} , . . . , x{n−1,n} } induces its action of the pair group
(2)
Sn on the set {x1 , x2 , . . . , xm }. We have
(2)
K[x{i,j} ]Sn ∼
= K[x1 , x2 , . . . , xm ]Sn .

In this notation any graph can be written in the way
g1 e1 + g2 e2 + · · · + gm em , gi ∈ K,
where es is the edge which connect the vertices {i′ , j ′ } if the pair {i′ , j ′ } has got the number s.
Thus, in this case the old variable x{i′ ,j ′} corresponds to the new variable xs .
Since for the simple graphs all its weights are 0, 1 then the reduction of the algebra K[Vn ]Sn
on the set of simple graphs has a simple structure.
Denote by Vn0 the set of all simple graphs on n vertices:
( m
)
X
Vn0 =
gi ei | gi ∈ {0, 1} ⊂ Vn ,
i=0

The corresponding subalgebra of polynomial function K[Vn0 ] ⊂ K[Vn ] is generated by polynomial functions xi which on every simple graph only take values 1 or 0.
Let us consider the ideal Im = (x21 − x1 , x22 − x2 . . . , x2m − xm ) in the algebra K[Vn ] =
K[x1 , x2 , . . . , xm ]. The following statement golds:

Theorem 1.
(i)

K[Vn0 ] ∼
= K[x1 , x2 , . . . , xm ]/Im ,

(2)
(2)
(ii) K[Vn0 ]Sn ∼
= K[x1 , x2 , . . . , xm ]Sn /Im .

Proof. On the ring of polynomial functions K[x1 , x2 , . . . , xm ] let us introduce a binary relation
∼: f ∼ g if f = g, considered as functions from {0, 1}m to K. Obviously that xpi ∼ xi , for all
p ≥ 1. Define an endomorphism γ : K[Vn ] → K[Vn0 ] by the way:
γ(xpi ) = xi .
It is clear that the kernel of the endomorphism is exactly the ideal Im . Then
K[V 0 ] ∼
= K[x1 , x2 , . . . , xm ]/Im .
n

K[Vn0 ]

Note that the algebra
is a finite dimensional vector space of the dimension 2m with the
basis
1, x1 , x2 , . . . , xn , x1 x2 , x1 x2 , . . . , xm−1 xm , . . . , x1 x2 · · · xm .
(2)

(ii) It is enough to prove that γ commutes with the action of the group Sn . Without lost
(2)
of generality it is sufficient to check on the monomials. For arbitrary element σ ∈ Sn and for
arbitrary monomial xk11 xk22 · · · xks s , s ≤ m we have
1
2
s
γ(σ −1 (xk11 xk22 · · · xks s )) = γ(xkσ(1)
xkσ(2)
· · · xkσ(s)
) = xσ(1) xσ(2) · · · xσ(s) =

= σ −1 (x1 x2 · · · xs ) = σ −1 γ(xk11 xk22 · · · xks s ) .
(2)
Sn



then we are able to find the algebra of invariants
If we know the algebra of invariants K[Vn ]
(2)
(2)
0 Sn
K[Vn ]
of simple graphs. Indeed, if the invariants f1 , f2 , . . . , fs generate the algebra K[Vn ]Sn
then the surjectivity of γ implies that the invariants γ(f1 ), γ(f2 ), . . . , γ(fs ) generate the algebra
(2)
K[Vn0 ]Sn .

4

LEONID BEDRATYUK AND ANNA BEDRATYUK
(2)

Example. Let us consider the case n = 4. The algebra of invariants K[V4 ]S4 is well known,
see [4], and its minimal generating system consists of the following 9 invariants:
1
1
R(x1 ) = (x1 + x2 + x3 + x4 + x5 + x6 ), R(x21 ) = (x21 + x22 + x23 + x24 + x25 + x26 ),
6
6
1
1
R(x1 x6 ) = (x1 x6 + x2 x5 + x3 x4 ), R(x31 ) = (x31 + x32 + x33 + x34 + x35 + x36 ),
3
6
2
2
2
2
2
2
24R(x1 x2 ) = x1 x2 + x1 x3 + x2 x1 + x2 x3 + x3 x1 + x3 2 x2 + x1 2 x4 + x1 2 x5 + x4 2 x1 +
+x4 2 x5 + x5 2 x1 + x5 2 x4 + x2 2 x4 + x2 2 x6 + x4 2 x2 + x4 2 x6 + x6 2 x2 + x6 2 x4 + x3 2 x5 +
+x3 2 x6 + x5 2 x3 + x5 2 x6 + x6 2 x3 + x6 2 x5
1
R(x1 x2 x3 ) = (x1 x3 x2 + x1 x5 x4 + x2 x6 x4 + x3 x6 x5 ),
4
1
1
R(x41 ) = (x41 + x42 + x43 + x44 + x45 + x46 ), R(x51 ) = (x51 + x52 + x53 + x54 + x45 + x56 ),
6
6
3
3
3
3
3
3
24R(x1 x2 ) = x1 x2 + x1 x3 + x2 x1 + x2 x3 + x3 x1 + x3 3 x2 + x1 3 x4 + x1 3 x5 + x4 3 x1 +
+x4 3 x5 + x5 3 x1 + x5 3 x4 + x2 3 x4 + x2 3 x6 + x4 3 x2 + x4 3 x6 + x6 3 x2 + x6 3 x4 + x3 3 x5 +
+x3 3 x6 + x5 3 x3 + x5 3 x6 + x6 3 x3 + x6 2 x5 .
Here
R=

1 X
g
n!
(2)
g∈Sn

(2)

is the Reinolds group action averaging operator which is a projector from K[Vn ] into K[Vn ]Sn .
We have that
γ(R(x51 )) = γ(R(x41 )) = γ(R(x31 )) = γ(R(x21 )) = R(x1 ), γ(R(x21 x2 )) = R(x1 x2 ).
(2)

Therefore, the algebra of invariants K[V40 ]S4 of simple graphs on n vertices is generated by the
4 invariants:
R(x1 ), R(x1 x6 ), R(x1 x2 ), R(x1 , x2 , x3 ).
(2)

So far, the algebra of invariants K[Vn ]Sn is calculated only for n ≤ 5, see [5].
(2)
3. The Poincaré series of the algebra K[Vn0 ]Sn . Let us consider the algebra K[Vn0 ] as a
vector space. Then the following decomposition into the direct sum of its subspaces holds:
K[Vn0 ] = (K[Vn0 ])0 + (K[Vn0 ])1 + · · · + (K[Vn0 ])m ,
where (K[Vn0 ])i is the vector space generated by the elements
xε11 xε22 · · · xεmm , ε1 + ε2 + · · · + εm = i, where εk = 0 or εk = 1.
(2)

Also, for the algebra K[Vn0 ]Sn the decomposition holds:
(2)

(2)

(2)

(2)

K[Vn0 ]Sn = (K[Vn0 ]Sn )0 + (K[Vn0 ]Sn )1 + · · · + (K[Vn0 ]Sn )m .
Since, the Reynolds operator is a projector which save the degree of a polynomial then the
(2)
component (K[Vn0 ]Sn )i is generated by the following elements
R(xε11 xε22 · · · xεmm ).
(2)

(2)

Particularly, we have that (K[Vn0 ]Sn )0 = K. Also, the component (K[Vn0 ]Sn )m has the
dimension 1 and it is generated by the polynomial R(x1 x2 · · · xm ) = x1 x2 · · · xm .

A NEW FORMULA FOR THE GENERATING FUNCTION OF THE NUMBERS OF SIMPLE GRAPHS

5

(2)

Let us now give an interpretation of dim(K[Vn0 ]Sn )i in terms of the graph theory. The
following important theorem holds.
(2)

Theorem 2. The dimension dim(K[Vn0 ]Sn )i equal to the number of non-isomorphic simple
graphs with n vertices and i edges.
(2)

Proof. The Sn -module (K[Vn0 ]/Im )i is generated by the monomials
xε11 xε22 · · · xεmm , ε1 + ε2 + · · · + εm = i, εk = 0 or εk = 1.
(2)

Since the group Sn is finite then the module (K[Vn0 ]/Im )i is decomposed into the direct sum
(2)
of its irreducible Sn -submodules:
(K[Vn0 ])i = M1 ⊕ M2 ⊕ · · · ⊕ Mp .
Each of these submodules has a basis generated by the monomials of the form xε11 xε22 · · · xεmm .
Let us choose for each Mi the corresponding basis monomials m1 , m2 , . . . , mp and consider the
invariants R(m1 ), R(m2 ), . . . , R(mp ). By the construction they are different and linearly inde(2)
(2)
pendent. Therefore the component (K[Vn0 ]Sn )i is the sum of one-dimensional Sn -submodules
(2)

(K[Vn0 ]Sn )i = hR(m1 )i + hR(m2 )i + · · · + hR(mp )i ,
(2)

and dim(K[Vn0 ]Sn )i = p for some p. To each of monomial m1 , m2 , . . . , mp assign a simple graph
in the following way: if mi = xε11 xε22 · · · xεmm then the corresponding simple graph has the form
Gmi = ε1 e1 + ε2 e2 + · · · + εm em .
(2)

Since the monomials m1 , m2 , . . . , mp belong to the different irreducible Sn -modules then Gmi
are non-isomorphic and they exhausted all the possible classes of isomorphic classes of isomorphic graphs with n vertices and i edges.

(2)

Let us recall that the ordinary generating function for the sequence dim(K[Vn0 ]Sn )i
(2)

P(K[Vn0 ]Sn , z) =

m
X

(2)

dim(K[Vn0 ]Sn )i · z i .

i=0

(2)

is called the Poincaré series of the algebra K[Vn0 ]Sn .
The Theorem 2 implies that
(2)

gn (z) = P(K[Vn0 ]Sn , z).
(2)

In the following theorem we derived explicit formulas for the series P(K[Vn0 ]Sn , z) and
(2)
P(K[Vn ]Sn , z).
(2)

Theorem 3. Let the group Sn be realized as m × m matrices. Then
(2)
1 X det(1m − α · z 2 )
0 Sn
(i) P(K[Vn ] , z) =
,
n!
det(1m − α · z)
(2)
α∈Sn
(2)
1 X
1
Sn
(ii) P(K[Vn ] , z) =
.
n!
det(1
−
α
·
z)
m
(2)
α∈Sn

here 1m is the unit m × m matrix.

6

LEONID BEDRATYUK AND ANNA BEDRATYUK
(2)

Proof. (i) The vector space (K[Vn0 ])1 has the basis hx1 , x2 , . . . , xm i and a permutation α ∈ Sn
acts on the (K[Vn0 ])1 by permutation of the basis vectors. Denote this linear operator by Aα .
(2)
Let us expand this operator on the component (K[Vn0 ]Sn )k as endomorphism and denote it by
(2)
(k)
(k)
Aα . Since Aα is endomorphism and acts as a permutation of the basis vectors of (K[Vn0 ]Sn )k
(k)
then the action of the operator Aα is defined correctly.
Let a permutation α be written uniquely as a product of disjoint cycles and let ji (α) be the
number of cycles of length i in the disjoint cycle decomposition of α.
(k)
Now find the track of the operator Aα .
Lemma 1.
Tr(A(i)
α )

X

=

β1 +2β2 +···+mβm =i






ji (α)
j1 (α) j2 (α)
.
···
βi
β2
β1

(i)

Proof. Since the operator Aα acts by permutations of the basis vectors of the vector space
(K[Vn0 ])i that its track equal to the numbers of its fixed point.
(1)
(1)
For i = 1 we have (K[Vn0 ])1 = hx1 , x2 , . . . , xm i and Aα (xs ) = xα−1 (s) . Thus Tr(Aα ) = j1 (α).
(2)
For i = 2 let us find out the number of fixed points of the operator Aα which acts on the
vector space (K[Vn0 ])2 with the basis vectors xi xj , i < j. An arbitrary pair of fixed points of the

(2)
such points. Also,
operator Aα form one fixed point for the operator Aα . Thus we get j1 (α)
2
every transposition define one fixed point. Therefore


j1 (α)
(2)
+ j2 (α).
Tr(Aα ) =
2

(3)
All j1 (α) fixed points of the permutation α generates j1 (α)
fixed points of the operator Aα .
3
(3)
Every fixed point of Aα together with j2 (α) transposition generate one fixed point of Aα . At
(3)
last, each any of 3-cycle of α generates one fixed point for Aα . Then


j1 (α)
(3)
+ j1 (α)j2 (α) + j3 (α).
Tr(Aα ) =
3
Analogously
 
   
α2
α1
α1
(4)
Tr(Aα ) =
+ α1 α3 + α4 .
α2 +
+
2
2
4
In the general case any partition of i
β1 + 2β2 + · · · + mβm = i.
generates

(i)


 


jm (α)
j1 (α) j2 (α)
···
βm
β2
β1

fixed points of the operator Aα . Therefore

 


X
jm (α)
j1 (α) j2 (α)
(i)
.
···
Tr(Aα ) =
βm
β2
β1
β +2β +···+mβ =i
1

Lemma 2.

m
X
i=0

2

m

Tr(Aα(i) )z i = (1 + z)j1 (α) (1 + z 2 )j2 (α) · · · (1 + z m )jm (α) .



A NEW FORMULA FOR THE GENERATING FUNCTION OF THE NUMBERS OF SIMPLE GRAPHS

7

Proof. We have
m
X

=


 


jm (α) i
j1 (α) j2 (α)
z =
···
=
β
β
β
i
2
1
i=0
β1 +2β2 +···+mβm =i

 


X
ji (α) β1 +2β2 +···+mβm
j1 (α) j2 (α)
z
=
···
=
βi
β2
β1
β1 +2β2 +···+mβm =i



 

X
ji (α)
j1 (α) β1 j2 (α)
2 β2
(z m )βm =
(z ) · · ·
z
=
βi
β2
β1
β1 +2β2 +···+mβm =i
!
!
!



m 
m 
m 
X
X
X
j
(α)
j2 (α)
j1 (α) β1
m
(z m )βm =
(z 2 )β2 · · ·
z
β
β
β
m
2
1
β =0
β =0
β =0
X

i
Tr(A(i)
α )z

2

1

= (1 + z)

j1 (α)

m

2 j2 (α)

(1 + z )

· · · (1 + z m )jm (α) .


Lemma 3.

m
X

i
Tr(A(i)
α )z =

i=0

det(1m − Aα · z 2 )
.
det(1m − Aα · z)

Proof. Let λ1 , λ2 , . . . , λm be the eigenvalues of the operator Aα . Since Am!
α is the identity matrix then all eigenvalues λi are roots of unity of orders j1 (α), j2 (α) . . . , jm (α). Therefore the
characteristic polynomial of the operator Aα has the form
det(1m − Aα z) = (1 − λ1 z)(1 − λ2 z) · · · (1 − λn z) = (1 − z)j1 (α) (1 − z 2 )j2 (α) · · · (1 − z m )jm (α) .
Now
m
X

i
j1 (α)
Tr(A(i)
(1 + z 2 )j2 (α) · · · (1 + z m )jm (α) =
α )z = (1 + z)

i=0

=

(1 − z 2 )j1 (α) (1 − z 4 )j2 (α)
(1 − z 2m )jm (α)
det(1m − Aα · z 2 )
·
·
·
=
.
(1 − z)j1 (α) (1 − z 2 )j2 (α)
(1 − z m )jm (α)
det(1m − Aα · z)

(2)

Let us find the dimension of Sn -invariant subspace (K[Vn0 ])i .
Lemma 4.
(2)

dim(K[Vn0 ]Sn )i =
(2)

1 X
Tr(A(i)
α ).
n! α∈G

Proof. The dimension of the subspace (K[Vn0 ]Sn )i is equal to the number of eigenvectors that
(i)
correspond to the eigenvalue 1 and which are common eigenvectors for all operators Aα . Consider the average matrix
1 X (i)
P (i) =
A .
|G| g∈G α
(2)

Since the Reynolds operator is a projector from (K[Vn0 ])i into (K[Vn0 ]Sn )i then it has the only
(2)
eigenvalues 1 and 0. Therefore the dimension of the space (K[Vn0 ]Sn )i is equal to the track of
the matrix P (i) .


8

LEONID BEDRATYUK AND ANNA BEDRATYUK

Taking into account the lemmas stated above we have
(2)
Sn

P(K[Vn0 ]

, z) =

m
X

(2)
Sn

dim(K[Vn0 ]

i=0

=

1 X
n!
(2)
g∈Sn

m
X
i=0



m
X
X
1

 zi =
)i z i =
Tr(A(i)
α )
n! i=0
(2)
α∈Sn

i
Tr(A(i)
α )z

!

=

1 X det(1m − α · z 2 )
.
n!
det(1m − α · z)
(2)
α∈Sn

(ii) It is the Molien formula for the Poincaré series of the algebra invariants of the group


(2)
Sn .

References
[1] Harary F., The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc. 78
(1955), 445-463
[2] Pólya, G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen,
Acta Math 68, 145-254(1937)
[3] Harary F., Palmer E., Graphical Enumeration. Academic Press, New York,1973, 271 p.
[4] Aslaksen H., Chan S.-P., Gulliksen T., Invariants of S4 and the Shape of Sets of Vectors,Appl. Algebra
Eng. Commun. Comput. 7, No.1, 53-57 (1996).
[5] Thiéry N., Algebraic invariants of graphs; a study based on computer exploration. ACM SIGSAM Bulletin,
2000, 34 (3), pp.9-20.
Khmelnitskiy national university, Instytuts’ka, 11, Khmelnits’ky, 29016, Ukraine
E-mail address: leonid.uk@gmal.com

