# Bipartite Graphs Related to Mutually Disjoint S-Permutation Matrices

Authors: Krasimir Yordzhev
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

Some numerical characteristics of bipartite graphs in relation to the problem of finding all disjoint pairs of S-permutation matrices in the generaln2×n2 case are discussed in this paper. All bipartite graphs of the type g=〈Rg∪Cg,Eg〉, where |Rg|=|Cg|=2 or |Rg|=|Cg|=3, are provided. The cardinality of the sets of mutually disjoint S-permutation matrices in both the 4×4 and 9×9 cases is calculated.


---

## Body

## 1.Introduction

Letm be a positive integer. By [m] we denote the set
(1.1)[m]={1,2,…,m}.We let𝒮m denote the symmetric group of order m, that is, the group of all one-to-one mappings of the set [m] to itself. If x∈[m], ρ∈𝒮m, then the image of the element x in the mapping ρ we will denote by ρ(x).Abipartite graph is an ordered triple
(1.2)g=〈Rg,Cg,Eg〉,
where Rg and Cg are nonempty sets such that Rg∩Cg=∅. The elements of Rg∪Cg will be called vertices. The set of edges is Eg⊆Rg×Cg={〈r,c〉∣r∈Rg,c∈Cg}. Multiple edges are not allowed in our considerations.The subject of the present work is bipartite graphs considered up to isomorphism.We refer to [1] or [2] for more details on graph theory.Letn and k be two nonnegative integers, and let 0≤k≤n2. We denote by 𝔊n,k the set of all bipartite graphs of the type g=〈Rg,Cg,Eg〉, considered up to isomorphism, such that |Rg|=|Cg|=n and |Eg|=k.LetPij, 1≤i,j≤n be n2 square n×n matrices, whose entries are elements of the set [n2]= {1,2,…,n2}. The n2×n2 matrix
(1.3)P=[P11P12⋯P1nP21P22⋯P2n⋮⋮⋱⋮Pn1Pn2⋯Pnn]
is called a Sudoku matrix, if every row, every column, and every submatrix Pij, 1≤i,j≤n comprise a permutation of the elements of set [n2], that is, every number s∈{1,2,…,n2} is found just once in each row, column, and submatrix Pij. Submatrices Pij are called blocks of P.Sudoku is a very popular game, and Sudoku matrices are special cases of Latin squares in the class of gerechte designs [3].A matrix is calledbinary if all of its elements are equal to 0 or 1. A square binary matrix is called permutation matrix if in every row and every column there is just one 1.Let us denote byΣn2 the set of all n2×n2 permutation matrices of the following type:
(1.4)A=[A11A12⋯A1nA21A22⋯A2n⋮⋮⋱⋮An1An2⋯Ann],
where for every s,t∈{1,2,…,n}, Ast is a square n×n binary submatrix (block) with only one element equal to 1.The elements ofΣn2 will be called S-permutation matrices.TwoΣn2 matrices A=(aij) and B=(bij), 1≤i,j≤n2 will be called disjoint if there are not elements aij and bij with the same indices such that aij=bij=1.The concept of S-permutation matrix was introduced by Dahl [4] in relation to the popular Sudoku puzzle.Obviously, a squaren2×n2 matrix P with entries from [n2]={1,2,…,n2} is a Sudoku matrix if and only if there are Σn2 matrices A1,A2,…,An2 pairwise disjoint, such that P can be written in the following way:
(1.5)P=1·A1+2·A2+⋯+n2·An2.In [5] Fontana offers an algorithm which returns a random family of n2×n2 mutually disjoint S-permutation matrices, where n=2,3. For n=3, he ran the algorithm 1000 times and found 105 different families of nine mutually disjoint S-permutation matrices. Then, applying (1.5), he decided that there are at least 9!·105=38102400 Sudoku matrices. This number is very small compared with the exact number of 9×9 Sudoku matrices. In [6] it was shown that there are exactly
(1.6)9!·722·27·27704267971=6670903752021072936960
number of 9×9 Sudoku matrices.To evaluate the effectiveness of Fontana's algorithm, it is necessary to calculate the probability of two randomly generated matrices being disjoint. As is proved in [4], the number of S-permutation matrices is equal to
(1.7)|Σn2|=(n!)2n.Thus the question of finding a formula for counting disjoint pairs of S-permutation matrices naturally arises. Such a formula is introduced and verified in [7]. In this paper, we demonstrate this formula to compute the number of disjoint pairs of S-permutation matrices in both the 4 × 4 and 9 × 9 cases.


## 2.A Formula for Counting Disjoint Pairs of S-Permutation Matrices

Letg=〈Rg,Cg,Eg〉∈𝔊n,k for some natural numbers n and k, and let v∈Vg=Rg∪Cg.ByN(v) we denote the set of all vertices of Vg, adjacent with v, that is, u∈N(v) if and only if there is an edge in Eg connecting u and v. If v is an isolated vertex (i.e., there is no edge, incident with v), then by definition N(v)=∅ and degree(v)=|N(v)|=0. If v∈Rg, then obviously N(v)⊆Cg, and if v∈Cg, then N(v)⊆Rg.Letg=〈Rg,Cg,Eg〉∈𝔊n,k, and let u,v∈Vg=Rg∪Cg. We will say that u and v are equivalent, and we will write u~v if N(u)=N(v). If u and v are isolated, then by definition u~v if and only if u and v belong simultaneously to Rg, or Cg. The above introduced relation is obviously an equivalence relation.ByVg/~ we denote the obtained factor set (the set of the equivalence classes) according to relation ~ and let
(2.1)Vg/~={Δ1,Δ2,…,Δs},
where Δi⊆Rg, or Δi⊆Cg,i=1,2,…s, 2≤s≤2n. We put
(2.2)δi=|Δi|,1≤δi≤n,i=1,2,…,s,
and for every g∈𝔊n,k we define multiset (set with repetition)
(2.3)[g]={δ1,δ2,…,δs},
where δ1,δ2,…,δs are natural numbers, obtained by the above described way.Ifz1,z2,…,zn is a permutation of the elements of the set [n]={1,2,…,n} and we shortly denote ρ this permutation, then in this case we denote by ρ(i) the ith element of this permutation, that is, ρ(i)=zi,i=1,2,…,n.The following theorem is proved in [7].Theorem 2.1 (see [7]).
Letn≥2 be a positive integer. Then the number Dn2 of all disjoint ordered pairs of matrices in Σn2 is equal to
(2.4)Dn2=(n!)4n+(n!)2(n+1)∑k=1n2‍(-1)k∑g∈𝔊n,k‍∏v∈Rg∪Cg(n-|N(v)|)!∏δ∈[g]δ!.The numberdn2 of all nonordered pairs of disjoint matrices in Σn2 is equal to
(2.5)dn2=12Dn2.The proof of Theorem2.1 is described in detail in [7], and here we will miss it.In order to apply Theorem2.1 it is necessary to describe all bipartite graphs up to isomorphism g=〈Rg,Cg,Eg〉, where |Rg|=|Cg|=n.Letn and k are positive integers, and let g∈𝔊n,k. We examine the ordered (n+1)-tuple
(2.6)Ψ(g)=〈ψ0(g),ψ1(g),…,ψn(g)〉,
where ψi(g), i=0,1,…,n is equal to the number of vertices of g incident with exactly i number of edges. It is obvious that ∑i=1n‍iψi(g)=2k is true for all g∈𝔊n,k. Then formula (2.4) can be presented as
(2.7)Dn2=(n!)4n+(n!)2(n+1)∑k=1n2‍(-1)k∑g∈𝔊n,k‍∏i=0n[(n-i)!]ψi(g)∏δ∈[g]δ!.Since(n-n)!=0!=1 and [n-(n-1)]!=1!=1, then
(2.8)Dn2=(n!)4n+(n!)2(n+1)∑k=1n2‍(-1)k∑g∈𝔊n,k‍∏i=0n-2[(n-i)!]ψi(g)∏δ∈[g]δ!.Consequently, to apply formula (2.8) for each bipartite graph g∈𝔊n,k and for the set 𝔊n,k of bipartite graphs, it is necessary to obtain the following numerical characteristics:
(2.9)ω(g)=∏i=0n-2[(n-i)!]ψi(g)∏δ∈[g]δ!,θ(n,k)=∑g∈𝔊n,k‍ω(g).Using the numerical characteristics (2.9), we obtain the following variety of Theorem 2.1.Theorem 2.2.
One has(2.10)Dn2=(n!)4n+(n!)2(n+1)∑k=1n2‍(-1)kθ(n,k),
where θ(n,k) is described using formulas (2.9).


## 3.Demonstrations in Applying Theorem2.2

### 3.1.Counting the NumberD4of All Ordered Pairs of Disjoint S-Permutation Matrices forn=2

#### 3.1.1. Considerk=1

Inn=2 and k=1, 𝔊2,1 consists of a single graph g1 shown in Figure 1.Figure 1
n
=
2
,
k
=
1.For graphg1∈𝔊2,1 we have
(3.1)[g1]={1,1,1,1},Ψ(g1)=〈ψ0(g1),ψ1(g1),ψ2(g1)〉=〈2,2,0〉.Then we get(3.2)ω(g1)=[(2-0)!]21!1!1!1!=4,
and therefore
(3.3)θ(2,1)=∑g∈𝔊2,1‍ω(g)=4.


#### 3.1.2. Considerk=2

The set𝔊2,2 consists of three graphs g2, g3, and g4 depicted in Figure 2.Figure 2
n
=
2
,
k
=
2.For graphg2∈𝔊2,2 we have
(3.4)[g2]={1,1,1,1},Ψ(g2)=〈ψ0(g2),ψ1(g2),ψ2(g2)〉=〈0,4,0〉,ω(g1)=[(2-0)!]01!1!1!1!=1.For graphsg3∈𝔊2,2 and g4∈𝔊2,2 we have
(3.5)[g3]=[g4]={2,1,1},Ψ(g3)=Ψ(g4)=〈1,2,1〉,ω(g3)=ω(g4)=[(2-0)!]12!1!1!=1.Then for the set𝔊2,2 we get
(3.6)θ(2,2)=∑g∈𝔊2,2‍ω(g)=1+1+1=3.


#### 3.1.3. Considerk=3

Inn=2 and k=3, 𝔊2,3 consists of a single graph g5 shown in Figure 3.Figure 3
n
=
2
,
k
=
3.For graphg5∈𝔊2,3 we have
(3.7)[g5]={1,1,1,1},Ψ(g5)=〈ψ0(g5),ψ1(g5),ψ2(g5)〉=〈0,2,2〉.Then we get(3.8)ω(g5)=[(2-0)!]01!1!1!1!=1
and therefore
(3.9)θ(2,3)=∑g∈𝔊2,3‍ω(g)=1.


#### 3.1.4. Considerk=4

Whenn=2 and k=4, there is only one graph, and this is the complete bipartite graph g6 which is shown in Figure 4.Figure 4
n
=
2
,
k
=
4.For graphg6∈𝔊2,4 we have
(3.10)[g6]={2,2},Ψ(g6)=〈ψ0(g6),ψ1(g6),ψ2(g6)〉=〈0,0,4〉.Then we get(3.11)ω(g6)=[(2-0)!]02!2!=14,
and therefore
(3.12)θ(2,4)=∑g∈𝔊2,1‍ω(g)=14.Having in mind the formulas (2.10), (3.3), (3.6), (3.9), and (3.12) for the number D4 of all ordered pairs disjoint S-permutation matrices in n=2 we finally get
(3.13)D4=(2!)8+(2!)6[-θ(2,1)+θ(2,2)-θ(2,3)+θ(2,4)]=256+64(-4+3-1+14)=144.The numberd4 of all nonordered pairs disjoint matrices from Σ4 is equal to
(3.14)d4=12D4=72.


### 3.2.Counting the NumberD9of All Ordered Pairs of Disjoint S-Permutation Matrices forn=3

#### 3.2.1. Considerk=1

Graphg7, which is displayed in Figure 5, is the only bipartite graph belonging to the set 𝔊3,1.Figure 5
n
=
3, k=1.For graphg7∈𝔊3,1 we have
(3.15)[g7]={1,1,2,2},Ψ(g7)=〈ψ0(g7),ψ1(g7),ψ2(g7),ψ3(g7),ψ4(g8)〉=〈4,2,0,0〉.Then we get(3.16)ω(g7)=[(3-0)!]4[(3-1)!]21!1!2!2!=64·221·1·2·2=1296,
and therefore
(3.17)θ(3,1)=∑g∈𝔊3,1‍ω(g)=1296.


#### 3.2.2. Considerk=2

In this case𝔊3,2={g8,g9,g10}. The graphs g8, g9, and g10 are shown in Figure 6.Figure 6
n
=
3
,
k
=
2.For graphg8∈𝔊3,2 we have
(3.18)[g8]={1,1,1,1,1,1},Ψ(g8)=〈ψ0(g8),ψ1(g8),ψ2(g8),ψ3(g8),ψ4(g8)〉=〈2,4,0,0〉,ω(g8)=[(3-0)!]2[(3-1)!]41!1!1!1!1!1!=62·24=576.For graphsg9∈𝔊3,2 and g10∈𝔊3,2 we have
(3.19)[g9]=[g10]={1,1,2,2},Ψ(g9)=Ψ(g10)=〈3,2,1,0〉,ω(g9)=ω(g10)=[(3-0)!]3[(3-1)!]21!1!2!2!=63·221·1·2·2=216.Then for the set𝔊3,2 we get
(3.20)θ(3,2)=∑g∈𝔊3,2‍ω(g)=576+216+216=1008.


#### 3.2.3. Considerk=3

Whenn=3 and k=3, the set 𝔊3,3={g11,g12,g13,g14,g15,g16} consists of six bipartite graphs, which are shown in Figure 7.Figure 7
n
=
3, k=3.For graphg11∈𝔊3,3 we have
(3.21)[g11]={1,1,1,1,1,1},Ψ(g11)=〈0,6,0,0〉,ω(g11)=[(3-0)!]0[(3-1)!]61!1!1!1!1!1!=60·26=64.For graphsg12,g13∈𝔊3,3 we have
(3.22)[g12]=[g13]={1,1,1,1,2},Ψ(g12)=Ψ(g13)=〈1,4,1,0〉,ω(g12)=ω(g13)=[(3-0)!]1[(3-1)!]41!1!1!1!2!=61·242=48.For graphg14∈𝔊3,3 we have
(3.23)[g14]={1,1,1,1,1,1},Ψ(g14)=〈2,2,2,0〉,ω(g14)=[(3-0)!]2[(3-1)!]21!1!1!1!1!1!=62·22=144.For graphsg15,g16∈𝔊3,3 we have
(3.24)[g15]=[g16]={1,2,3},Ψ(g15)=Ψ(g16)=〈2,3,0,1〉,ω(g15)=ω(g16)=[(3-0)!]2[(3-1)!]31!2!3!=62·232·6=24.Then for the set𝔊3,3 we get
(3.25)θ(3,3)=∑g∈𝔊3,3‍ω(g)=64+48+48+144+24+24=352.


#### 3.2.4. Considerk=4

Whenn=3 and k=4, the set 𝔊3,4={g17,g18,g19,g20,g21,g22,g23} consists of seven bipartite graphs, which are shown in Figure 8.Figure 8
n
=
3, k=4.For graphg17∈𝔊3,4 we have
(3.26)[g17]={1,1,2,2},Ψ(g17)=〈2,0,4,0〉,ω(g17)=[(3-0)!]2[(3-1)!]01!1!2!2!=62·2022=9.For graphg18∈𝔊3,4 we have
(3.27)[g18]={1,1,2,2},Ψ(g18)=〈0,4,2,0〉,ω(g18)=[(3-0)!]0[(3-1)!]41!1!2!2!=60·2422=4.For graphg19∈𝔊3,4 we have
(3.28)[g19]={1,1,1,1,1,1},Ψ(g19)=〈0,4,2,0〉,ω(g19)=[(3-0)!]0[(3-1)!]41!1!1!1!1!1!=60·24=16.For graphsg20∈𝔊3,4 and g21∈𝔊3,4 we have
(3.29)[g20]=[g21]={1,1,1,1,1,1},Ψ(g20)=Ψ(g21)=〈1,2,3,0〉,ω(g20)=ω(g21)=[(3-0)!]1[(3-1)!]21!1!1!1!1!1!=61·22=24.For graphsg22∈𝔊3,4 and g23∈𝔊3,4 we have
(3.30)[g22]=[g23]={1,1,1,1,2},Ψ(g22)=Ψ(g23)=〈1,3,1,1〉,ω(g22)=ω(g23)=[(3-0)!]1[(3-1)!]31!1!1!1!2!=61·232=24.Then we get(3.31)θ(3,4)=∑g∈𝔊3,4‍ω(g)=9+4+16+24+24+24+24=125.


#### 3.2.5. Considerk=5

Whenn=3 and k=5, the set 𝔊3,5 consists of seven bipartite graphs g24÷g30, which are shown in Figure 9.Figure 9
n
=
3, k=5.For graphg24∈𝔊3,5 we have
(3.32)[g24]={1,1,2,2},Ψ(g24)=〈0,4,0,2〉,ω(g18)=[(3-0)!]0[(3-1)!]41!1!2!2!=60·2422=4.For graphg25∈𝔊3,5 we have
(3.33)[g25]={1,1,2,2},Ψ(g25)=〈0,2,4,0〉,ω(g18)=[(3-0)!]0[(3-1)!]21!1!2!2!=60·2222=1.For graphg26∈𝔊3,5 we have
(3.34)[g26]={1,1,1,1,1,1},Ψ(g26)=〈0,2,4,0〉,ω(g26)=[(3-0)!]0[(3-1)!]21!1!1!1!1!1!=60·22=4.For graphsg27∈𝔊3,5 and g28∈𝔊3,5 we have
(3.35)[g27]=[g28]={1,1,1,1,1,1},Ψ(g27)=Ψ(g28)=〈0,3,2,1〉,ω(g27)=ω(g28)=[(3-0)!]0[(3-1)!]31!1!1!1!1!1!=60·23=8.For graphsg29∈𝔊3,5 and g30∈𝔊3,5 we have
(3.36)[g29]=[g30]={1,1,1,1,2},Ψ(g29)=Ψ(g30)=〈1,1,3,1〉,ω(g29)=ω(g30)=[(3-0)!]1[(3-1)!]11!1!1!1!2!=61·212=6.Then we get(3.37)θ(3,5)=∑g∈𝔊3,5‍ω(g)=4+1+4+8+8+6+6=37.


#### 3.2.6. Considerk=6

Whenn=3 and k=6, the set 𝔊3,6={g31,g32,g33,g34,g35,g36} consists of six bipartite graphs, which are shown in Figure 10.Figure 10
n
=
3, k=6.For graphg31∈𝔊3,6 we have
(3.38)[g31]={1,1,1,1,1,1},Ψ(g31)=〈0,0,6,0〉,ω(g31)=[(3-0)!]0[(3-1)!]01!1!1!1!1!1!=1.For graphsg32∈𝔊3,6 and g33∈𝔊3,6 we have
(3.39)[g32]=[g33]={1,1,1,1,2},Ψ(g32)=Ψ(g33)=〈0,1,4,1〉,ω(g32)=ω(g33)=[(3-0)!]0[(3-1)!]11!1!1!1!2!=60·212=1.For graphg34∈𝔊3,6 we have
(3.40)[g34]={1,1,1,1,1,1},Ψ(g34)=〈0,2,2,2〉,ω(g34)=[(3-0)!]0[(3-1)!]21!1!1!1!1!1!=60·221=4.For graphsg35∈𝔊3,6 and g36∈𝔊3,6 we have
(3.41)[g35]=[g36]={1,2,3},Ψ(g35)=Ψ(g36)=〈1,0,3,2〉,ω(g35)=ω(g36)=[(3-0)!]1[(3-1)!]01!2!3!=61·202·6=12.Then for the set𝔊3,6 we get
(3.42)θ(3,6)=∑g∈𝔊3,6‍ω(g)=1+1+1+4+12+12=8.


#### 3.2.7. Considerk=7

Whenn=3 and k=7 the set 𝔊3,7={g37,g38,g39} consists of three bipartite graphs, which are shown in Figure 11.Figure 11
n
=
3, k=7.For graphg37∈𝔊3,7 it is true that
(3.43)[g37]={1,1,1,1,1,1},Ψ(g37)=〈0,0,4,2〉,ω(g37)=[(3-0)!]0[(3-1)!]01!1!1!1!1!1!=60·201=1.For graphsg38∈𝔊3,7 and g39∈𝔊3,7 we get
(3.44)[g38]=[g39]={1,1,2,2},Ψ(g38)=Ψ(g39)=〈0,1,2,3〉,ω(g38)=ω(g39)=[(3-0)!]0[(3-1)!]11!1!2!2!=60·2122=12.Then for the set𝔊3,7 we get
(3.45)θ(3,7)=∑g∈𝔊3,7‍ω(g)=1+12+12=2.


#### 3.2.8. Considerk=8

Graphg40, which is displayed in Figure 12, is the only bipartite graph belonging to the set 𝔊3,8 in the case n=3 and k=8.Figure 12
n
=
3, k=8.For graphg40∈𝔊3,8 it is true that
(3.46)[g40]={1,1,2,2},Ψ(g40)=〈0,0,2,4〉,ω(g40)=[(3-0)!]0[(3-1)!]01!1!2!2!=60·2022=14.Therefore,(3.47)θ(3,8)=∑g∈𝔊3,8‍ω(g)=14.


#### 3.2.9. Considerk=9

Whenn=3 and k=9 there is only one graph, and this is the complete bipartite graph g41 which is shown in Figure 13.Figure 13
n
=
3, k=9.For graphg41 it is true that
(3.48)[g41]={3,3},Ψ(g41)=〈0,0,0,6〉,ω(g41)=[(3-0)!]0[(3-1)!]03!3!=60·2062=136.Therefore(3.49)θ(3,9)=∑g∈𝔊3,9‍ω(g)=136.Having in mind the formula (2.10) and formulas (3.17) ÷ (3.49) for the number D9 of all ordered pairs disjoint S-permutation matrices in n=3 we finally get
(3.50)D9=(3!)12+(3!)8[∑k=19‍(-1)kθ(n,k)]=2176782336+1679616(-1296+1008-352+125-37+8-2+14-136)=1260085248.The numberd9 of all nonordered pairs disjoint matrices from Σ9 is equal to
(3.51)d9=12D9=630042624.


### 3.3.On a Combinatorial Problem of Graph Theory Related to the Number of Sudoku Matrices

Problem. Let n≥2 be a natural number, and let G be a simple graph having (n!)2n vertices. Let each vertex of G be identified with an element of the set Σn2 of all n2×n2 S-permutation matrices. Two vertices are connected by an edge if and only if the corresponding matrices are disjoint. The problem is to find the number of all complete subgraphs of G having n2 vertices.Note that the number of edges in graphG is equal to dn2 and can be calculated using formulas (2.4) and (2.5) (resp., formulas (2.9), (2.10), and (2.5)).Denote byzn the solution of the Problem 1, and let σn be the number of all n2×n2 Sudoku matrices. Then according to formula (1.5) and the method of construction of the graph G, it follows that the next equality is valid:
(3.52)zn=σn(n2)!.We do not know a general formula for finding the number of alln2×n2 Sudoku matrices for each natural number n≥2, and we consider that this is an open combinatorial problem. Only some special cases are known. For example in n=2 it is known that σ2=288 [8]. Then according to formula (3.52) we get
(3.53)z2=σ24!=28824=12.In [6] it has been shown that in n=3 there are exactly,
(3.54)σ3=6670903752021072936960=9!×722×27×27704267971=220×38×51×71×277042679711~6.671×1021,
a number of Sudoku matrices. Then according to formula (3.52) we get
(3.55)z3=σ39!=6670903752021072936960362880=18383222420692992.


## 3.1.Counting the NumberD4of All Ordered Pairs of Disjoint S-Permutation Matrices forn=2

### 3.1.1. Considerk=1

Inn=2 and k=1, 𝔊2,1 consists of a single graph g1 shown in Figure 1.Figure 1
n
=
2
,
k
=
1.For graphg1∈𝔊2,1 we have
(3.1)[g1]={1,1,1,1},Ψ(g1)=〈ψ0(g1),ψ1(g1),ψ2(g1)〉=〈2,2,0〉.Then we get(3.2)ω(g1)=[(2-0)!]21!1!1!1!=4,
and therefore
(3.3)θ(2,1)=∑g∈𝔊2,1‍ω(g)=4.


### 3.1.2. Considerk=2

The set𝔊2,2 consists of three graphs g2, g3, and g4 depicted in Figure 2.Figure 2
n
=
2
,
k
=
2.For graphg2∈𝔊2,2 we have
(3.4)[g2]={1,1,1,1},Ψ(g2)=〈ψ0(g2),ψ1(g2),ψ2(g2)〉=〈0,4,0〉,ω(g1)=[(2-0)!]01!1!1!1!=1.For graphsg3∈𝔊2,2 and g4∈𝔊2,2 we have
(3.5)[g3]=[g4]={2,1,1},Ψ(g3)=Ψ(g4)=〈1,2,1〉,ω(g3)=ω(g4)=[(2-0)!]12!1!1!=1.Then for the set𝔊2,2 we get
(3.6)θ(2,2)=∑g∈𝔊2,2‍ω(g)=1+1+1=3.


### 3.1.3. Considerk=3

Inn=2 and k=3, 𝔊2,3 consists of a single graph g5 shown in Figure 3.Figure 3
n
=
2
,
k
=
3.For graphg5∈𝔊2,3 we have
(3.7)[g5]={1,1,1,1},Ψ(g5)=〈ψ0(g5),ψ1(g5),ψ2(g5)〉=〈0,2,2〉.Then we get(3.8)ω(g5)=[(2-0)!]01!1!1!1!=1
and therefore
(3.9)θ(2,3)=∑g∈𝔊2,3‍ω(g)=1.


### 3.1.4. Considerk=4

Whenn=2 and k=4, there is only one graph, and this is the complete bipartite graph g6 which is shown in Figure 4.Figure 4
n
=
2
,
k
=
4.For graphg6∈𝔊2,4 we have
(3.10)[g6]={2,2},Ψ(g6)=〈ψ0(g6),ψ1(g6),ψ2(g6)〉=〈0,0,4〉.Then we get(3.11)ω(g6)=[(2-0)!]02!2!=14,
and therefore
(3.12)θ(2,4)=∑g∈𝔊2,1‍ω(g)=14.Having in mind the formulas (2.10), (3.3), (3.6), (3.9), and (3.12) for the number D4 of all ordered pairs disjoint S-permutation matrices in n=2 we finally get
(3.13)D4=(2!)8+(2!)6[-θ(2,1)+θ(2,2)-θ(2,3)+θ(2,4)]=256+64(-4+3-1+14)=144.The numberd4 of all nonordered pairs disjoint matrices from Σ4 is equal to
(3.14)d4=12D4=72.


## 3.1.1. Considerk=1

Inn=2 and k=1, 𝔊2,1 consists of a single graph g1 shown in Figure 1.Figure 1
n
=
2
,
k
=
1.For graphg1∈𝔊2,1 we have
(3.1)[g1]={1,1,1,1},Ψ(g1)=〈ψ0(g1),ψ1(g1),ψ2(g1)〉=〈2,2,0〉.Then we get(3.2)ω(g1)=[(2-0)!]21!1!1!1!=4,
and therefore
(3.3)θ(2,1)=∑g∈𝔊2,1‍ω(g)=4.


## 3.1.2. Considerk=2

The set𝔊2,2 consists of three graphs g2, g3, and g4 depicted in Figure 2.Figure 2
n
=
2
,
k
=
2.For graphg2∈𝔊2,2 we have
(3.4)[g2]={1,1,1,1},Ψ(g2)=〈ψ0(g2),ψ1(g2),ψ2(g2)〉=〈0,4,0〉,ω(g1)=[(2-0)!]01!1!1!1!=1.For graphsg3∈𝔊2,2 and g4∈𝔊2,2 we have
(3.5)[g3]=[g4]={2,1,1},Ψ(g3)=Ψ(g4)=〈1,2,1〉,ω(g3)=ω(g4)=[(2-0)!]12!1!1!=1.Then for the set𝔊2,2 we get
(3.6)θ(2,2)=∑g∈𝔊2,2‍ω(g)=1+1+1=3.


## 3.1.3. Considerk=3

Inn=2 and k=3, 𝔊2,3 consists of a single graph g5 shown in Figure 3.Figure 3
n
=
2
,
k
=
3.For graphg5∈𝔊2,3 we have
(3.7)[g5]={1,1,1,1},Ψ(g5)=〈ψ0(g5),ψ1(g5),ψ2(g5)〉=〈0,2,2〉.Then we get(3.8)ω(g5)=[(2-0)!]01!1!1!1!=1
and therefore
(3.9)θ(2,3)=∑g∈𝔊2,3‍ω(g)=1.


## 3.1.4. Considerk=4

Whenn=2 and k=4, there is only one graph, and this is the complete bipartite graph g6 which is shown in Figure 4.Figure 4
n
=
2
,
k
=
4.For graphg6∈𝔊2,4 we have
(3.10)[g6]={2,2},Ψ(g6)=〈ψ0(g6),ψ1(g6),ψ2(g6)〉=〈0,0,4〉.Then we get(3.11)ω(g6)=[(2-0)!]02!2!=14,
and therefore
(3.12)θ(2,4)=∑g∈𝔊2,1‍ω(g)=14.Having in mind the formulas (2.10), (3.3), (3.6), (3.9), and (3.12) for the number D4 of all ordered pairs disjoint S-permutation matrices in n=2 we finally get
(3.13)D4=(2!)8+(2!)6[-θ(2,1)+θ(2,2)-θ(2,3)+θ(2,4)]=256+64(-4+3-1+14)=144.The numberd4 of all nonordered pairs disjoint matrices from Σ4 is equal to
(3.14)d4=12D4=72.


## 3.2.Counting the NumberD9of All Ordered Pairs of Disjoint S-Permutation Matrices forn=3

### 3.2.1. Considerk=1

Graphg7, which is displayed in Figure 5, is the only bipartite graph belonging to the set 𝔊3,1.Figure 5
n
=
3, k=1.For graphg7∈𝔊3,1 we have
(3.15)[g7]={1,1,2,2},Ψ(g7)=〈ψ0(g7),ψ1(g7),ψ2(g7),ψ3(g7),ψ4(g8)〉=〈4,2,0,0〉.Then we get(3.16)ω(g7)=[(3-0)!]4[(3-1)!]21!1!2!2!=64·221·1·2·2=1296,
and therefore
(3.17)θ(3,1)=∑g∈𝔊3,1‍ω(g)=1296.


### 3.2.2. Considerk=2

In this case𝔊3,2={g8,g9,g10}. The graphs g8, g9, and g10 are shown in Figure 6.Figure 6
n
=
3
,
k
=
2.For graphg8∈𝔊3,2 we have
(3.18)[g8]={1,1,1,1,1,1},Ψ(g8)=〈ψ0(g8),ψ1(g8),ψ2(g8),ψ3(g8),ψ4(g8)〉=〈2,4,0,0〉,ω(g8)=[(3-0)!]2[(3-1)!]41!1!1!1!1!1!=62·24=576.For graphsg9∈𝔊3,2 and g10∈𝔊3,2 we have
(3.19)[g9]=[g10]={1,1,2,2},Ψ(g9)=Ψ(g10)=〈3,2,1,0〉,ω(g9)=ω(g10)=[(3-0)!]3[(3-1)!]21!1!2!2!=63·221·1·2·2=216.Then for the set𝔊3,2 we get
(3.20)θ(3,2)=∑g∈𝔊3,2‍ω(g)=576+216+216=1008.


### 3.2.3. Considerk=3

Whenn=3 and k=3, the set 𝔊3,3={g11,g12,g13,g14,g15,g16} consists of six bipartite graphs, which are shown in Figure 7.Figure 7
n
=
3, k=3.For graphg11∈𝔊3,3 we have
(3.21)[g11]={1,1,1,1,1,1},Ψ(g11)=〈0,6,0,0〉,ω(g11)=[(3-0)!]0[(3-1)!]61!1!1!1!1!1!=60·26=64.For graphsg12,g13∈𝔊3,3 we have
(3.22)[g12]=[g13]={1,1,1,1,2},Ψ(g12)=Ψ(g13)=〈1,4,1,0〉,ω(g12)=ω(g13)=[(3-0)!]1[(3-1)!]41!1!1!1!2!=61·242=48.For graphg14∈𝔊3,3 we have
(3.23)[g14]={1,1,1,1,1,1},Ψ(g14)=〈2,2,2,0〉,ω(g14)=[(3-0)!]2[(3-1)!]21!1!1!1!1!1!=62·22=144.For graphsg15,g16∈𝔊3,3 we have
(3.24)[g15]=[g16]={1,2,3},Ψ(g15)=Ψ(g16)=〈2,3,0,1〉,ω(g15)=ω(g16)=[(3-0)!]2[(3-1)!]31!2!3!=62·232·6=24.Then for the set𝔊3,3 we get
(3.25)θ(3,3)=∑g∈𝔊3,3‍ω(g)=64+48+48+144+24+24=352.


### 3.2.4. Considerk=4

Whenn=3 and k=4, the set 𝔊3,4={g17,g18,g19,g20,g21,g22,g23} consists of seven bipartite graphs, which are shown in Figure 8.Figure 8
n
=
3, k=4.For graphg17∈𝔊3,4 we have
(3.26)[g17]={1,1,2,2},Ψ(g17)=〈2,0,4,0〉,ω(g17)=[(3-0)!]2[(3-1)!]01!1!2!2!=62·2022=9.For graphg18∈𝔊3,4 we have
(3.27)[g18]={1,1,2,2},Ψ(g18)=〈0,4,2,0〉,ω(g18)=[(3-0)!]0[(3-1)!]41!1!2!2!=60·2422=4.For graphg19∈𝔊3,4 we have
(3.28)[g19]={1,1,1,1,1,1},Ψ(g19)=〈0,4,2,0〉,ω(g19)=[(3-0)!]0[(3-1)!]41!1!1!1!1!1!=60·24=16.For graphsg20∈𝔊3,4 and g21∈𝔊3,4 we have
(3.29)[g20]=[g21]={1,1,1,1,1,1},Ψ(g20)=Ψ(g21)=〈1,2,3,0〉,ω(g20)=ω(g21)=[(3-0)!]1[(3-1)!]21!1!1!1!1!1!=61·22=24.For graphsg22∈𝔊3,4 and g23∈𝔊3,4 we have
(3.30)[g22]=[g23]={1,1,1,1,2},Ψ(g22)=Ψ(g23)=〈1,3,1,1〉,ω(g22)=ω(g23)=[(3-0)!]1[(3-1)!]31!1!1!1!2!=61·232=24.Then we get(3.31)θ(3,4)=∑g∈𝔊3,4‍ω(g)=9+4+16+24+24+24+24=125.


### 3.2.5. Considerk=5

Whenn=3 and k=5, the set 𝔊3,5 consists of seven bipartite graphs g24÷g30, which are shown in Figure 9.Figure 9
n
=
3, k=5.For graphg24∈𝔊3,5 we have
(3.32)[g24]={1,1,2,2},Ψ(g24)=〈0,4,0,2〉,ω(g18)=[(3-0)!]0[(3-1)!]41!1!2!2!=60·2422=4.For graphg25∈𝔊3,5 we have
(3.33)[g25]={1,1,2,2},Ψ(g25)=〈0,2,4,0〉,ω(g18)=[(3-0)!]0[(3-1)!]21!1!2!2!=60·2222=1.For graphg26∈𝔊3,5 we have
(3.34)[g26]={1,1,1,1,1,1},Ψ(g26)=〈0,2,4,0〉,ω(g26)=[(3-0)!]0[(3-1)!]21!1!1!1!1!1!=60·22=4.For graphsg27∈𝔊3,5 and g28∈𝔊3,5 we have
(3.35)[g27]=[g28]={1,1,1,1,1,1},Ψ(g27)=Ψ(g28)=〈0,3,2,1〉,ω(g27)=ω(g28)=[(3-0)!]0[(3-1)!]31!1!1!1!1!1!=60·23=8.For graphsg29∈𝔊3,5 and g30∈𝔊3,5 we have
(3.36)[g29]=[g30]={1,1,1,1,2},Ψ(g29)=Ψ(g30)=〈1,1,3,1〉,ω(g29)=ω(g30)=[(3-0)!]1[(3-1)!]11!1!1!1!2!=61·212=6.Then we get(3.37)θ(3,5)=∑g∈𝔊3,5‍ω(g)=4+1+4+8+8+6+6=37.


### 3.2.6. Considerk=6

Whenn=3 and k=6, the set 𝔊3,6={g31,g32,g33,g34,g35,g36} consists of six bipartite graphs, which are shown in Figure 10.Figure 10
n
=
3, k=6.For graphg31∈𝔊3,6 we have
(3.38)[g31]={1,1,1,1,1,1},Ψ(g31)=〈0,0,6,0〉,ω(g31)=[(3-0)!]0[(3-1)!]01!1!1!1!1!1!=1.For graphsg32∈𝔊3,6 and g33∈𝔊3,6 we have
(3.39)[g32]=[g33]={1,1,1,1,2},Ψ(g32)=Ψ(g33)=〈0,1,4,1〉,ω(g32)=ω(g33)=[(3-0)!]0[(3-1)!]11!1!1!1!2!=60·212=1.For graphg34∈𝔊3,6 we have
(3.40)[g34]={1,1,1,1,1,1},Ψ(g34)=〈0,2,2,2〉,ω(g34)=[(3-0)!]0[(3-1)!]21!1!1!1!1!1!=60·221=4.For graphsg35∈𝔊3,6 and g36∈𝔊3,6 we have
(3.41)[g35]=[g36]={1,2,3},Ψ(g35)=Ψ(g36)=〈1,0,3,2〉,ω(g35)=ω(g36)=[(3-0)!]1[(3-1)!]01!2!3!=61·202·6=12.Then for the set𝔊3,6 we get
(3.42)θ(3,6)=∑g∈𝔊3,6‍ω(g)=1+1+1+4+12+12=8.


### 3.2.7. Considerk=7

Whenn=3 and k=7 the set 𝔊3,7={g37,g38,g39} consists of three bipartite graphs, which are shown in Figure 11.Figure 11
n
=
3, k=7.For graphg37∈𝔊3,7 it is true that
(3.43)[g37]={1,1,1,1,1,1},Ψ(g37)=〈0,0,4,2〉,ω(g37)=[(3-0)!]0[(3-1)!]01!1!1!1!1!1!=60·201=1.For graphsg38∈𝔊3,7 and g39∈𝔊3,7 we get
(3.44)[g38]=[g39]={1,1,2,2},Ψ(g38)=Ψ(g39)=〈0,1,2,3〉,ω(g38)=ω(g39)=[(3-0)!]0[(3-1)!]11!1!2!2!=60·2122=12.Then for the set𝔊3,7 we get
(3.45)θ(3,7)=∑g∈𝔊3,7‍ω(g)=1+12+12=2.


### 3.2.8. Considerk=8

Graphg40, which is displayed in Figure 12, is the only bipartite graph belonging to the set 𝔊3,8 in the case n=3 and k=8.Figure 12
n
=
3, k=8.For graphg40∈𝔊3,8 it is true that
(3.46)[g40]={1,1,2,2},Ψ(g40)=〈0,0,2,4〉,ω(g40)=[(3-0)!]0[(3-1)!]01!1!2!2!=60·2022=14.Therefore,(3.47)θ(3,8)=∑g∈𝔊3,8‍ω(g)=14.


### 3.2.9. Considerk=9

Whenn=3 and k=9 there is only one graph, and this is the complete bipartite graph g41 which is shown in Figure 13.Figure 13
n
=
3, k=9.For graphg41 it is true that
(3.48)[g41]={3,3},Ψ(g41)=〈0,0,0,6〉,ω(g41)=[(3-0)!]0[(3-1)!]03!3!=60·2062=136.Therefore(3.49)θ(3,9)=∑g∈𝔊3,9‍ω(g)=136.Having in mind the formula (2.10) and formulas (3.17) ÷ (3.49) for the number D9 of all ordered pairs disjoint S-permutation matrices in n=3 we finally get
(3.50)D9=(3!)12+(3!)8[∑k=19‍(-1)kθ(n,k)]=2176782336+1679616(-1296+1008-352+125-37+8-2+14-136)=1260085248.The numberd9 of all nonordered pairs disjoint matrices from Σ9 is equal to
(3.51)d9=12D9=630042624.


## 3.2.1. Considerk=1

Graphg7, which is displayed in Figure 5, is the only bipartite graph belonging to the set 𝔊3,1.Figure 5
n
=
3, k=1.For graphg7∈𝔊3,1 we have
(3.15)[g7]={1,1,2,2},Ψ(g7)=〈ψ0(g7),ψ1(g7),ψ2(g7),ψ3(g7),ψ4(g8)〉=〈4,2,0,0〉.Then we get(3.16)ω(g7)=[(3-0)!]4[(3-1)!]21!1!2!2!=64·221·1·2·2=1296,
and therefore
(3.17)θ(3,1)=∑g∈𝔊3,1‍ω(g)=1296.


## 3.2.2. Considerk=2

In this case𝔊3,2={g8,g9,g10}. The graphs g8, g9, and g10 are shown in Figure 6.Figure 6
n
=
3
,
k
=
2.For graphg8∈𝔊3,2 we have
(3.18)[g8]={1,1,1,1,1,1},Ψ(g8)=〈ψ0(g8),ψ1(g8),ψ2(g8),ψ3(g8),ψ4(g8)〉=〈2,4,0,0〉,ω(g8)=[(3-0)!]2[(3-1)!]41!1!1!1!1!1!=62·24=576.For graphsg9∈𝔊3,2 and g10∈𝔊3,2 we have
(3.19)[g9]=[g10]={1,1,2,2},Ψ(g9)=Ψ(g10)=〈3,2,1,0〉,ω(g9)=ω(g10)=[(3-0)!]3[(3-1)!]21!1!2!2!=63·221·1·2·2=216.Then for the set𝔊3,2 we get
(3.20)θ(3,2)=∑g∈𝔊3,2‍ω(g)=576+216+216=1008.


## 3.2.3. Considerk=3

Whenn=3 and k=3, the set 𝔊3,3={g11,g12,g13,g14,g15,g16} consists of six bipartite graphs, which are shown in Figure 7.Figure 7
n
=
3, k=3.For graphg11∈𝔊3,3 we have
(3.21)[g11]={1,1,1,1,1,1},Ψ(g11)=〈0,6,0,0〉,ω(g11)=[(3-0)!]0[(3-1)!]61!1!1!1!1!1!=60·26=64.For graphsg12,g13∈𝔊3,3 we have
(3.22)[g12]=[g13]={1,1,1,1,2},Ψ(g12)=Ψ(g13)=〈1,4,1,0〉,ω(g12)=ω(g13)=[(3-0)!]1[(3-1)!]41!1!1!1!2!=61·242=48.For graphg14∈𝔊3,3 we have
(3.23)[g14]={1,1,1,1,1,1},Ψ(g14)=〈2,2,2,0〉,ω(g14)=[(3-0)!]2[(3-1)!]21!1!1!1!1!1!=62·22=144.For graphsg15,g16∈𝔊3,3 we have
(3.24)[g15]=[g16]={1,2,3},Ψ(g15)=Ψ(g16)=〈2,3,0,1〉,ω(g15)=ω(g16)=[(3-0)!]2[(3-1)!]31!2!3!=62·232·6=24.Then for the set𝔊3,3 we get
(3.25)θ(3,3)=∑g∈𝔊3,3‍ω(g)=64+48+48+144+24+24=352.


## 3.2.4. Considerk=4

Whenn=3 and k=4, the set 𝔊3,4={g17,g18,g19,g20,g21,g22,g23} consists of seven bipartite graphs, which are shown in Figure 8.Figure 8
n
=
3, k=4.For graphg17∈𝔊3,4 we have
(3.26)[g17]={1,1,2,2},Ψ(g17)=〈2,0,4,0〉,ω(g17)=[(3-0)!]2[(3-1)!]01!1!2!2!=62·2022=9.For graphg18∈𝔊3,4 we have
(3.27)[g18]={1,1,2,2},Ψ(g18)=〈0,4,2,0〉,ω(g18)=[(3-0)!]0[(3-1)!]41!1!2!2!=60·2422=4.For graphg19∈𝔊3,4 we have
(3.28)[g19]={1,1,1,1,1,1},Ψ(g19)=〈0,4,2,0〉,ω(g19)=[(3-0)!]0[(3-1)!]41!1!1!1!1!1!=60·24=16.For graphsg20∈𝔊3,4 and g21∈𝔊3,4 we have
(3.29)[g20]=[g21]={1,1,1,1,1,1},Ψ(g20)=Ψ(g21)=〈1,2,3,0〉,ω(g20)=ω(g21)=[(3-0)!]1[(3-1)!]21!1!1!1!1!1!=61·22=24.For graphsg22∈𝔊3,4 and g23∈𝔊3,4 we have
(3.30)[g22]=[g23]={1,1,1,1,2},Ψ(g22)=Ψ(g23)=〈1,3,1,1〉,ω(g22)=ω(g23)=[(3-0)!]1[(3-1)!]31!1!1!1!2!=61·232=24.Then we get(3.31)θ(3,4)=∑g∈𝔊3,4‍ω(g)=9+4+16+24+24+24+24=125.


## 3.2.5. Considerk=5

Whenn=3 and k=5, the set 𝔊3,5 consists of seven bipartite graphs g24÷g30, which are shown in Figure 9.Figure 9
n
=
3, k=5.For graphg24∈𝔊3,5 we have
(3.32)[g24]={1,1,2,2},Ψ(g24)=〈0,4,0,2〉,ω(g18)=[(3-0)!]0[(3-1)!]41!1!2!2!=60·2422=4.For graphg25∈𝔊3,5 we have
(3.33)[g25]={1,1,2,2},Ψ(g25)=〈0,2,4,0〉,ω(g18)=[(3-0)!]0[(3-1)!]21!1!2!2!=60·2222=1.For graphg26∈𝔊3,5 we have
(3.34)[g26]={1,1,1,1,1,1},Ψ(g26)=〈0,2,4,0〉,ω(g26)=[(3-0)!]0[(3-1)!]21!1!1!1!1!1!=60·22=4.For graphsg27∈𝔊3,5 and g28∈𝔊3,5 we have
(3.35)[g27]=[g28]={1,1,1,1,1,1},Ψ(g27)=Ψ(g28)=〈0,3,2,1〉,ω(g27)=ω(g28)=[(3-0)!]0[(3-1)!]31!1!1!1!1!1!=60·23=8.For graphsg29∈𝔊3,5 and g30∈𝔊3,5 we have
(3.36)[g29]=[g30]={1,1,1,1,2},Ψ(g29)=Ψ(g30)=〈1,1,3,1〉,ω(g29)=ω(g30)=[(3-0)!]1[(3-1)!]11!1!1!1!2!=61·212=6.Then we get(3.37)θ(3,5)=∑g∈𝔊3,5‍ω(g)=4+1+4+8+8+6+6=37.


## 3.2.6. Considerk=6

Whenn=3 and k=6, the set 𝔊3,6={g31,g32,g33,g34,g35,g36} consists of six bipartite graphs, which are shown in Figure 10.Figure 10
n
=
3, k=6.For graphg31∈𝔊3,6 we have
(3.38)[g31]={1,1,1,1,1,1},Ψ(g31)=〈0,0,6,0〉,ω(g31)=[(3-0)!]0[(3-1)!]01!1!1!1!1!1!=1.For graphsg32∈𝔊3,6 and g33∈𝔊3,6 we have
(3.39)[g32]=[g33]={1,1,1,1,2},Ψ(g32)=Ψ(g33)=〈0,1,4,1〉,ω(g32)=ω(g33)=[(3-0)!]0[(3-1)!]11!1!1!1!2!=60·212=1.For graphg34∈𝔊3,6 we have
(3.40)[g34]={1,1,1,1,1,1},Ψ(g34)=〈0,2,2,2〉,ω(g34)=[(3-0)!]0[(3-1)!]21!1!1!1!1!1!=60·221=4.For graphsg35∈𝔊3,6 and g36∈𝔊3,6 we have
(3.41)[g35]=[g36]={1,2,3},Ψ(g35)=Ψ(g36)=〈1,0,3,2〉,ω(g35)=ω(g36)=[(3-0)!]1[(3-1)!]01!2!3!=61·202·6=12.Then for the set𝔊3,6 we get
(3.42)θ(3,6)=∑g∈𝔊3,6‍ω(g)=1+1+1+4+12+12=8.


## 3.2.7. Considerk=7

Whenn=3 and k=7 the set 𝔊3,7={g37,g38,g39} consists of three bipartite graphs, which are shown in Figure 11.Figure 11
n
=
3, k=7.For graphg37∈𝔊3,7 it is true that
(3.43)[g37]={1,1,1,1,1,1},Ψ(g37)=〈0,0,4,2〉,ω(g37)=[(3-0)!]0[(3-1)!]01!1!1!1!1!1!=60·201=1.For graphsg38∈𝔊3,7 and g39∈𝔊3,7 we get
(3.44)[g38]=[g39]={1,1,2,2},Ψ(g38)=Ψ(g39)=〈0,1,2,3〉,ω(g38)=ω(g39)=[(3-0)!]0[(3-1)!]11!1!2!2!=60·2122=12.Then for the set𝔊3,7 we get
(3.45)θ(3,7)=∑g∈𝔊3,7‍ω(g)=1+12+12=2.


## 3.2.8. Considerk=8

Graphg40, which is displayed in Figure 12, is the only bipartite graph belonging to the set 𝔊3,8 in the case n=3 and k=8.Figure 12
n
=
3, k=8.For graphg40∈𝔊3,8 it is true that
(3.46)[g40]={1,1,2,2},Ψ(g40)=〈0,0,2,4〉,ω(g40)=[(3-0)!]0[(3-1)!]01!1!2!2!=60·2022=14.Therefore,(3.47)θ(3,8)=∑g∈𝔊3,8‍ω(g)=14.


## 3.2.9. Considerk=9

Whenn=3 and k=9 there is only one graph, and this is the complete bipartite graph g41 which is shown in Figure 13.Figure 13
n
=
3, k=9.For graphg41 it is true that
(3.48)[g41]={3,3},Ψ(g41)=〈0,0,0,6〉,ω(g41)=[(3-0)!]0[(3-1)!]03!3!=60·2062=136.Therefore(3.49)θ(3,9)=∑g∈𝔊3,9‍ω(g)=136.Having in mind the formula (2.10) and formulas (3.17) ÷ (3.49) for the number D9 of all ordered pairs disjoint S-permutation matrices in n=3 we finally get
(3.50)D9=(3!)12+(3!)8[∑k=19‍(-1)kθ(n,k)]=2176782336+1679616(-1296+1008-352+125-37+8-2+14-136)=1260085248.The numberd9 of all nonordered pairs disjoint matrices from Σ9 is equal to
(3.51)d9=12D9=630042624.


## 3.3.On a Combinatorial Problem of Graph Theory Related to the Number of Sudoku Matrices

Problem. Let n≥2 be a natural number, and let G be a simple graph having (n!)2n vertices. Let each vertex of G be identified with an element of the set Σn2 of all n2×n2 S-permutation matrices. Two vertices are connected by an edge if and only if the corresponding matrices are disjoint. The problem is to find the number of all complete subgraphs of G having n2 vertices.Note that the number of edges in graphG is equal to dn2 and can be calculated using formulas (2.4) and (2.5) (resp., formulas (2.9), (2.10), and (2.5)).Denote byzn the solution of the Problem 1, and let σn be the number of all n2×n2 Sudoku matrices. Then according to formula (1.5) and the method of construction of the graph G, it follows that the next equality is valid:
(3.52)zn=σn(n2)!.We do not know a general formula for finding the number of alln2×n2 Sudoku matrices for each natural number n≥2, and we consider that this is an open combinatorial problem. Only some special cases are known. For example in n=2 it is known that σ2=288 [8]. Then according to formula (3.52) we get
(3.53)z2=σ24!=28824=12.In [6] it has been shown that in n=3 there are exactly,
(3.54)σ3=6670903752021072936960=9!×722×27×27704267971=220×38×51×71×277042679711~6.671×1021,
a number of Sudoku matrices. Then according to formula (3.52) we get
(3.55)z3=σ39!=6670903752021072936960362880=18383222420692992.



---

*Source: 384068-2012-12-09.xml*