MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The same formula for the number of four-line Latin rectangles was given in:

  • Athreya, K. B., Pranesachar, C. R. and Singhi, N. M. On the Number of Latin Rectangles and Chromatic Polynomial of $L(K_{r,s})$, European Journal of Combinatorics, (1) 1980, 9-17.
  • Pranesachar, C. R., Enumeration of Latin Rectangles via SDR's, Lecture Notes in Math., 1981, Springer, 380-390.

I'll reproduce the formula below:

\[L(4,k,n)=\frac{n!k!}{(n-k)!^4} \sum \frac{(-1)^{\sum \beta_i+\varepsilon} 2^{\sum \delta_i} 6^\varepsilon}{\alpha! \prod (\beta_i!) \prod (\gamma_i!) \prod (\delta_i!) \varepsilon!} \times T \times S \] where the sum is over all \[\alpha+\sum_{i=1}^6 \beta_i+\sum_{i=1}^3 \gamma_i + \sum_{i=1}^4 \delta_i + \epsilon=k.\] Further \begin{align*} T=& \sum_{\theta_1,\theta_2,\theta_3 \geq 0} {{\beta_1+\gamma_1} \choose \theta_1} {{\beta_6+\gamma_1} \choose \theta_1} \theta_1! {{\beta_2+\gamma_2} \choose \theta_2} {{\beta_5+\gamma_2} \choose \theta_2} \theta_2! \times\\\\ & {{\beta_3+\gamma_3} \choose \theta_3} {{\beta_4+\gamma_3} \choose \theta_3} \theta_3! (\underbrace{n-(\sum \beta_i+2\sum \gamma_i+\sum \delta_i+\epsilon)+\theta_1+\theta_2+\theta_3}_{\text{can be negative?!}})! \end{align*} and \begin{align*} S=& (n-k+\alpha+\beta_4+\beta_5+\beta_6+\delta_1)! (n-k+\alpha+\beta_2+\beta_3+\beta_6+\delta_2)! \times\\\\ & (n-k+\alpha+\beta_1+\beta_3+\beta_5+\delta_3)! (n-k+\alpha+\beta_1+\beta_2+\beta_4+\delta_4)!. \end{align*}

The four-line Latin rectangles case is when k=n. In trying to implement this formula, I find that one of the terms can be a negative factorial. I've (unsuccessfully) tried replacing the negative factorials by 0 or 1.

Does anyone know how to resolve this problem and get this formula to actually count four-line Latin rectangles?

My interest in this formula is mostly historical since Doyle gave a superior formula here.

share|cite|improve this question

Obviously, as you know, writing down something like $(-3)!$ is absurd and meaningless. But I would contend that absurd and meaningless as an expression like $$\frac{(-3)!}{(-6)!}$$ is, that it still equals $(-3)(-4)(-5)=-60$. If you have these negative factorials paired up into numerators and denominators, you can calculate like this. Essentially this is interpolating the factorial in the obvious way via the gamma function and noting that sometimes poles cancel to give removable singularities.

I don't know if using a convention like this will successfully resolve your particular problem though.

share|cite|improve this answer
This is also what I would look for, but it won't work here. To work, you need for every single term to be able to "cancel poles" and give a meaning to that term. But consider $$ \alpha =0 , \beta_i =0, \delta_i =0 , \epsilon=0 $$ and $n=k$. Then $T$ will have one $(-n)!$, with all other factors involving only factorials of positive integers... – Paul-Olivier Dehaye Oct 7 '10 at 9:17

Your Answer


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.