A333737 -id:A333737 - cp's OEIS frontend

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.

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

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 5, 3, 1, 1, 1, 5, 8, 10, 3, 1, 1, 1, 6, 14, 26, 16, 4, 1, 1, 1, 7, 20, 61, 60, 29, 4, 1, 1, 1, 8, 30, 128, 243, 184, 45, 5, 1, 1, 1, 9, 40, 254, 800, 1228, 488, 75, 5, 1, 1, 1, 10, 55, 467, 2518, 7252, 6684, 1509, 115, 6, 1

Offset: 0

Andrew Howroyd, Apr 08 2020

T(n,k) is the number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to k and isomorphism being up to simultaneous permutation of rows and columns. The case that allows independent permutations of rows and columns is covered by A333737.

Terms may be computed without generating each graph by enumerating the graphs by degree sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A188403. Burnside's lemma as applied in A192517 can be used to extend this method to the unlabeled case.

			Array begins:
==============================================
n\k | 0 1  2   3    4     5      6       7
----+-----------------------------------------
  0 | 1 1  1   1    1     1      1       1 ...
  1 | 1 1  1   1    1     1      1       1 ...
  2 | 1 2  3   4    5     6      7       8 ...
  3 | 1 2  5   8   14    20     30      40 ...
  4 | 1 3 10  26   61   128    254     467 ...
  5 | 1 3 16  60  243   800   2518    6999 ...
  6 | 1 4 29 184 1228  7252  38194  175369 ...
  7 | 1 4 45 488 6684 78063 772243 6254652 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..377 (antidiagonals 0..26)

Rows n=0..4 are A000012, A000012, A000027(n+1), A006918(n+1), A333897.
Columns k=0..5 are A000012, A008619, A000990, A333894, A333895, A333896.
Cf. A188403, A192517, A263293, A333161, A333330, A333737, A334546.

A106607 Expansion of (1+t^3)^2/((1-t)(1-t^2)^2(1-t^4)).

Original entry on oeis.org

1, 1, 3, 5, 9, 13, 20, 28, 39, 51, 67, 85, 107, 131, 160, 192, 229, 269, 315, 365, 421, 481, 548, 620, 699, 783, 875, 973, 1079, 1191, 1312, 1440, 1577, 1721, 1875, 2037, 2209, 2389, 2580, 2780, 2991, 3211, 3443, 3685, 3939, 4203, 4480, 4768, 5069, 5381, 5707, 6045

Offset: 0

N. J. A. Sloane, May 12 2005

Molien series for 5-dimensional group of order 8.
For of each of the quadrisections the n-th term is a polynomial in n of degree 3. - Ralf Stephan, Nov 16 2010
Number of non-isomorphic 3 X 3 nonnegative integer matrices with all row and column sums equal to n up to permutations of rows and columns. - Andrew Howroyd, Apr 08 2020
Take the square spiral on the square grid, with cells on the spiral numbered starting at 1. Every time the spiral crosses the x- or y-axis, calculate the sum of the numbers on the intersection of the spiral and the axis. This produces the present sequence (see illustration). - Karl-Heinz Hofmann, Aug 14 2022

			The a(4) = 9 symmetric matrices are:
  [0 0 4]  [0 1 3]  [0 1 3]  [0 2 2]  [0 2 2]
  [0 4 0]  [1 2 1]  [1 3 0]  [2 0 2]  [2 1 1]
  [4 0 0]  [3 1 0]  [3 0 1]  [2 2 0]  [2 1 1]
.
  [1 1 2]  [1 0 3]  [1 1 2]  [2 0 2]
  [1 2 1]  [0 4 0]  [1 3 0]  [0 4 0]
  [2 1 1]  [3 0 1]  [2 0 2]  [2 0 2]

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. Ling and P. Solé, Type II Codes over F_4 + u F_4, European J. Combinatorics, 22 (2001), pp. 983-997.
Karl-Heinz Hofmann, An alternative way to get the terms of A106607. Examples of a(1..18)
Index entries for linear recurrences with constant coefficients, signature (3,-3,1,1,-3,3,-1).

Row n=3 of A333737.

Cf. A100779.

(1+t^3)^2/((1-t)*(1-t^2)^2*(1-t^4));
seq(coeff(series(%,t,n+1), t,n), n=0..60);

LinearRecurrence[{3,-3,1,1,-3,3,-1}, {1,1,3,5,9,13,20}, 61] (* G. C. Greubel, Sep 08 2021 *)

a(n) = i=I; (4*n^3+18*n^2+56*n+3*(9*(-1)^n+(2-2*i)*(-i)^n+(2+2*i)*i^n+19))/96 \\ Colin Barker, Feb 08 2016

def A106607_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x^3)^2/((1-x)*(1-x^2)^2*(1-x^4)) ).list()
A106607_list(60) # G. C. Greubel, Sep 08 2021

G.f.: (1-x+x^2)^2/( (1+x)*(1+x^2)*(1-x)^4 ). - R. J. Mathar, Dec 18 2014
a(n) = (4*n^3 +18*n^2 +56*n +3*(9*(-1)^n +2*(1-i)*(-i)^n +2*(1+i)*i^n +19))/96 where i is the imaginary unit. - Colin Barker, Feb 08 2016
E.g.f.: (1/48)*(6*(cos(x) - sin(x)) + p(x)*sinh(x) + (27 + p(x))*cosh(x)), where p(x) = 15 + 39*x + 15*x^2 + 2*x^3. - G. C. Greubel, Sep 08 2021

A333886 Number of non-isomorphic 4 X 4 nonnegative integer symmetric matrices with all row and column sums equal to n up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 5, 12, 33, 74, 163, 319, 596, 1044, 1754, 2820, 4394, 6629, 9756, 14018, 19743, 27286, 37111, 49707, 65699, 85756, 110691, 141382, 178882, 224309, 278990, 344342, 422000, 513718, 621506, 747493, 894105, 1063920, 1259823, 1484886, 1742533, 2036377, 2370431, 2748936, 3176544

Offset: 0

Andrew Howroyd, Apr 08 2020

nonn

			The a(2) = 5 matrices are:
  [0 0 0 2]  [0 0 0 2]  [0 0 1 1]  [0 0 1 1]  [0 0 1 1]
  [0 0 2 0]  [0 1 1 0]  [0 0 1 1]  [0 1 0 1]  [0 2 0 0]
  [0 2 0 0]  [0 1 1 0]  [1 1 0 0]  [1 0 1 0]  [1 0 0 1]
  [2 0 0 0]  [2 0 0 0]  [1 1 0 0]  [1 1 0 0]  [1 0 1 0]
.
The a(3) = 12 matrices are:
  [0 0 0 3] [0 0 1 2] [0 0 1 2] [0 0 1 2] [0 0 1 2] [0 1 1 1]
  [0 0 3 0] [0 0 2 1] [0 1 1 1] [0 1 2 0] [0 2 1 0] [1 0 1 1]
  [0 3 0 0] [1 2 0 0] [1 1 1 0] [1 2 0 0] [1 1 0 1] [1 1 0 1]
  [3 0 0 0] [2 1 0 0] [2 1 0 0] [2 0 0 1] [2 0 1 0] [1 1 1 0]
.
  [0 0 0 3] [0 0 1 2] [0 0 1 2] [0 0 1 2] [0 1 1 1] [1 0 1 1]
  [0 1 2 0] [0 2 1 0] [0 3 0 0] [0 3 0 0] [1 1 0 1] [0 3 0 0]
  [0 2 1 0] [1 1 1 0] [1 0 1 1] [1 0 2 0] [1 0 2 0] [1 0 1 1]
  [3 0 0 0] [2 0 0 1] [2 0 1 0] [2 0 0 1] [1 1 0 1] [1 0 1 1]

Row n=4 of A333737.

A333738 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to n up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 2, 5, 33, 556, 31781, 5882230, 3589936407, 7347418294141, 51304793433150418, 1240428029662246026001, 105148289475978338858008298, 31582581551955332317665959184087

Offset: 0

Andrew Howroyd, Apr 08 2020

			The a(3) = 5 matrices are:
  [0, 0, 3]  [0, 1, 2]  [0, 1, 2]  [1, 0, 2]  [1, 1, 1]
  [0, 3, 0]  [1, 1, 1]  [1, 2, 0]  [0, 3, 0]  [1, 1, 1]
  [3, 0, 0]  [2, 1, 0]  [2, 0, 1]  [2, 0, 1]  [1, 1, 1]

Main diagonal of A333737.

A333887 Number of non-isomorphic 5 X 5 nonnegative integer symmetric matrices with all row and column sums equal to n up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 7, 29, 142, 556, 1919, 5793, 15758, 39131, 90185, 194905, 398773, 777708, 1454721, 2622421, 4575020, 7750397, 12787648, 20600441, 32473894, 50185556, 76161130, 113665307, 167041499, 242001146, 345981348, 488570133, 682023069, 941871068, 1287649789

Offset: 0

Andrew Howroyd, Apr 08 2020

nonn

Row n=5 of A333737.

A333888 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to 3 up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 2, 5, 12, 29, 79, 225, 677, 2141, 7121, 24693, 89117, 333312, 1288949, 5140039, 21094565, 88931387, 384544989, 1703083332, 7715920544, 35720666818, 168809971994, 813633173238, 3996247863791, 19986651995983, 101715962631912, 526405121697307, 2768690275913665, 14791474244527076, 80224577967948446

Offset: 0

Andrew Howroyd, Apr 08 2020

nonn

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

Column k=3 of A333737.

A333889 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to 4 up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 3, 9, 33, 142, 742, 4454, 30516, 233574, 1972430, 18190806, 181774873, 1955268162, 22516241557, 276294103003, 3598106433662, 49551992313623, 719398127720459, 10979514511427858, 175716291405379723, 2942195925987952412, 51436169813668249174, 937106275320950472387, 17761791825490936694507

Offset: 0

Andrew Howroyd, Apr 08 2020

nonn

			The a(3) = 9 matrices are:
   [0 0 4]  [0 1 3]  [0 1 3]  [0 2 2]  [0 2 2]
   [0 4 0]  [1 2 1]  [1 3 0]  [2 0 2]  [2 1 1]
   [4 0 0]  [3 1 0]  [3 0 1]  [2 2 0]  [2 1 1]
.
   [1 0 3]  [1 1 2]  [1 1 2]  [2 0 2]
   [0 4 0]  [1 2 1]  [1 3 0]  [0 4 0]
   [3 0 1]  [2 1 1]  [2 0 2]  [2 0 2]

Column k=4 of A333737.

A333890 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to 5 up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 3, 13, 74, 556, 5369, 64000, 917235, 15450781, 300882997, 6682784998, 167423745058, 4687321410460, 145487540598936, 4972006889998672, 185965612590706251, 7572297055379416985, 334097417273761302271, 15905277840810391655517, 813931037149014145154401

Offset: 0

Andrew Howroyd, Apr 08 2020

nonn

Column k=5 of A333737.

The a(2) = 3 matrices are:
  [0 5]  [1 4]  [2 3]
  [5 0]  [4 1]  [3 2]

cp's OEIS Frontend

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

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A106607 Expansion of (1+t^3)^2/((1-t)*(1-t^2)^2*(1-t^4)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A333886 Number of non-isomorphic 4 X 4 nonnegative integer symmetric matrices with all row and column sums equal to n up to permutations of rows and columns.

Views

Author

Keywords

Examples

Crossrefs

A333738 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to n up to permutations of rows and columns.

Views

Author

Keywords

Examples

Crossrefs

A333887 Number of non-isomorphic 5 X 5 nonnegative integer symmetric matrices with all row and column sums equal to n up to permutations of rows and columns.

Views

Author

Keywords

Crossrefs

A333888 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to 3 up to permutations of rows and columns.

Views

Author

Keywords

Examples

Crossrefs

A333889 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to 4 up to permutations of rows and columns.

Views

Author

Keywords

Examples

Crossrefs

A333890 Number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to 5 up to permutations of rows and columns.

Views

Author

Keywords

Crossrefs

Formula

A106607 Expansion of (1+t^3)^2/((1-t)(1-t^2)^2(1-t^4)).