login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000186 Number of 3 X n Latin rectangles in which the first row is in order.
(Formerly M2140 N0851)
26
1, 0, 0, 2, 24, 552, 21280, 1073760, 70299264, 5792853248, 587159944704, 71822743499520, 10435273503677440, 1776780700509416448, 350461958856515690496, 79284041282622163140608, 20392765404792755583221760, 5917934230798104348783083520, 1924427226324694427836833857536 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Or number of n X n matrices with exactly one 1 and one 2 in each row and column which are not in the main diagonal, other entries 0. - Vladimir Shevelev, Mar 22 2010

REFERENCES

K. P. Bogart and J. Q. Longyear, Counting 3 by n Latin rectangles, Proc. Amer. Math. Soc., 54 (1976), 463-467.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 183.

Dulmage, A. L.; McMaster, G. E. A formula for counting three-line Latin rectangles. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 279-289. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0392611 (52 #13428). - From N. J. A. Sloane, Apr 06 2012

I. Gessel, Counting three-line Latin rectangles, Lect. Notes Math, 1234(1986), 106-111. [From Vladimir Shevelev, Mar 25 2010]

Goulden and Jackson, Combin. Enum., Wiley, 1983 p. 284.

S. M. Jacob, The enumeration of the Latin rectangle of depth three..., Proc. London Math. Soc., 31 (1928), 329-336.

S. M. Kerawala, The enumeration of the Latin rectangle of depth three by means of a difference equation, Bull. Calcutta Math. Soc., 33 (1941), 119-127.

S. M. Kerawala, The asymptotic number of three-deep Latin rectangles, Bull. Calcutta Math. Soc., 39 (1947), 71-72.

Koichi, Yamamoto, An asymptotic series for the number of three-line Latin rectangles, J. Math. Soc. Japan 1, (1950). 226-241.

W. Moser. A generalization of Riordan's formula for 3Xn Latin rectangles, Discrete Math., 40, 311-313 [From Vladimir Shevelev, Mar 25 2010]

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 210.

V. S. Shevelev, Reduced Latin rectangles and square matrices with identical sums in the rows and columns [Russian], Diskret. Mat., 4 (1992), no. 1, 91-110.

V. S. Shevelev, A generalized Riordan formula for three-rowed Latin rectangles and its applications, DAN of the Ukraine, 2 (1991), 8-12 (in Russian) [From Vladimir Shevelev, Mar 25 2010]

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. S. Stones, The many formulas for the number of Latin rectangles, Electron. J. Combin 17 (2010), A1.

D. S. Stones and I. M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A 117 (2010), 204-215.

RJ Stones, S Lin, X Liu, G Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..207

F. Alayont and N. Krzywonos, Rook Polynomials in Three and Higher Dimensions, 2012. - From N. J. A. Sloane, Jan 02 2013

S. M. Jacob, The enumeration of the Latin rectangle of depth three..., Proc. London Math. Soc., 31 (1928), 329-336.

S. M. Kerawala, The enumeration of the Latin rectangle of depth three by means of a difference equation, Bull. Calcutta Math. Soc., 33 (1941), 119-127. [Annotated scanned copy]

S. M. Kerawala, The asymptotic number of three-deep Latin rectangles, Bull. Calcutta Math. Soc., 39 (1947), 71-72. [Annotated scanned copy]

Vladimir Shevelev, SPECTRUM OF PERMANENTS VALUES AND ITS EXTREMAL MAGNITUDES ..., arXiv preprint arXiv:1104.4051, 2011.

Index entries for sequences related to Latin squares and rectangles

FORMULA

a(n)=n!*Sum_{k+j<=n} (2^j/j!)*k!*binomial(-3*(k+1), n-k-j).

Note that the formula Sum_{k=0..n, k <= n/2} binomial(n, k)D(n-k)*D(k)*U(n-2*k), where D() = A000166, U() = A000179 given by Riordan, p. 209 gives the wrong answers unless we set U(1) = -1 (or in other words we must take U() = A102761). With U(1) = 0 it produces A170904. See the Maple code here. - N. J. A. Sloane, Jan 21 2010, Apr 04 2010. Thanks to Vladimir Shevelev for clarifying this comment.

E.g.f.: exp(2*x) Sum(n>=0; n! x^n /(1+x)^(3*n+3)) from Gessel reference. - Wouter Meeussen, Nov 02 2013

a(n) ~ n!^2/exp(3). - Vaclav Kotesovec, Sep 08 2016

MAPLE

for n from 1 to 250 do t0:=0; for j from 0 to n do for k from 0 to n-j do t0:=t0 + (2^j/j!)*k!*binomial(-3*(k+1), n-k-j); od: od: t0:=n!*t0; lprint(n, t0); od:

Maple code for A000186 based on Eq. (30) of Riordan, p. 205. Eq. (30a) on p. 206 is wrong. - N. J. A. Sloane, Jan 21 2010. Thanks to Neven Juric for correcting an error in the definition of fU, Mar 01 2010

# A000166

unprotect(D);

D := proc(n) option remember; if n<=1 then 1-n else (n-1)*(D(n-1)+D(n-2)); fi; end;

[seq(D(n), n=0..30)];

# A000179

U := proc(n) if n<=1 then 1-n else

add ((-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k), k=0..n); fi; end;

[seq(U(n), n=0..30)];

# funny A000179

fU := proc(n) global U; if n<=-2 then U(-n) elif abs(n)=1 then -1 elif n=0 then 2 else U(n); fi; end;

[seq(fU(n), n=-10..10)];

# A000186

K:=proc(n) local k; global D, fU; (1/2)*add( binomial(n, k)*D(n-k)*D(k)*fU(n-2*k), k=0..n ); end;

[seq(K(n), n=0..30)];

# another Maple program:

a:= proc(n) option remember; `if`(n<5, [1, 0, 0, 2, 24][n+1],

     ((n-1)*(n^2-2*n+2)*a(n-1) +(n-1)*(n-2)*(n^2-2*n+2)*a(n-2)

      +(n-1)*(n-2)*(n^2-2*n-2) *a(n-3)

      +2*(n-1)*(n-2)*(n-3)*(n^2-5*n+3) *a(n-4)

      -4*(n-2)*(n-3)*(n-4)*(n-1)^2 *a(n-5)) / (n-2))

    end:

seq(a(n), n=0..25);  # Alois P. Heinz, Nov 02 2013

MATHEMATICA

a[n_] := (t0 = 0; Do[t0 = t0 + (2^j/j!)*k!*Binomial[-3*(k+1), n-k-j], {j, 0, n}, {k, 0, n-j}]; n!*t0); Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Oct 13 2011, after Maple *)

CROSSREFS

Cf. A000512.

Sequence in context: A262009 A054946 A046744 * A210905 A012113 A156525

Adjacent sequences:  A000183 A000184 A000185 * A000187 A000188 A000189

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Formula and more terms from Vladeta Jovovic, Mar 31 2001

Edited by N. J. A. Sloane, Jan 21 2010, Mar 04 2010, Apr 04 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 29 22:45 EDT 2017. Contains 287257 sequences.