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,2

Comments

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)

Links

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

Example

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

Prog

(PARI)
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

Crossrefs

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.

Sequence in context: A067410 A213947 A348482 * A248929 A109977 A201199

Adjacent sequences: A188400 A188401 A188402 * A188404 A188405 A188406

Keyword

nonn,tabl

Author

R. H. Hardin, Mar 30 2011

Status

approved