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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Emile Maras
    Commented 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
    Commented 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).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .