1. Introduction

Everywhere in the current work will denote the set . If is a finite set, as usual will denote the cardinality of , and with we will be denoting the set of all permutations of the elements from . With we will be denoting the symmetric group, . If , then is the image of by the mapping .

Binary is called a matrix whose elements belong to the set .

-matrices we will call all binary matrices, in which in every row and every column there exist exactly identities and zeros. In the current work we will examine the following

Problem 1 Obtain all -matrices.

Let us denote with the number of all -matrices. In ^[3], the next formula is shown:

(1)

Let us notice that formula (1) does not give a solution to problem 1, it only calculates the number of the objects which are being sought. We will give a solution to problem 1 with the help of algorithm 1 described below. Furthermore, formula (1) has been obtained by V. E. Tarakanov when examining an equivalence relation in the set of all ordered pairs of derangements. Let us remind that is called derangement, if for every . In the current work we will suggest a new constructive proof of formula (1) by suggesting an algorithm for obtaining all -matrices.

2. The Main Results

A partition of the set we will be calling every family of sets , such that for every , when . The subsets are called blocks of partition. We say that a partition is of type , if there exist exactly blocks with cardinality , . As it is well known ^[1] there exists an one-to-one correspondence between the set of all types of partitions of , and the set of all solutions to the equation .

Algorithm 1 Obtaining all -matrices.

1. For every solution to the equation Do begin

2. For every partition U of of type Do begin

3. For every partition V of of type Do begin

4. For every , for which Do begin

5. Form the sets

and

where U,V,

6. For every Do begin

7. For every Do begin

8.

/* - integer; - set of integers */

9.

10. For every permutation Do begin

11. For every permutation Do begin

12. If Then return to 11;

13.

14. Obtain the set of three-dimensional vectors:

15. End 11

16. End 10

17. End 7

18. Form the set

19. For every -tuple Do begin

20. Form the set of three-dimensional vectors:

21. End 19

22. End 6

23. End 4

24. For every -tuple Do begin

/* If , then by definition and . */

25. For every -tuple Do begin

/* If , then by definition и . */

26. Form the set of three-dimensional vectors:

/* If , then by definition и . */

27. From obtain only -matrix , such that if , then in in -th column the only two units stand in rows with numbers and ;

28. End 25

29. End 24

30. End 3

31. End 2

32. End 1

Theorem 1. With the help of algorithm 1, all -matrices are obtained, moreover during every execution of statement 27 a different -matrix is obtained.

Proof. Let and be two vectors from set , which is obtained during execution of statement 26 from algorithm 1. If there exist and , such that (i.e. and are obtained during single execution of statement 14), then according to statements 10 and 14 . According to statements 20 and 26 it is not possible to exist , , such that and and to be from one and the same set , which is obtained during execution of statement 26. If when , then and are from different blocks of the partition U, i.e. again . Furthermore, obviously for every there exists a block , such that and according to statements 10 and 14 there exist a natural number and , such that . Therefore, the first elements of every vector in the set during single execution of statement 26 correctly indicate a number of a column in a matrix.

Let . Since statements 11,12,14 and 26 are inner for loops with numbers 2 and 3, then according to these statements there exist unique three-dimensional vectors and , from the set during single execution of statement 26, such that be at second position in and at third position in . Therefore, in the matrices which are obtained in statement 27 there are exactly two units in every row and according to statement 27 exactly two units in every column.

We assume that there exist two sets and , obtained during different executions of statement 26, which are equal to each other. Then , which is impossible, bearing in mind the courses of action of statements 14, 20 and 26, and with what objects they work during each of their executions. Therefore, during every execution of statement 27 a different -matrix is obtained.

Let us denote with the set of the matrices obtained during the work of statement 27. Since in there are not any duplicate elements, then .

Let be an arbitrary -matrix. We will show that . Let in the beginning have not any marked rows and columns. In we build a walk, starting from the upper ''1'' of the leftmost unmarked column of the matrix, we continue to the next below ''1'' in the column, after that we reach the second ''1'' from the same row, then the second ''1'' from the same column and so on until we return to the initial cell. Moving on this walk we mark the rows and the columns we pass, and when passing through -th column we obtain the vector (we have first passed through the ''1'' in -th row, then through the ''1'' in -th row). We continue the same process with the unmarked rows and columns until we mark the whole matrix. Let be the minimum number among the numbers standing at first position of the vectors corresponding to a particular walk. Since the beginning of the loop starts from the upper ''1'' of the leftmost column of the walk, then for the vector the inequality is satisfied. Therefore, for every walk we obtain a set of vectors, which are obtained in statement 14 as well. Uniting the sets of all vectors which are obtained from walks in with the same length, we obtain a set, which is obtained in statement 20 as well. The union of all such sets corresponding to a particular matrix, is a set, which is obtained in statement 26 as well. Therefore , whence the assertion of the theorem follows.

With the help of Algorithm 1 and Theorem 1 we will also prove the next theorem, proven in ^[3] in a different way.

Theorem 2. ^[3] The number of all -matrices is given by the formula:

Proof. Let us denote with the number of the iterations of loop with number in Algorithm 1. Since Algorithm 1 has been maid so that every time during execution of statements 14, 20, 26 and therefore also statement 27 (it follows from Theorem 1) different objects are obtained, then

(2)

It is easy to see that

According to a well-known formula ^[1] the next equation is true:

For and we obtain respectively:

Substituting in (2) we obtain the assertion of the theorem as well.

3. Conclusion

Comparing the proof of theorem 2 to formula (1) we are convinced of the high efficiency of algorithm 1. This is practically a proof of the fact that algorithm 1 works exactly as much as necessary.

References

[1]	M. Aigner. Combinatorial Theori. Springer-Verlag, 1979.
	In article		CrossRef
[2]	P. Lancaster, Theory of Matrices. Academic Press, NY, 1969.
	In article		PubMed
[3]	V. E. Tarakanov, Combinatorial problems on binary matrices. in Combinatorial Analysis, Vol. 5 (1980), Moscow State University, 4-15. (in Russian).
	In article