1
$\begingroup$

Stanley's Enumerative Combinatorics (http://www-math.mit.edu/~rstan/ec/ec1.pdf) contains next fact: 1.1.3 Example. Let f(n) be the number of n × n matrices M of $0$’s and $1$’s such that every row and column of M has three 1’s. For example, f(0) = 1, f(1) = f(2) = 0, f(3) = 1. The most explicit formula known at present for f(n) is $$f(n)=6^{-n}{(n!)}^2\sum\frac{(-1)^{\beta}(\beta+3\gamma)!2^\alpha 3^{\beta}}{\alpha!\beta!\gamma!^26^{\gamma}}$$ where the sum ranges over all (n + 2)(n + 1)/2 solutions to α + β + γ = n in nonnegative integers.

I need proof of this fact. (i.e. reference to book or articles that contains proof this fact).

$\endgroup$
  • 2
    $\begingroup$ If it's not already mentioned in the book, you could ask Stanley. $\endgroup$ – Marc van Leeuwen Mar 12 '13 at 10:04
  • $\begingroup$ It might help if you quote the formula $\endgroup$ – Ross Millikan May 16 '15 at 22:48
  • 2
    $\begingroup$ Your question is totally valid, but I would like to point out that that example is presented to show you heuristically what "closed form" means in combinatorics, and you are by no means expected to derive or prove the correctness of that formula at that point. $\endgroup$ – Eric Tressler May 16 '15 at 22:50
  • 1
    $\begingroup$ I also cannot see how to show this; if you really want to know the derivation, you should try this: find f(3),...,f(7) (say), and plug it into OEIS (the Online Encyclopedia of Integer Sequences). There you will find the sequence, most likely, and also probably references to a proof. $\endgroup$ – Eric Tressler May 16 '15 at 22:54
9
$\begingroup$

You want the coefficient of $x_1^3\cdots x_n^3y_1^3\cdots y_n^3$ in $\prod_{i=1}^n \prod_{j=1}^n (1+x_iy_j)$. Expand the logarithm, delete all terms with an exponent greater than 3, apply the exponential function exp, and simplify. For a generalization, see the paper by Musiker-Odama at https://www.mtholyoke.edu/courses/gcobb/REU_MCMC/papers.html.

$\endgroup$
4
$\begingroup$

For $n=4$, there are $4$ options for placing the single $0$ in the first row, then $3$ in the second row, $2$ in the third row and $1$ in the fourth row, for a total of $24$. Searching for $1,0,0,1,24$ at OEIS yields OEIS sequence A001501; the entry contains lots of references.

$\endgroup$
2
$\begingroup$

This problem was first solved by Ron Read in this 1958 PhD thesis. I didn't check if exactly this formula appears, but there are several that look very similar. One combinatorial way to prove it is like this:

Let $A_1,\ldots,A_n$ and $B_1,\ldots,B_n$ be disjoint sets of size 3. Consider bijections from $A_1\cup\cdots\cup A_n$ to $B_1\cup\cdots\cup B_n$. There are $(3n)!$ in total. Use inclusion-exclusion to find the number such that each $A_i$ maps to 3 different $B_j$s. (There are two things that can go wrong: mapping two elements of $A_i$ to two elements of $B_j$, and mapping all of $A_i$ to all of $B_j$; the counting is easy since the involved $B_j$s are distinct.) Then make an $n\times n$ matrix whose $(i,j)$ entry is the number of elements of $A_i$ which map to $B_j$. Finally, note that each matrix comes from $(3!)^{2n}$ bijections.

$\endgroup$
1
$\begingroup$

An answer can also be found in the section 6.3 of the book "L. Comtet, Advanced Combinatorics, Springer 1974" and asymptotic formula $f(n)\sim e^{-2}36^{-n}(3n)!$ can be derived from a general asymptotic formula in the paper "C. J. Everett, P. R. Stein, The asymptotic number of integer stochastic matrices, Disc. Math. Vol. 1, No. 1 (1972) 55-72".

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.