A000512 -id:A000512 - cp's OEIS frontend

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

1, 0, 0, 2, 24, 552, 21280, 1073760, 70299264, 5792853248, 587159944704, 71822743499520, 10435273503677440, 1776780700509416448, 350461958856515690496, 79284041282622163140608, 20392765404792755583221760, 5917934230798104348783083520, 1924427226324694427836833857536

Offset: 0

N. J. A. Sloane

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

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

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
K. P. Bogart and J. Q. Longyear, Counting 3 by n Latin rectangles, Proc. Amer. Math. Soc., 54 (1976), 463-467.
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]
John Riordan, Table of a(0) - a(25), circa 1968
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha, beta, gamma), arXiv preprint arXiv:1104.4051[math.CO], 2011.
D. S. Stones and I. M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A 117 (2010), 204-215.
Index entries for sequences related to Latin squares and rectangles

Cf. A000512, A000166, A000179, A335700, A170904.

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. 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).
# 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=0 then 1 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)];
# 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;
[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

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

# after Maple code based on Riordan's Eq. (30a)
d = [1,0]
for j in range(2,31):
    d.append((j - 1) * (d[-1] + d[-2]))
def u(n):
    if n == 0:
        return 1
    else:
        return sum((-1)^k * (2 * n) * binomial(2 * n - k, k) * factorial(n - k) / (2 * n - k) for k in range(0, n + 1))
def k(n):
    return sum(binomial(n, k) * d[n - k] * d[k] * u(n - 2 * k) for k in range(0, floor(n / 2) + 1))
[k(n) for n in range(0, 31)] # William P. Orrick, Aug 12 2020

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 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
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
a(n+p)-2*a(n) is divisible by p for any prime p. - Mark van Hoeij, Jun 13 2019

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

A133687 Triangle with number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to k (0<=k<=n), where equivalence is defined by row and column permutations.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 4, 7, 4, 1, 1, 1, 1, 4, 16, 16, 4, 1, 1, 1, 1, 7, 51, 194, 51, 7, 1, 1, 1, 1, 8, 224, 3529, 3529, 224, 8, 1, 1, 1, 1, 12, 1165, 121790, 601055, 121790, 1165, 12, 1, 1, 1, 1, 14, 7454, 5582612, 156473848, 156473848, 5582612, 7454, 14, 1, 1

Offset: 0

Joost Vermeij (joost_vermeij(AT)live.nl), Jan 04 2008

T(n,k) = T(n,n-k). When 0 and 1 are switched, the number of equivalence classes remain the same.

Terms may be computed without generating each matrix by enumerating the number of matrices by column sum sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A008300. Burnside's lemma can be used to extend this method to the unlabeled case. This seems to require looping over partitions for both rows and columns. The number of partitions squared increases rapidly with n. For example, A000041(20)^2 = 393129. - Andrew Howroyd, Apr 03 2020

			Triangle begins:
  1;
  1, 1;
  1, 1, 1;
  1, 1, 1,   1;
  1, 1, 2,   1,    1;
  1, 1, 2,   2,    1,    1;
  1, 1, 4,   7,    4,    1,   1;
  1, 1, 4,  16,   16,    4,   1, 1;
  1, 1, 7,  51,  194,   51,   7, 1, 1;
  1, 1, 8, 224, 3529, 3529, 224, 8, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..189

Columns k=0..5 are A000012, A000012, A002865, A000512, A000513, A000516.
Row sums are A333681.
T(2n,n) gives A333740.
Cf. A000519, A008300 (labeled case), A008327 (bipartite graphs), A333159 (symmetric case).

Sum_{k=1..n} T(n, k) = A000519(n).

Missing a(72) inserted by Andrew Howroyd, Apr 01 2020

A000513 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 4, where equivalence is defined by row and column permutations. Also number of isomorphism classes of bicolored quartic bipartite graphs, where isomorphism cannot exchange the colors.

Original entry on oeis.org

0, 0, 0, 1, 1, 4, 16, 194, 3529, 121790, 5582612, 317579783, 21543414506, 1711281449485, 157117486414656, 16502328443493967, 1965612709107379155, 263512349078757245789, 39497131936385398782814, 6579940884199010139737829, 1211896874083479131415289345, 245593008009270037388205883048

Offset: 1

Eric Rogoyski

nonn

			a(4) = 1:
1111
1111
1111
1111
a(5)=1:
01111
10111
11011
11101
11110
Two of the four examples with n = 6:
111100 . 111100
110011 . 011110
001111 . 001111
111100 . 100111
110011 . 110011
001111 . 111001

A. Burgess, P. Danziger, E. Mendelsohn, B. Stevens, Orthogonally Resolvable Cycle Decompositions, 2013; http://www.math.ryerson.ca/~andrea.burgess/OCD-submit.pdf

A. Al-Azemi, Isomorph-rejection: theory and an application, Kuwait J. Sci., 39 (2A) (2012), 1-14. - From _N. J. A. Sloane_, Mar 01 2013
A. Burgess, P. Danziger, E. Mendelsohn, B. Stevens, Orthogonally Resolvable Cycle Decompositions, Journal of Combinatorial Designs, Volume 23, Issue 8, August 2015, Pages 328-351.
Index entries for sequences related to Latin squares and rectangles

Column k=4 of A133687.

Cf. A000512.

Definition corrected by Brendan McKay, May 28 2006
Offset corrected and a(12) added (from Al-Azemi) by N. J. A. Sloane, Mar 01 2013
Terms a(13) and beyond from Andrew Howroyd, Apr 01 2020

A229161 Number of n X n binary matrices with exactly 2 ones in each row and column, and with rows and columns in lexicographically nondecreasing order.

Original entry on oeis.org

0, 1, 1, 2, 5, 13, 42, 155, 636, 2889, 14321, 76834, 443157

Offset: 1

N. J. A. Sloane, Sep 15 2013

A column of A227061.
From Brendan McKay, Sep 16 2013: (Start)
If all row and column permutations are allowed, one gets A002865 for k=2, A000512 for k=3, A000513 for k=4, A000516 for k=5, etc., where k = number of 1's in each row and column. See also A133687.
A229161 is strictly different from A002865, which gives the number of equivalence classes of n X n binary matrices with exactly 2 1's in each row and column, up to permutations of rows and columns.
For example, take two non-equivalent n X n matrices A,B which are in sorted form (i.e. the rows are in increasing order and so are the columns). Now form a 2n X 2n matrix by placing A and B in the off-diagonal blocks and zeros in the two diagonal blocks.  This matrix is in sorted form.  Interchanging A and B gives a different matrix that is also in sorted form, and yet it is easily produced from the first matrix by permuting rows and columns.  That is, one equivalence class can contain two different sorted matrices.  I expect that on average the number of sorted matrices per equivalence class is exponentially large.
(End)

K. Yordzhev, On an Algorithm for Isomorphism-Free Generations of Combinatorial Objects, International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), Web Site: www.ijettcs.org, Volume 2, Issue 6, November - December 2013, ISSN 2278-6856

K. Yordzhev, Fibonacci sequence related to a combinatorial problem on binary matrices, arXiv preprint arXiv:1305.6790, 2013
K. Yordzhev, Semi-canonical binary matrices, arXiv preprint arXiv:1506.04642, 2015

Cf. A229162, A229163, A229164, A181344, A181345, A002865, A000512, A000513, A000516, A133687.

Better definition and values of a(12)-a(13) from R. H. Hardin, Sep 17 2013

A000840 Number of cubic bicolored graphs on n unlabeled nodes admitting an automorphism exchanging the colors.

Original entry on oeis.org

0, 0, 1, 1, 2, 5, 12, 31, 90, 285, 938, 3285, 11983, 45390, 177803, 718390, 2986407, 12749364, 55802982, 250068732, 1145923828, 5363795830, 25620207380, 124767647097, 618983876918, 3126035142910, 16060182735947, 83883575376862, 445164927249466, 2399098651337048

Offset: 1

Brendan McKay and Eric Rogoyski

nonn

Column k=3 of A333159.

Cf. A000512, A000843, A004066, A008325.

a(11)-a(30) from Andrew Howroyd, Mar 10 2020

A004066 Number of simple regular trivalent bicolored graphs with 2n nodes.

Original entry on oeis.org

0, 0, 1, 1, 2, 6, 14, 41, 157, 725, 4196, 29817, 246646, 2297088, 23503564, 260265650, 3090341095, 39101587595, 524783295041, 7443251159470, 111222017297268, 1746166043555813, 28734210790531045, 494526547845483641, 8883866458982018870, 166286444108288113541, 3237719185652343485853, 65477290060076644381373

Offset: 1

Gunnar Brinkmann, Brendan McKay and Eric Rogoyski

nonn

Sean A. Irvine, On the difference between A004066 and A008325
Patric R. J. Östergård, Classifying generalized Howell designs, Designs Codes Cryptog. (2025). See Sect. 3.2.1.

Cf. A000512, A000840, A008325 (bipartite), A006823 (connected).

a(n) = (A000840(n) + A000512(n))/2. - Andrew Howroyd, Apr 01 2020

a(1)-a(2) prepended and terms a(15) and beyond from Andrew Howroyd, Apr 01 2020

A181344 Number of n X n matrices over {0,1} with rows and columns summing to 3, rows and columns sorted (>=) by value.

Original entry on oeis.org

0, 0, 1, 1, 5, 25, 161, 1112, 8787, 76156, 728699, 7609065, 86162795, 1050755884, 13728407061, 191309852944

Offset: 1

Michael Steyer (m.steyer(AT)osram.de), Oct 14 2010

			n=4: {1110,1101,1011,0111} is the only matrix where each row (column) - read as a binary number - is equal to or larger than the previous one, so a(4)=1.

Bert Dobbelaere, Illustration of initial terms

Cf. A000512, A001501, A181345.

a(10)-a(16) from Bert Dobbelaere, Feb 23 2020

A000516 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 5, where equivalence is defined by row and column permutations. Isomorphism classes of bicolored 5-regular bipartite graphs, where isomorphism cannot exchange the colors.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 4, 51, 3529, 601055, 156473848, 54062069505, 23869437984682, 13186966476208771, 8971034249976338907, 7414924597575224629299, 7360058177440420943520750, 8683626883245180573511018830, 12066478410398147578519948851818, 19585444567548740264243478805318202

Offset: 1

Eric Rogoyski

nonn

Index entries for sequences related to Latin squares and rectangles

Column k=5 of A133687.

Cf. A000512, A000513.

Definition corrected by Brendan McKay, May 28 2006

Offset corrected and terms a(12) and beyond from Andrew Howroyd, Apr 01 2020

A181345 Number of n X n matrices over {0,1} with rows and columns summing to 3, rows and columns sorted (>) by value.

Original entry on oeis.org

0, 0, 0, 1, 2, 12, 87, 662, 5611, 51141, 509277, 5504398, 64122940, 800741192, 10673478573, 151323048909

Offset: 1

Michael Steyer (m.steyer(AT)osram.de), Oct 18 2010

			n=4: {1110,1101,1011,0111} is the only matrix where each row (column) - read as a binary number - is larger than the previous one, so a(4)=1.

Bert Dobbelaere, Illustration of initial terms

Cf. A000512, A001501, A181344.

Offset corrected and a(10)-a(16) from Bert Dobbelaere, Feb 23 2020

A079815 Number of equivalent classes of n X n 0-1 matrices with 3 1's in each row and column.

Original entry on oeis.org

0, 0, 1, 1, 2, 7, 16, 71

Offset: 1

Michael Steyer (m.steyer(AT)osram.de), Feb 20 2003

Matrices are considered to belong to the same equivalent class if they can be transformed into each other by successive permutations of rows or columns.
In general, to transform 2 equivalent matrices into each other, it is necessary to first permute rows, then columns, then rows and so on.
From Brendan McKay, Aug 27 2010: (Start)
A079815 appears on the surface to describe the same objects as A000512, but I don't know where the term "71" comes from.
Also the comment "In general, to transform 2 equivalent matrices into each other, it is necessary to first permute rows, then columns, then rows and so on." is wrong - actually only one permutation of rows and one permutation of columns is enough.
I will guess that this sequence counts matrices in which both the rows and columns are in sorted order. The reason I suspect that is because a common way to make such matrices is to alternately sort the rows and columns until it stabilizes.
The value of a(8) should be checked. (End)

			n=4: every matrix with 3 1's in each row and column can be transformed by permutation of rows (or columns) into {1110,1101,1011,0111}, therefore a(4)=1.

Cf. A001501.

Edited by N. J. A. Sloane, Sep 04 2010

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

Extensions

A133687 Triangle with number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to k (0<=k<=n), where equivalence is defined by row and column permutations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A000513 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 4, where equivalence is defined by row and column permutations. Also number of isomorphism classes of bicolored quartic bipartite graphs, where isomorphism cannot exchange the colors.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A229161 Number of n X n binary matrices with exactly 2 ones in each row and column, and with rows and columns in lexicographically nondecreasing order.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A000840 Number of cubic bicolored graphs on n unlabeled nodes admitting an automorphism exchanging the colors.

Views

Author

Keywords

Crossrefs

Extensions

A004066 Number of simple regular trivalent bicolored graphs with 2n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A181344 Number of n X n matrices over {0,1} with rows and columns summing to 3, rows and columns sorted (>=) by value.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A000516 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 5, where equivalence is defined by row and column permutations. Isomorphism classes of bicolored 5-regular bipartite graphs, where isomorphism cannot exchange the colors.

Views

Author

Keywords

Links

Crossrefs

Extensions

A181345 Number of n X n matrices over {0,1} with rows and columns summing to 3, rows and columns sorted (>) by value.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions