Matrices with fixed row and column sums

Given two vectors \(p\) and \(q\) of non-negative integer numbers, denote by \(A(p, q)\) the number of matrices with non-negative integer entries whose row sum and column sum respectively are \(p\) and \(q\), and denote by \(B(p, q)\) the number of matrices with entries in \(\{0, 1\}\) whose row sum and column sum respectively are \(p\) and \(q\).

The problem of determining \(A(p,q)\) and \(B(p,q)\) has a solution in the theory of symmetric polynomials. Denote by \(\lambda\) the vector obtained by sorting \(p\) in decreasing order and dropping the zero elements, and similarly, denote by \(\mu\) the vector obtained by sorting \(q\) in decreasing order and dropping the zero elements. Then \(\lambda\) and \(\mu\) are two integer partitions. In order for the two numbers \(A(p,q)\) and \(B(p,q)\) to be non-zero, an obvious necessary condition is that the sum of \(p\) is equal to the sum of \(q\). Let’s assume this condition holds true and denote by \(n\) this common sum. Of course, \(n\) is also the sum of \(\lambda\) and the sum of \(\mu\).

Then it is known in the theory of symmetric polynomials that \[ A(p, q) = \sum_{\kappa \vdash n} K(\kappa, \lambda)K(\kappa, \mu) \] where the notation \(\kappa \vdash n\) means that \(\kappa\) is an integer partition of \(n\) and where \(K(\kappa, \nu)\) denotes the Kostka number associated to two integer partitions \(\kappa\) and \(\nu\).

It is also known that \[ B(p, q) = \sum_{\kappa \vdash n} K(\kappa, \lambda) K(\kappa’, \mu) \] where \(\kappa’\) denotes the conjugate partition (or dual partition) of the partition \(\kappa\).

One also has \(A(p,q) = \langle h_\lambda, h_\mu \rangle\) where \(h_\kappa\) denotes the complete homogeneous symmetric function associated to an integer partition \(\kappa\) and \(\langle \cdot, \cdot \rangle\) denotes the Hall inner product, and one has \(B(p,q) = \langle h_\lambda, e_\mu \rangle\) where \(e_\kappa\) denotes the elementary symmetric function associated to an integer partition \(\kappa\).

All these results can be found in Macdonald’s book Symmetric functions and Hall polynomials.

Now let’s turn to the implementation of \(A(p,q)\) and \(B(p,q)\) in R. Enumerating the partitions of an integer is one of the features of the partitions package (the parts function). This package also allows to get the conjugate partition of an integer partition (the conjugate function). The Kostka numbers can be obtained with the syt package (the KostkaNumber function). So we use these two packages.

library(partitions)
library(syt)

Apq <- function(p, q) {
  n <- sum(p)
  if(sum(q) != n) {
    return(0L)
  }
  lambda <- Filter(\(i) {i > 0}, sort(p, decreasing = TRUE))
  mu <- Filter(\(i) {i > 0}, sort(q, decreasing = TRUE))
  partitions <- parts(n)
  sum(apply(partitions, 2L, function(kappa) {
    KostkaNumber(kappa, lambda) * KostkaNumber(kappa, mu)
  }))
}

Bpq <- function(p, q) {
  n <- sum(p)
  if(sum(q) != n) {
    return(0L)
  }
  lambda <- Filter(\(i) {i > 0}, sort(p, decreasing = TRUE))
  mu <- Filter(\(i) {i > 0}, sort(q, decreasing = TRUE))
  muprime <- conjugate(mu)
  partitions <- parts(n)
  sum(apply(partitions, 2L, function(kappa) {
    KostkaNumber(kappa, lambda) * KostkaNumber(kappa, muprime)
  }))
}