In how many ways can 3n elements be chosen out of an n*n array with exactly 3 in each row and column?

combinatorics/multipermutations New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

In how many ways can 3n elements be chosen out of an n*n array with
exactly 3 in each row and column?  [Examples: n=3, #ways=1; n=4,
#ways=4!=24 because the four remaining elements must form a permutation
matrix; n=10, #ways=?]

Show solution

Reference: Comtet, Louis, _Advanced_Combinatorics_, D. Reidel [Editor: spelled
"Riedel" in the original] Publishing Company, 1974, page 235.

Comtet calls these "multipermutations", which is apparently standard.  For
k=3, he gives the formula:
          1                   a2                            2   a2   a3
P(n,3) = ---     SUM      (-1)  (3a1+a2)! a2! a3! (a1,a2,a3)  18   12
         36! a1+a2+a3 = n

-- Frank Adams <ihnp4!philabs!pwa-b!mmintl!franka>

In the above formula 36! must be read 36^n.

Comtet gives also:
                                                      2
                              (k n)! exp(- 1/2 (k - 1) )
                    P(n,k) ~ ----------------------------
                                         (2 n)
                                       k!

In Enumeration and Design (David M. Jackson & Scott A. Vanstone), p.225-238,
Brendan D. McKay proves:
                                                         3
                                                 2      k
                         (k n)! exp(- 1/2 (k - 1)  + O(----))
                                                         n
               P(n,k) = --------------------------------------
                                          (2 n)
                                        k!

uniformly for 1 <= k <= epsilon * n, where 0 < epsilon < 1/6.

-- Paul Zimmermann