3
$\begingroup$

I do research in thermo-statistic and I have a maths problem i'dd like to solve.

Let's consider a checkerboard of R rows and C columns. We want to know the number of available configurations to fill the board with N balls with the following rules : - we can put only one ball per square - there must be n_i balls on the ith column - there must be m balls on each row (m is the same for all rows)

So we'dd like to find out this number of configurations as a function of R, C, N, {n_i}, m.

$\endgroup$

2 Answers 2

4
$\begingroup$

See the formula on page 399 in:

http://stat.gamma.rug.nl/Snijders_Psychometrika1991_Enumeration_Simulation.pdf

EDIT For a more general setup see:

MR2600999 (2011e:05005) Barvinok, Alexander(1-MI) On the number of matrices and a random matrix with prescribed row and column sums and 0–1 entries. (English summary) Adv. Math. 224 (2010), no. 1, 316–339.

$\endgroup$
2
  • $\begingroup$ It's not far... but in that case they have a square board whereas mine is not. And the formulae they give is valid when R = C is very large. In my case, C is very large, but R is small (less than 20)... $\endgroup$ Sep 30, 2011 at 17:08
  • $\begingroup$ You are incorrect. The matrices do NOT need to be square, however the bounds on the number of 1s are the same vertically and horizontally. See The edit for a more modern/general result. $\endgroup$
    – Igor Rivin
    Sep 30, 2011 at 18:41
4
$\begingroup$

The case of $R~$ bounded and $C~$ large is not covered by the formulas of Barvinok. The only published case as far as I know is for the row and column sums both being uniform. See E. Rodney Canfield and Brendan D. McKay, Asymptotic Enumeration of Dense 0-1 Matrices with Equal Row Sums and Equal Column Sums, Electron. J. Combin., 12 (2005) R29, Theorem 4. http://www.combinatorics.org/Volume_12/Abstracts/v12i1r29.html .

To do the case of more general column sums asymptotically, you just need to apply a suitable central limit theorem. Each column corresponds to an $R$-dimensional random variable taking values in $\{0,1\}^R$. All these variables are independent, and the row sums are just the sums of these variables. You need a local limit theorem in the lattice case, for example around Corollary 22.3 of R. N. Bhattacharya and R. R. Rao, Normal Approximation and Asymptotic Expansions, John Wiley & Sons (NY, 1976).

Don't expect any exact answers except for very small $n_i$. You can compute some exact values by making a recurrence based on adding one more column, and also by other means (see Section 6 of my paper).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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