One dimension ({0,1} n*n matrix with exactly one 1 per row or column): The number of permutations satisfies Stirling's formula: it's [(1+o(1)(n/e)]^n
Two dimensions ({0,1} n*n*n matrix with exactly one 1 per row, column or shaft): The number of Latin squares, as seen from Van Lint and Wilson's book, is [(1+o(1))(n/e^2)]^{n^2}.
Conjecture: in d dimensions, it's [(1+o(1))(n/e^d)]^{n^d}
Linial and Zur Luria proved the "less than or equal to" side. The "greater than or equal to" is still open.
Is there some natural heuristic that suggests why this should be the correct bound?
ReplyDeleteTo answer my own question, I guess one way of thinking about it is as follows.
DeleteFix one direction, and place one 1 uniformly and independently at random on each of the n^d parallel lines in that direction. For each of the dn^d lines not in the fixed direction, there's an approximately 1/e chance that the line contains exactly one 1 (the limiting distribution is Poisson with mean 1).
These events aren't independent for different lines, but they should me "nearly" independent in some sense (placing one 1 on one line doesn't have too much impact on the possible locations of 1's on other lines). So you might expect the probability every line contains exactly one 1 to be roughly e^{-d n^d}.