A000186 -id:A000186 - cp's OEIS frontend

A174584 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) n X n matrices A<=J_n-I-P-P^2-P^3 with exactly two 1's in every row and column.

Original entry on oeis.org

0, 1, 31, 3114, 381022

Offset: 5

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 A174582

A347927 a(n) is the number of reduced Latin trapezoids of height 3, whose top row has n boxes, the middle row has n+1 boxes, and the bottom row has n+2 boxes.

Original entry on oeis.org

1, 6, 68, 1670, 67295, 3825722, 285667270, 26889145828, 3102187523467, 429700007845870, 70303573947346474, 13405343287124139802, 2945521072579394529097, 738633749151050116349946, 209620243382776121032416188, 66830750007674204750148252472, 23780886787936166425634118631117

Offset: 1

Peter Luschny, Oct 22 2021

nonn

			There are 6 reduced Latin trapezoids of height 3 with base of length 4:
----------------------------------------------
    2, 3;       |    4, 3;       |    2, 3;
   3, 1, 2;     |   3, 1, 2;     |   3, 4, 1;
  1, 2, 3, 4;   |  1, 2, 3, 4;   |  1, 2, 3, 4;
-----------------------------------------------
    2, 1;       |    2, 3;       |    2, 3;
   3, 4, 2;     |   3, 4, 2;     |   4, 1, 2;
  1, 2, 3, 4;   |  1, 2, 3, 4;   |  1, 2, 3, 4;
-----------------------------------------------

Peter Luschny, Table of n, a(n) for n = 1..100. Data from George Spahn and Doron Zeilberger, see link.
George Spahn and Doron Zeilberger, Automatic Counting of Generalized Latin Rectangles and Trapezoids, Enumerative Combinatorics and Applications, 2:1 (2022).
George Spahn and Doron Zeilberger, Latin trapezoids with three rows, the first 100 terms.
George Spahn and Doron Zeilberger, Latin trapezoids, a Maple package.

Cf. A002860 (Latin squares), A000186, A001623, A001626.

A174585 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-P^3) with exactly one 1 and one 2 in every row and column.

Original entry on oeis.org

0, 2, 132, 9800, 1309928

Offset: 5

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 A174582 A174584

A176901 Number of 3 X n semireduced Latin rectangles, that is, having exactly n fixed points in the first two rows.

Original entry on oeis.org

4, 72, 1584, 70720, 3948480, 284570496, 25574768128, 2808243910656, 369925183388160, 57585548812887040, 10458478438093154304, 2191805683821733404672, 525011528578874444283904, 142540766765931981615759360, 43542026550306796238178877440, 14867182204795857282384287236096, 5640920219495105293649671985430528

Offset: 3

Vladimir Shevelev, Apr 28 2010

nonn

A Latin rectangle is called reduced if its first row is [1,2,...,n] (the number of 3 X n reduced Latin rectangles is given in A000186). Therefore a Latin rectangle having exactly n fixed points in the first two rows may be called "semireduced". Thus if A1(i), A2(i), i=1,...,n, are the first two rows, then, for every i, either A1(i)=i or A2(i)=i.

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.
V. S. Shevelev, Modern enumeration theory of permutations with restricted positions, Diskr. Mat., 1993, 5, no.1, 3-35 (Russian).
V. S. Shevelev, Modern enumeration theory of permutations with restricted positions, English translation, Discrete Math. and Appl., 1993, 3:3, 229-263 (pp. 255-257).

Cf. A174563, A000179, A000186, A087981, A094047, A174556, A174560, A174561.

Let F_n = A087981(n) = n! * Sum_{2*k_2+...+n*k_n=n, k_i>=0} Product_{i=2..n} 2^k_i/(k_i!*i^k_i). Then a(n) = Sum_{k=0..floor(n/2)} binomial(n,k) * F_k * F_(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

A220905 Triangle read by rows: rook numbers of certain "probleme des rencontres" boards of the second kind of size n X k (0 <= k <= n).

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 6, 6, 2, 1, 24, 132, 176, 24, 1, 60, 960, 4580, 5040, 552, 1, 120, 4260, 52960, 213000, 206592, 21280, 1, 210, 14070, 368830, 3762360, 13109712, 11404960, 1073160

Offset: 0

N. J. A. Sloane, Jan 02 2013

Rows 0 through 2 were not given in the reference and should be checked. (There is a Maple program in the Appendix).

What are the row sums?

			Triangle begins:
  1
  1,   0
  1,   2,     0
  1,   6,     6,      2
  1,  24,   132,    176,      24
  1,  60,   960,   4580,    5040,      552
  1, 120,  4260,  52960,  213000,   206592,    21280
  1, 210, 14070, 368830, 3762360, 13109712, 11404960, 1073160
  ...

F. Alayont and N. Krzywonos, Rook Polynomials in Three and Higher Dimensions, 2012.

Right-hand diagonal is A000186.

A275922 Number of 6 X n Latin rectangles.

Original entry on oeis.org

9408, 16942080, 335390189568, 12952605404381184, 870735405591003709440, 96299552373292505158778880, 16790769154925929673725062021120, 4453330421956050777867897829494620160, 1742101863056111789338065277444595027804160, 978514587314819902819845847828230416011100160000

Offset: 6

N. J. A. Sloane, Aug 28 2016

nonn

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, A275921.

cp's OEIS Frontend

A174584 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) n X n matrices A<=J_n-I-P-P^2-P^3 with exactly two 1's in every row and column.

Views

Author

Keywords

References

Crossrefs

A347927 a(n) is the number of reduced Latin trapezoids of height 3, whose top row has n boxes, the middle row has n+1 boxes, and the bottom row has n+2 boxes.

Views

Author

Keywords

Examples

Links

Crossrefs

A174585 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-P^3) with exactly one 1 and one 2 in every row and column.

Views

Author

Keywords

References

Crossrefs

A176901 Number of 3 X n semireduced Latin rectangles, that is, having exactly n fixed points in the first two rows.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A220905 Triangle read by rows: rook numbers of certain "probleme des rencontres" boards of the second kind of size n X k (0 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A275922 Number of 6 X n Latin rectangles.

Views

Author

Keywords

Links

Crossrefs