Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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)... –  Emile Maras Sep 30 '11 at 17:08
    
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. –  Igor Rivin Sep 30 '11 at 18:41

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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