Algorithms for constructing (0,1)-matrices with prescribed row and column sum vectors

摘要

There is a bijection between the class (R, S) of (0,1)-matrices with row sum vector R and column sum vector S and pairs of Young tableaux of conjugate shapes λ and λ~* with S≤λ≤R~*. In this bijection, the tableau of shape λ, the insertion tableau, has content S and the tableau of shape λ~*, the recording tableau, has content R. Using a Ryser-like algorithm, we give canonical constructions for matrices in (R, S) whose insertion tableaux have shape λ=S and R~*, respectively.