On the number of disjoint pairs of S-permutation matrices

In [R. Fontana, Fraction of permutations, an application to Sudoku, Journal of Statistical Planning and Inference 141 (2011) 3697–3704], Roberto Fontana offers an algorithm for obtaining Sudoku matrices. Introduced by Geir Dahl concept disjoint pairs of S-permutation matrices [G. Dahl, Permutation matrices related to Sudoku, Linear Algebra and its Applications (430) (2009) 2457–2463] is used in this algorithm. Analyzing the works of G. Dahl and R. Fontana, the question of finding a general formula for counting disjoint pairs of n2×n2n2×n2 S-permutation matrices as a function of the integer nn naturally arises. This is an interesting combinatorial problem that deserves its consideration. The present work solves this problem. To do that, the graph theory techniques have been used. It has been shown that to count the number of disjoint pairs of n2×n2n2×n2 S-permutation matrices, it is sufficient to obtain some numerical characteristics of the set of all bipartite graphs of the type g=〈Rg∪Cg,Eg〉g=〈Rg∪Cg,Eg〉, where V=Rg∪CgV=Rg∪Cg is the set of vertices, and EgEg is the set of edges of the graph gg, Rg∩Cg=0̸Rg∩Cg=0̸, |Rg|=|Cg|=n|Rg|=|Cg|=n.