cp's OEIS Frontend

A000186 Number of 3 X n Latin rectangles in which the first row is in order.

%I A000186 M2140 N0851 #101 May 19 2024 14:03:15
%S A000186 1,0,0,2,24,552,21280,1073760,70299264,5792853248,587159944704,
%T A000186 71822743499520,10435273503677440,1776780700509416448,
%U A000186 350461958856515690496,79284041282622163140608,20392765404792755583221760,5917934230798104348783083520,1924427226324694427836833857536
%N A000186 Number of 3 X n Latin rectangles in which the first row is in order.
%C A000186 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
%D A000186 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 183.
%D A000186 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
%D A000186 I. Gessel, Counting three-line Latin rectangles, Lect. Notes Math, 1234(1986), 106-111. [From _Vladimir Shevelev_, Mar 25 2010]
%D A000186 Goulden and Jackson, Combin. Enum., Wiley, 1983 p. 284.
%D A000186 S. M. Jacob, The enumeration of the Latin rectangle of depth three..., Proc. London Math. Soc., 31 (1928), 329-336.
%D A000186 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.
%D A000186 S. M. Kerawala, The asymptotic number of three-deep Latin rectangles, Bull. Calcutta Math. Soc., 39 (1947), 71-72.
%D A000186 Koichi, Yamamoto, An asymptotic series for the number of three-line Latin rectangles, J. Math. Soc. Japan 1, (1950). 226-241.
%D A000186 W. Moser. A generalization of Riordan's formula for 3Xn Latin rectangles, Discrete Math., 40, 311-313 [From _Vladimir Shevelev_, Mar 25 2010]
%D A000186 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 210.
%D A000186 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.
%D A000186 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]
%D A000186 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000186 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000186 D. S. Stones, The many formulas for the number of Latin rectangles, Electron. J. Combin 17 (2010), A1.
%D A000186 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
%H A000186 N. J. A. Sloane, <a href="/A000186/b000186.txt">Table of n, a(n) for n = 0..207</a>
%H A000186 F. Alayont and N. Krzywonos, <a href="http://faculty.gvsu.edu/alayontf/notes/rook_polynomials_higher_dimensions_preprint.pdf">Rook Polynomials in Three and Higher Dimensions</a>, 2012. - From _N. J. A. Sloane_, Jan 02 2013
%H A000186 K. P. Bogart and J. Q. Longyear, <a href="https://doi.org/10.1090/S0002-9939-1976-0389618-9">Counting 3 by n Latin rectangles</a>, Proc. Amer. Math. Soc., 54 (1976), 463-467.
%H A000186 S. M. Jacob, <a href="http://dx.doi.org/10.1112/plms/s2-31.1.329">The enumeration of the Latin rectangle of depth three...</a>, Proc. London Math. Soc., 31 (1928), 329-336.
%H A000186 S. M. Kerawala, <a href="/A001623/a001623.pdf">The enumeration of the Latin rectangle of depth three by means of a difference equation</a>, Bull. Calcutta Math. Soc., 33 (1941), 119-127. [Annotated scanned copy]
%H A000186 S. M. Kerawala, <a href="/A000186/a000186.pdf">The asymptotic number of three-deep Latin rectangles</a>, Bull. Calcutta Math. Soc., 39 (1947), 71-72. [Annotated scanned copy]
%H A000186 John Riordan, <a href="/A000186/a000186_1.pdf">Table of a(0) - a(25), circa 1968</a>
%H A000186 Vladimir Shevelev, <a href="http://arxiv.org/abs/1104.4051">Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha, beta, gamma)</a>, arXiv preprint arXiv:1104.4051[math.CO], 2011.
%H A000186 D. S. Stones and I. M. Wanless, <a href="https://doi.org/10.1016/j.jcta.2009.03.019">Divisors of the number of Latin rectangles</a>, J. Combin. Theory Ser. A 117 (2010), 204-215.
%H A000186 <a href="/index/La#Latin">Index entries for sequences related to Latin squares and rectangles</a>
%F A000186 a(n) = n!*Sum_{k+j<=n} (2^j/j!)*k!*binomial(-3*(k+1), n-k-j).
%F A000186 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 and U() represents the menage numbers given by Riordan, p. 209 gives the wrong answers unless we set U(1) = -1 (or in other words we must take U() = A000179). With U(1) = 0 (see A335700) 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. Additional changes from _William P. Orrick_, Aug 12 2020
%F A000186 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
%F A000186 a(n) ~ n!^2/exp(3). - _Vaclav Kotesovec_, Sep 08 2016
%F A000186 a(n+p)-2*a(n) is divisible by p for any prime p. - _Mark van Hoeij_, Jun 13 2019
%p A000186 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:
%p A000186 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. Additional comment and modifications of code due to changes in underlying sequences from _William P. Orrick_, Aug 12 2020: Eq. (30) and Eq. (30a) are, in fact, related to each other by a trivial transformation and are both valid. Current code is based on Eq. (30a).
%p A000186 # A000166
%p A000186 unprotect(D);
%p A000186 D := proc(n) option remember; if n<=1 then 1-n else (n-1)*(D(n-1)+D(n-2));fi; end;
%p A000186 [seq(D(n), n=0..30)];
%p A000186 # A000179
%p A000186 U := proc(n) if n=0 then 1 else add ((-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k), k=0..n); fi; end;
%p A000186 [seq(U(n), n=0..30)];
%p A000186 # A000186
%p A000186 K:=proc(n) local k; global D, U; add( binomial(n,k)*D(n-k)*D(k)*U(n-2*k), k=0..floor(n/2) ); end;
%p A000186 [seq(K(n), n=0..30)];
%p A000186 # another Maple program:
%p A000186 a:= proc(n) option remember; `if`(n<5, [1, 0, 0, 2, 24][n+1],
%p A000186      ((n-1)*(n^2-2*n+2)*a(n-1) +(n-1)*(n-2)*(n^2-2*n+2)*a(n-2)
%p A000186       +(n-1)*(n-2)*(n^2-2*n-2) *a(n-3)
%p A000186       +2*(n-1)*(n-2)*(n-3)*(n^2-5*n+3) *a(n-4)
%p A000186       -4*(n-2)*(n-3)*(n-4)*(n-1)^2 *a(n-5)) / (n-2))
%p A000186     end:
%p A000186 seq(a(n), n=0..25);  # _Alois P. Heinz_, Nov 02 2013
%t A000186 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 *)
%o A000186 (SageMath)
%o A000186 # after Maple code based on Riordan's Eq. (30a)
%o A000186 d = [1,0]
%o A000186 for j in range(2,31):
%o A000186     d.append((j - 1) * (d[-1] + d[-2]))
%o A000186 def u(n):
%o A000186     if n == 0:
%o A000186         return 1
%o A000186     else:
%o A000186         return sum((-1)^k * (2 * n) * binomial(2 * n - k, k) * factorial(n - k) / (2 * n - k) for k in range(0, n + 1))
%o A000186 def k(n):
%o A000186     return sum(binomial(n, k) * d[n - k] * d[k] * u(n - 2 * k) for k in range(0, floor(n / 2) + 1))
%o A000186 [k(n) for n in range(0, 31)] # _William P. Orrick_, Aug 12 2020
%Y A000186 Cf. A000512, A000166, A000179, A335700, A170904.
%K A000186 nonn,nice,easy
%O A000186 0,4
%A A000186 _N. J. A. Sloane_
%E A000186 Formula and more terms from _Vladeta Jovovic_, Mar 31 2001
%E A000186 Edited by _N. J. A. Sloane_, Jan 21 2010, Mar 04 2010, Apr 04 2010