2
$\begingroup$

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a triangle, $T(n,k)$ like this: \begin{array}{c} \text{degree}\; \backslash \text{line-sum} & 0 & 1 & 2 & 3 & 4 & 5 & \dots & \text{Sum}\\ \hline 0 & 1 & & & & & & & 1 \\ 1 & 1 & 1 & & & & & & 2 \\ 2 & 1 & 2 & 1 & & & & & 4 \\ 3 & 1 & 4 & 4 & 1 & & & & 10\\ 4 & 1 & 10& 18& 10& 1 & & & 40\\ 5 & 1 & 26& ? & ? & 26& 1 & & ? \\ \vdots & & & & & & & \ddots \end{array}

The column $T(n, 1)$ corresponds to the number of $n \times n$ symmetric permutation matrices (A00085). In general $T(n,k) = T(n, n-k)$ since, if we have an element of $T(n, k)$ we can send $1 \mapsto 0$ and $0 \mapsto 1$, and have a corresponding element of $T(n, n-k)$.

$T(n, k)$ is equivalent to the number of $n$-vertex graphs with degree $k$ at every vertex (including loops). A related question is: how many edges does this graph have?

I'm looking for a closed, or recursive formula for $T(n, k)$ because I've been struggling for a while on this.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.