A000186 -id:A000186 - cp's OEIS frontend

A174560 Number of 3 X n Latin rectangles whose second row has cycles of even length only.

Original entry on oeis.org

0, 24, 0, 18000, 0, 52254720

Offset: 3

Vladimir Shevelev, Mar 22 2010

V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr. Mat.(J. of the Akademy of Sciences of Russia) 4(1992), 91-110.

Cf. A000186, A094047, A174556.

A174581 Let J_n be an n X n all-1's matrix, I = I_n the n X n identity matrix and P = P_n the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1) n X n matrices A <= J_n - I - P - P^2 with exactly two 1's in every row and column.

Original entry on oeis.org

0, 1, 20, 1266, 102574, 9746472

Offset: 4

Vladimir Shevelev, Mar 23 2010

V. S. Shevelev, Development of the rook technique for calculating the cyclic indicators of (0,1)-matrices, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 21-28 (in Russian).
S. E. Grigorchuk, V. S. Shevelev, An algorithm of computing the cyclic indicator of couples discordant permutations with restricted position, Izvestia Vuzov of the North-Caucasus region, Nature sciences 3 (1997), 5-13 (in Russian).

Cf. A001499, A007107, A082491, A000186, A174564, A174580.

A001627 Related to Latin rectangles.

Original entry on oeis.org

1, 0, 2, 44, 1008, 34432, 1629280, 101401344, 8030787968, 788377273856, 93933191303424, 13350759115563520, 2231133728986759168, 433075048506207645696, 96617322164029448916992, 24549315871469898190266368, 7047652261245574026565877760

Offset: 1

N. J. A. Sloane

nonn

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.
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).

Index entries for sequences related to Latin squares and rectangles

a(1) = 1, a(n) = A000186(n) + A000186(n-1) + 3*(n-1)*A001626(n-1). - Sean A. Irvine, Sep 25 2015

More terms from Sean A. Irvine, Sep 25 2015

A170904 Sequence obtained by a formal reading of Riordan's Eq. (30a), p. 206.

Original entry on oeis.org

1, 0, 0, 2, 24, 572, 21280, 1074390, 70299264, 5792903144, 587159944704, 71822748886440, 10435273503677440, 1776780701352504408, 350461958856515690496, 79284041282799128098778, 20392765404792755583221760, 5917934230798152486136427600, 1924427226324694427836833857536

Offset: 0

N. J. A. Sloane, Jan 21 2010

nonn

See the comments in A000186 for further discussion.
Neven Juric alerted me to the fact that Riordan's formula is misleading.
It is not error of Riordan, since, according to the rook theory, he considered U(1) to be -1. [Vladimir Shevelev, Apr 02 2010]
A combinatorial argument, valid for n >= 2, leads to Touchard's formula for the n-th menage number, U(n), a formula which involves the coefficients of Chebyshev polynomials of the first kind. It is combinatorially reasonable to take U(0) = 1 and U(1) = 0, leading to A335700, but taking the connection with Chebyshev polynomials seriously instead gives U(0) = 2 and U(1) = -1, leading to A102761. Riordan derives equation (30) on page 205 for the number of reduced three-line Latin rectangles (A000186) by making use of product identities on Chebyshev polynomials, and therefore requires the second definition; it also requires extending the definition of menage numbers to negative index. Riordan then obtains equation (30a) on page 206 by eliminating the negative indices and redefining U(0) to be 1 (which leads to A000179). A170904 (this sequence) is what is obtained by mistakenly using A335700 instead of A000179 in Riordan's equation (30a). - William P. Orrick, Aug 11 2020

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 206, 209.

# 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)];
# A335700 (equals A000179 except that A335700(1) = 0)
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)];
# bad A000186 (A170904)
Kbad:=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;
[seq(Kbad(n),n=0..30)];

One can enumerate 3 X n Latin rectangles by the formula A000186(2n)=a(2n) and A000186(2n+1)=a(2n+1)-A001700(n)*A000166(n)*A000166(n+1). - Vladimir Shevelev, Apr 04 2010

a(2n)=A000186(2n), a(2n+1)=A000186(2n+1)+A001700(n)*A000166(n)*A000166(n+1). [From Vladimir Shevelev, Apr 02 2010]

Edited by N. J. A. Sloane, Apr 04 2010 following a suggestion from Vladimir Shevelev

A174561 Number of 3 X n Latin rectangles whose second row contains two cycles with the same order of its elements, e.g., the cycle (x_2, x_3, ..., x_k, x_1) with x_1 < x_2 < ... < x_k.

Original entry on oeis.org

12, 120, 2020, 32410, 563948

Offset: 4

Vladimir Shevelev, Mar 22 2010

V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr. Mat.(J. of the Akademy of Sciences of Russia) 4(1992), 91-110.

Cf. A000179, A000186, A094047, A174560, A174556.

A174582 Let J_n be n X n matrix which contains 1's only, I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1,2) n X n matrices A<=2(J_n-I-P-P^2) with exactly one 1 and one 2 in every row and column.

Original entry on oeis.org

0, 2, 72, 3722, 329192, 32842446

Offset: 4

Vladimir Shevelev, Mar 23 2010

V. S. Shevelev, Development of the rook technique for calculating the cyclic indicators of (0,1)-matrices, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 21-28 (in Russian).
S. E. Grigorchuk, V. S. Shevelev, An algorithm of computing the cyclic indicator of couples discordant permutations with restricted position, Izvestia Vuzov of the North-Caucasus region, Nature sciences 3 (1997), 5-13 (in Russian).

A001499 A007107 A082491 A000186 A174564 A174580 A174581

A275921 Number of 5 X n Latin rectangles.

Original entry on oeis.org

56, 9408, 11270400, 27206658048, 112681643083776, 746988383076286464, 7533492323047902093312, 111048869433803210653040640, 2315236533572491933131807916032, 66415035616070432053233927044726784, 2560483881619577552584872021599994249216

Offset: 5

N. J. A. Sloane, Aug 28 2016

nonn

N. J. A. Sloane, Table of n, a(n) for n = 5..40 [Moused from the table in Stones et al. 2016]
R. J. Stones, S. Lin, X. Liu, G. Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1

Cf. A000179, A000186, A001623.

A001568 Related to 3-line Latin rectangles.

Original entry on oeis.org

1, -1, -1, 2, 49, 629, 6961, 38366, -1899687, -133065253, -6482111309, -281940658286, -10702380933551, -247708227641863, 14512103549430397, 3377044611825908414, 433180638973276282801, 47474992085447610990231

Offset: 1

N. J. A. Sloane

S. M. Kerawala, The asymptotic number of three-deep Latin rectangles, Bull. Calcutta Math. Soc., 39 (1947), 71-72.
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).

S. M. Kerawala, The asymptotic number of three-deep Latin rectangles, Bull. Calcutta Math. Soc., 39 (1947), 71-72. [Annotated scanned copy]
S. M. Kerawala, Asymptotic solution of the "Probleme des menages, Bull. Calcutta Math. Soc., 39 (1947), 82-84. [Annotated scanned copy]
Index entries for sequences related to Latin squares and rectangles

def A001568(N):
    a = polygen(QQ, 'a')
    R = PowerSeriesRing(a.parent(), 't', default_prec=N + 2)
    t = R.gen()
    n = 1 / t
    dico = {0: 1}
    for k in range(1, N + 1):
        U = sum(di * t**i / factorial(i) for i, di in dico.items())
        U += a * t**k / factorial(k)
        U = U.O(k + 2)
        delta = -U+(n-1)*(n**2-2*n+2)/n**2/(n-2)*U(t=1/(n-1))+(n**2-2*n+2)/n**2/(n-1)*U(t=1/(n-2))+(n**2-2*n-2)/n**2/(n-1)/(n-2)**2*U(t=1/(n-3))+2*(n*n-5*n+3)/n**2/(n-1)/(n-2)**2/(n-3)*U(t=1/(n-4))-4/n**2/(n-2)**2/(n-3)/(n-4)*U(t=1/(n-5))
        dico[k] = delta[k + 1].numerator().roots()[0][0]
    return list(dico.values())
# F. Chapoton, Jan 01 2022

Signs added by N. J. A. Sloane, Jul 23 2015

More terms from F. Chapoton, Jan 01 2022

A098276 Difference between the number of even reduced Latin rectangles of size 3 X n and the number of odd ones.

Original entry on oeis.org

1, 0, 2, 0, 72, -320, 3600, -32256, 344960, -3926016, 48625920, -648243200, 9270125568, -141579509760, 2300668418048, -39642283376640, 722055883161600, -13863472939925504, 279868860012625920

Offset: 1

Ralf Stephan, Sep 06 2004

Vincenzo Librandi, Table of n, a(n) for n = 1..200
J. Zeng, The generating function for the difference in even and odd three-line latin rectangles, Ann. Sci. Math. Quebec 20/1 (1996) 105-108. [alternate link]

Cf. A000186.

Rest[CoefficientList[Series[x + ((1-x)^2/(1+x)+x/(1+x)^2)*E^(2*x), {x, 0, 20}], x]* Range[0, 20]!] (* Vaclav Kotesovec, Sep 29 2013 *)

a(n)=polcoeff(serlaplace(exp(2*x)*((1-x)^2/(1+x)+x/(1+x)^2)),n)

a(n)=(-1)^(n-1)*(n-2)*n!/2*polcoeff(Ser(exp(2*(atanh(x)-x))),n)

E.g.f.: x + [(1-x)^2/(1+x)+x/(1+x)^2] * exp(2x). - corrected by Vaclav Kotesovec, Sep 29 2013

a(n) ~ n! * (-1)^(n+1) * n * exp(-2). - Vaclav Kotesovec, Sep 29 2013

A174563 Number of 3 X n Latin rectangles such that every element of the second row has the same cyclic order (see comment).

Original entry on oeis.org

1, 14, 133, 3300, 93889, 3391086, 148674191, 7796637196, 480640583751, 34370030511334, 2818294139246649, 262403744798653716, 27506121212584723373, 3222018028986227724702, 418998630100386520363619, 60138044879434564251209580, 9477043948863636836099726259, 1632099068624734991723488992214

Offset: 3

Vladimir Shevelev, Mar 22 2010

nonn

We say that an element alpha_i of a permutation alpha of {1,2,...,n} has cyclic order k if it belongs to a cycle of length k of alpha. If every cycle of alpha has length k, then k|n.

V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr. Mat. [Journal published by the Academy of Sciences of Russia], 4 (1992), 91-110.
V. S. Shevelev, Modern enumeration theory of permutations with restricted positions, Diskr. Mat., 1993, 5, no.1, 3-35 (Russian) [English translation in Discrete Math. and Appl., 1993, 3:3, 229-263 (pp. 255-257)].

Cf. A000179, A000186, A000296, A094047, A174556, A174560, A174561.

Let G_n = A000296(n) = n! * Sum_{2*k_2+...+n*k_n=n, k_i>=0} Product_{i=2,...,n} (k_i!*i!^k_i)^(-1). Then a(n) = Sum_{k=0,...,floor(n/2)} binomial(n,k) * G_k * G_(n-k) * u_(n-2*k), where u(n) = A000179(n). - Vladimir Shevelev, Mar 30 2016

More terms from William P. Orrick, Jul 25 2020

cp's OEIS Frontend

A174560 Number of 3 X n Latin rectangles whose second row has cycles of even length only.

Views

Author

Keywords

Links

Crossrefs

A174581 Let J_n be an n X n all-1's matrix, I = I_n the n X n identity matrix and P = P_n the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1) n X n matrices A <= J_n - I - P - P^2 with exactly two 1's in every row and column.

Views

Author

Keywords

References

Crossrefs

A001627 Related to Latin rectangles.

Views

Author

Keywords

References

Links

Formula

Extensions

A170904 Sequence obtained by a formal reading of Riordan's Eq. (30a), p. 206.

Views

Author

Keywords

Comments

References

Programs

Maple

Formula

Extensions

A174561 Number of 3 X n Latin rectangles whose second row contains two cycles with the same order of its elements, e.g., the cycle (x_2, x_3, ..., x_k, x_1) with x_1 < x_2 < ... < x_k.

Views

Author

Keywords

Links

Crossrefs

A174582 Let J_n be n X n matrix which contains 1's only, I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1,2) n X n matrices A<=2(J_n-I-P-P^2) with exactly one 1 and one 2 in every row and column.

Views

Author

Keywords

References

Crossrefs

A275921 Number of 5 X n Latin rectangles.

Views

Author

Keywords

Links

Crossrefs

A001568 Related to 3-line Latin rectangles.

Views

Author

Keywords

References

Links

Programs

Sage

Extensions

A098276 Difference between the number of even reduced Latin rectangles of size 3 X n and the number of odd ones.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A174563 Number of 3 X n Latin rectangles such that every element of the second row has the same cyclic order (see comment).

Views

Author

Keywords

Comments

References

Crossrefs

Formula

Extensions