Generating functions and counting symmetric (0,1) matrices

Abstract

In this work we will present an original solution to the problem: how many symmetric (0,1) matrices (whose entries are all equal to 0 or 1) of order n can be constructed with the additional constraint that the sum of the elements of any row is fixed for each integer 0, 1, 2, . . . , n as for example:

How many symmetric (0,1) matrices of order 5 can be constructed such that the sum of the elements in any row is equal to 2?
• How many symmetric (0,1) matrices of order 4 can be constructed such that s(1) = 2, s(2) =(3) = 3 and s(4) = 4, where s(i) indicates the sum of the elements of row i?
The strategy for solving this problem involves the use of generating functions, an extremely important tool with diverse applications, but little studied in undergraduate courses in mathematics and exact sciences. In this sense, this text aims to offer an introduction to this tool through several examples, including the problem of symmetric matrices, whose solution can be modeled by a generating function of n variables with polynomial expansion in which the coefficient of x₁^{t₁}...x_n^{t_n}, t_i ∈ {0, 1, 2, . . . , n} expresses the number of matrices in which the sum of row i is equal to ti. This work was presented in the form of a minicourse, without publication in the proceedings, at the XI Bienal de Matem´atica, held in S˜ao Carlos-SP, between July 29 and August 2, 2024.