A333157 -id:A333157 - cp's OEIS frontend

A008300 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= n) gives number of {0,1} n X n matrices with all row and column sums equal to k.

1, 1, 1, 1, 2, 1, 1, 6, 6, 1, 1, 24, 90, 24, 1, 1, 120, 2040, 2040, 120, 1, 1, 720, 67950, 297200, 67950, 720, 1, 1, 5040, 3110940, 68938800, 68938800, 3110940, 5040, 1, 1, 40320, 187530840, 24046189440, 116963796250, 24046189440, 187530840, 40320, 1, 1, 362880, 14398171200, 12025780892160, 315031400802720, 315031400802720, 12025780892160, 14398171200, 362880, 1

Offset: 0

N. J. A. Sloane

Or, triangle of multipermutation numbers T(n,k), n >= 0, 0 <= k <= n: number of relations on an n-set such that all vertical sections and all horizontal sections have k elements.

			Triangle begins:
  1;
  1,    1;
  1,    2,       1;
  1,    6,       6,        1;
  1,   24,      90,       24,        1;
  1,  120,    2040,     2040,      120,       1;
  1,  720,   67950,   297200,    67950,     720,    1;
  1, 5040, 3110940, 68938800, 68938800, 3110940, 5040, 1;
  ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 236, P(n,k).

Brendan D. McKay, Rows n = 0..30, flattened
C. J. Everett and P. R. Stein, The asymptotic number of integer stochastic matrices, Disc. Math. 1 (1971), 55-72.
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.
Richard J. Mathar, Rencontres for equipartite distributions of multisets of colored balls into urns, vixra:2306.0157 (2023)
B. D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221.
Brendan D. McKay, first 30 rows : entries named Bv[n,k,n,k]
Wouter Meeussen, relevant entries from B. D. McKay reference

Row sums give A067209.
Central coefficients are A058527.
Cf. A000142 (column 1), A001499 (column 2), A001501 (column 3), A058528 (column 4), A075754 (column 5), A172544 (column 6), A172541 (column 7), A172536 (column 8), A172540 (column 9), A172535 (column 11), A172534 (column 12), A172538 (column 13), A172537 (column 14).
Cf. A133687, A333157 (symmetric matrices), A257493 (nonnegative elements), A260340 (up to row permutations), A364068 (traceless).

T(n, k)={
  local(M=Map(Mat([n, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(i, p, v, e) = if(i<0, if(!e, acc(p, v)), my(t=polcoef(p,i)); for(j=0, min(t, e), self()(i-1, p+j*(x-1)*x^i, binomial(t, j)*v, e-j))));
  for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(k-1, src[i, 1], src[i, 2], k))); vecsum(Mat(M)[,2]);
} \\ Andrew Howroyd, Apr 03 2020

Comtet quotes Everett and Stein as showing that T(n,k) ~ (kn)!(k!)^(-2n) exp( -(k-1)^2/2 ) for fixed k as n -> oo.

T(n,k) = T(n,n-k).

More terms from Greg Kuperberg, Feb 08 2001

A188403 T(n,k) = Number of (n*k) X k binary arrays with rows in nonincreasing order, n ones in every column and no more than 2 ones in any row.

Original entry on oeis.org

1, 2, 1, 4, 3, 1, 10, 11, 4, 1, 26, 56, 23, 5, 1, 76, 348, 214, 42, 6, 1, 232, 2578, 2698, 641, 69, 7, 1, 764, 22054, 44288, 14751, 1620, 106, 8, 1, 2620, 213798, 902962, 478711, 62781, 3616, 154, 9, 1, 9496, 2313638, 22262244, 20758650, 3710272, 222190, 7340, 215, 10, 1

Offset: 1

R. H. Hardin, Mar 30 2011

From Andrew Howroyd, Apr 09 2020: (Start)
T(n,k) is the number of k X k symmetric matrices with nonnegative integer entries and all row and column sums n. The number of such matrices up to isomorphism is given in A333737.
T(n,k) is also the number of loopless multigraphs with k labeled nodes of degree n or less. The number of such multigraphs up to isomorphism is given in A333893. (End)

			Table starts
  1  2   4    10      26        76         232          764          2620
  1  3  11    56     348      2578       22054       213798       2313638
  1  4  23   214    2698     44288      902962     22262244     648446612
  1  5  42   641   14751    478711    20758650   1158207312   80758709676
  1  6  69  1620   62781   3710272   313568636  36218801244 5518184697792
  1  7 106  3616  222190  22393101  3444274966 767013376954 ...
  1  8 154  7340  681460 111200600 29445929253 ...
  1  9 215 13825 1865715 472211360 ...
  1 10 290 24510 4655535 ...
  1 11 381 41336 ...
  ...
All solutions for 4 X 2:
..1..0....1..1....1..1
..1..0....1..1....1..0
..0..1....0..0....0..1
..0..1....0..0....0..0

Andrew Howroyd, Table of n, a(n) for n = 1..351 (first 95 terms from R. H. Hardin; terms 96..153 from Alois P. Heinz)
J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962, 2014

Columns 1..8 are A000012, A000027(n+1), A019298(n+1), A053493, A053494, A188400, A188401, A188402.
Rows 1..8 are A000085, A000985, A188404, A188405, A188406, A188407, A188408, A188409.
Main diagonal is A333739.
Cf. A257493, A333157, A333737, A333893.

T(k,n)={
  local(M=Map(Mat([0, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(r, h, p, q, v, e) = if(!p, acc(x^e+q, v), my(i=poldegree(p), t=pollead(p)); self()(r, k, p-t*x^i, q+t*x^i, v, e); for(m=1, h-i, for(j=1, min(t, (k-e)\m), self()(r, if(j==t, k, i+m-1), p-j*x^i, q+j*x^(i+m), binomial(t, j)*v, e+j*m)))));
  for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(n-r, k, src[i, 1], 0, src[i, 2], 0))); vecsum(Mat(M)[,2]);
}
{for(n=1, 7, for(k=1, 7, print1(T(n,k),", ")); print)} \\ Andrew Howroyd, Apr 08 2020

A333159 Triangle read by rows: T(n,k) is the number of non-isomorphic n X n symmetric binary matrices with k ones in every row and column up to permutation of rows and columns.

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, 5, 4, 1, 1, 1, 1, 4, 12, 12, 4, 1, 1, 1, 1, 7, 31, 66, 31, 7, 1, 1, 1, 1, 8, 90, 433, 433, 90, 8, 1, 1, 1, 1, 12, 285, 3442, 7937, 3442, 285, 12, 1, 1, 1, 1, 14, 938, 30404, 171984, 171984, 30404, 938, 14, 1, 1

Offset: 0

Andrew Howroyd, Mar 10 2020

Rows and columns may be permuted independently. The case that rows and columns must be permuted together is covered by A333161.

T(n,k) is the number of k-regular bicolored graphs on 2n unlabeled nodes which are invariant when the two color classes are exchanged.

			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,   5,    4,    1,    1;
  1, 1,  4,  12,   12,    4,    1,   1;
  1, 1,  7,  31,   66,   31,    7,   1,  1;
  1, 1,  8,  90,  433,  433,   90,   8,  1, 1;
  1, 1, 12, 285, 3442, 7937, 3442, 285, 12, 1, 1;
  ...
The T(2,1) = 1 matrix is:
  [1 0]
  [0 1]
.
The T(4,2)= 2 matrices are:
  [1 1 0 0]   [1 1 0 0]
  [1 1 0 0]   [1 0 1 0]
  [0 0 1 1]   [0 1 0 1]
  [0 0 1 1]   [0 0 1 1]

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

Columns k=0..4 are A000012, A000012, A002865, A000840, A000843.
Row sums are A333160.
Central coefficients are A333165.
Cf. A008327, A122082, A333157, A133687, A333161.

T(n,k) = T(n,n-k).

A333351 Array read by antidiagonals: T(n,k) is the number of k-regular loopless multigraphs on n labeled nodes, n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 3, 1, 1, 0, 1, 0, 6, 0, 1, 1, 0, 1, 1, 10, 22, 15, 1, 1, 0, 1, 0, 15, 0, 130, 0, 1, 1, 0, 1, 1, 21, 158, 760, 822, 105, 1, 1, 0, 1, 0, 28, 0, 3355, 0, 6202, 0, 1, 1, 0, 1, 1, 36, 654, 12043, 93708, 190050, 52552, 945, 1, 1, 0, 1, 0, 45, 0, 36935, 0, 3535448, 0, 499194, 0, 1

Offset: 0

Andrew Howroyd, Mar 15 2020

			Array begins:
=================================================================
n\k | 0   1    2      3       4        5         6          7
----+------------------------------------------------------------
  0 | 1   1    1      1       1        1         1          1 ...
  1 | 1   0    0      0       0        0         0          0 ...
  2 | 1   1    1      1       1        1         1          1 ...
  3 | 1   0    1      0       1        0         1          0 ...
  4 | 1   3    6     10      15       21        28         36 ...
  5 | 1   0   22      0     158        0       654          0 ...
  6 | 1  15  130    760    3355    12043     36935     100135 ...
  7 | 1   0  822      0   93708        0   3226107          0 ...
  8 | 1 105 6202 190050 3535448 45163496 431400774 3270643750 ...
  ...

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

Rows n=4..6 are A000217(n+1), A244868 (with interspersed zeros), A244878.
Columns k=0..4 are A000012, A123023, A002137, A108243 (with interspersed zeros), A367497.
Cf. A059441 (graphs), A333157, A333330 (unlabeled nodes), A333467 (with loops).

MultigraphsByDegreeSeq(n, limit, ok)={
  local(M=Map(Mat([0, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(r, h, p, q, v, e) = if(!p, if(ok(x^e+q, r), acc(x^e+q, v)), my(i=poldegree(p), t=pollead(p)); self()(r, limit, p-t*x^i, q+t*x^i, v, e); for(m=1, h-i, for(k=1, min(t, (limit-e)\m), self()(r, if(k==t, limit, i+m-1), p-k*x^i, q+k*x^(i+m), binomial(t, k)*v, e+k*m)))));
  for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(n-r, limit, src[i, 1], 0, src[i, 2], 0))); Mat(M);
}
T(n,k)={if((n%2&&k%2)||(n==1&&k>0), 0, vecsum(MultigraphsByDegreeSeq(n, k, (p,r)->subst(deriv(p), x, 1)>=(n-2*r)*k)[,2]))}
{ for(n=0, 8, for(k=0, 7, print1(T(n,k), ", ")); print) }

A334548 Array read by antidiagonals: T(n,k) is the number of n X n symmetric binary matrices with no row sum greater than k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 8, 14, 1, 1, 2, 8, 45, 43, 1, 1, 2, 8, 64, 315, 142, 1, 1, 2, 8, 64, 809, 2634, 499, 1, 1, 2, 8, 64, 1024, 13846, 25518, 1850, 1, 1, 2, 8, 64, 1024, 28217, 301262, 280257, 7193, 1, 1, 2, 8, 64, 1024, 32768, 1146419, 8035168, 3434595, 29186, 1

Offset: 0

Andrew Howroyd, May 08 2020

			Array begins:
=============================================================
n\k | 0    1      2       3        4         5         6
----|-------------------------------------------------------
  0 | 1    1      1       1        1         1         1 ...
  1 | 1    2      2       2        2         2         2 ...
  2 | 1    5      8       8        8         8         8 ...
  3 | 1   14     45      64       64        64        64 ...
  4 | 1   43    315     809     1024      1024      1024 ...
  5 | 1  142   2634   13846    28217     32768     32768 ...
  6 | 1  499  25518  301262  1146419   1914733   2097152 ...
  7 | 1 1850 280257 8035168 62951431 178499118 254409765 ...
  ...

Column k=0..9 are A000012, A005425, A139678, A139679, A139680, A139681, A139682, A139683, A139684, A139685.

Cf. A006125, A135589, A333157.

T(n,k) = 2^(n*(n+1)/2) = A006125(n+1) for k >= n.

A139670 Number of n X n symmetric binary matrices with all row sums 4.

Original entry on oeis.org

1, 26, 820, 35150, 1944530, 133948836, 11234051976, 1127512146540, 133475706272700, 18406586045919060, 2925154024273348296, 530686776655470875076, 109004840145995702773410, 25164525076896596670014400, 6486836210471246515195539840, 1856264107759263993451053077856

Offset: 4

R. H. Hardin, Jun 12 2008

nonn

From R. J. Mathar, Apr 07 2017: (Start)
These are the row sums of the following triangle, which shows in row n and column t the number of symmetric n X n {0,1}-matrices with trace t and 4 ones in each row and each column, 0 <= t <= n:
   1;
   0,     0;
   0,     0,     0;
   0,     0,     0,     0;
   0,     0,     0,     0,     1;
   1,     0,    10,     0,    15,     0;
  15,     0,   270,     0,   465,     0,    70;
 465,     0,  9660,     0, 19355,     0,  5670,     0;
(End)

Andrew Howroyd, Table of n, a(n) for n = 4..30

Column k=4 of A333157 and row 4 of A188448.

Cf. A000085 (row sums 1), A000986 (row sums 2), A110040 (row sums 3).

Terms a(13) and beyond from Andrew Howroyd, Mar 09 2020

A333161 Triangle read by rows: T(n,k) is the number of k-regular graphs on n unlabeled nodes with half-edges.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 3, 3, 3, 1, 1, 3, 4, 4, 3, 1, 1, 4, 8, 12, 8, 4, 1, 1, 4, 10, 24, 24, 10, 4, 1, 1, 5, 17, 70, 118, 70, 17, 5, 1, 1, 5, 24, 172, 634, 634, 172, 24, 5, 1, 1, 6, 36, 525, 4428, 9638, 4428, 525, 36, 6, 1, 1, 6, 50, 1530, 35500, 187990, 187990, 35500, 1530, 50, 6, 1

Offset: 0

Andrew Howroyd, Mar 11 2020

A half-edge is like a loop except it only adds 1 to the degree of its vertex.
T(n,k) is the number of non-isomorphic n X n symmetric binary matrices with k ones in every row and column and isomorphism being up to simultaneous permutation of rows and columns. The case that allows independent permutations of rows and columns is covered by A333159.
T(n,k) is the number of simple graphs on n unlabeled vertices with every vertex degree being either k or k-1.

			Triangle begins:
  1;
  1, 1;
  1, 2,  1;
  1, 2,  2,   1;
  1, 3,  3,   3,    1;
  1, 3,  4,   4,    3,    1;
  1, 4,  8,  12,    8,    4,    1;
  1, 4, 10,  24,   24,   10,    4,   1;
  1, 5, 17,  70,  118,   70,   17,   5,  1;
  1, 5, 24, 172,  634,  634,  172,  24,  5, 1;
  1, 6, 36, 525, 4428, 9638, 4428, 525, 36, 6, 1;
  ...
The a(2,1) = 2 adjacency matrices are:
  [0 1]  [1 0]
  [1 0]  [0 1]
.
The A(4,2) = 3 adjacency matrices are:
  [0 0 1 1]   [1 1 0 0]   [1 1 0 0]
  [0 0 1 1]   [1 1 0 0]   [1 0 1 0]
  [1 1 0 0]   [0 0 1 1]   [0 1 0 1]
  [1 1 0 0]   [0 0 1 1]   [0 0 1 1]

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

Columns k=0..3 are A000012, A004526(n+2), A186417, A333163.
Row sums are A333162.
Central coefficients are A333166.
Cf. A051031, A333157, A333159.

T(n,k) = T(n, n-k).

A322698 Number of regular graphs with half-edges on n labeled vertices.

Original entry on oeis.org

1, 2, 4, 10, 40, 278, 3554, 84590, 3776280, 317806466, 50710452574, 15414839551538, 8964708979273634, 10008446308186072290, 21518891146915893435358, 89320970210116481106835986, 717558285660687970023516336792, 11176382741327158622885664697124082, 338202509574712032788035618665293979610

Offset: 0

Gus Wiseman, Dec 23 2018

nonn

A graph is regular if all vertices have the same degree. A half-edge is like a loop except it only adds 1 to the degree of its vertex.

			The a(3) = 10 edge sets:
  {}
  {{1},{2,3}}
  {{3},{1,2}}
  {{2},{1,3}}
  {{1},{2},{3}}
  {{1,2},{1,3},{2,3}}
  {{1},{3},{1,2},{2,3}}
  {{1},{2},{1,3},{2,3}}
  {{2},{3},{1,2},{1,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3}}

Wikipedia, Regular graph

Row sums of A333157.

Cf. A058891, A059441, A116539, A283877, A295193, A319189, A319190, A319612, A319729.

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s,{s,Union/@Select[Tuples[Range[n],2],OrderedQ]}],Sequence@@Table[{x[i],0,k},{i,n}]],{k,0,n-1}],{n,1,6}]

for(n=1, 10, print1(A322698(n), ", ")) \\ See A295193 for script, Andrew Howroyd, Aug 28 2019

a(10)-a(18) from Andrew Howroyd, Aug 28 2019

A333164 Number of 2n X 2n symmetric matrices with entries in {+1, -1} and all rows and columns summing to zero.

Original entry on oeis.org

1, 2, 18, 1760, 1944530, 26615510712, 4762109992158288, 11528251571501588791296, 386860001875783390762182911250, 183238648400953515891207813311894423000, 1242327573587456839123512395835593196519781229768, 121917941188016997420391711911475819481799846311888884541952

Offset: 0

Andrew Howroyd, Mar 11 2020

nonn

a(n) is the number of 2n X 2n symmetric binary matrices with n ones in every row and column.

			The a(1) = 2 matrices are:
  [ 1 -1]  [-1  1]
  [-1  1]  [ 1 -1]

Central coefficients of A333157.

Cf. A213793, A333165, A333166.

a(n) = A333157(2*n, n).

a(n) = A213793(2*n). - Andrew Howroyd, Apr 08 2020

A139671 Number of n X n symmetric binary matrices with all row sums 5.

Original entry on oeis.org

1, 76, 6912, 848932, 133948836, 26615510712, 6549149852112, 1966499966796816, 711040444591249476, 305907023641901084832, 154921887640109512226304, 91469751377953081098144816, 62419855497729620428436222688, 48849705066296300911892229634944

Offset: 5

R. H. Hardin, Jun 12 2008

nonn

Andrew Howroyd, Table of n, a(n) for n = 5..25

Column k=5 of A333157 and row 5 of A188448.

Terms a(13) and beyond from Andrew Howroyd, Mar 09 2020

cp's OEIS Frontend

A008300 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= n) gives number of {0,1} n X n matrices with all row and column sums equal to k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A188403 T(n,k) = Number of (n*k) X k binary arrays with rows in nonincreasing order, n ones in every column and no more than 2 ones in any row.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A333159 Triangle read by rows: T(n,k) is the number of non-isomorphic n X n symmetric binary matrices with k ones in every row and column up to permutation of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A333351 Array read by antidiagonals: T(n,k) is the number of k-regular loopless multigraphs on n labeled nodes, n >= 0, k >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A334548 Array read by antidiagonals: T(n,k) is the number of n X n symmetric binary matrices with no row sum greater than k.

Views

Author

Keywords

Examples

Crossrefs

Formula

A139670 Number of n X n symmetric binary matrices with all row sums 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A333161 Triangle read by rows: T(n,k) is the number of k-regular graphs on n unlabeled nodes with half-edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A322698 Number of regular graphs with half-edges on n labeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A333164 Number of 2n X 2n symmetric matrices with entries in {+1, -1} and all rows and columns summing to zero.