3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Paul-Olivier Dehaye Oct 7 '10 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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