A110058 -id:A110058 - cp's OEIS frontend

A257493 Number A(n,k) of n X n nonnegative integer matrices with all row and column sums equal to k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 6, 1, 1, 1, 4, 21, 24, 1, 1, 1, 5, 55, 282, 120, 1, 1, 1, 6, 120, 2008, 6210, 720, 1, 1, 1, 7, 231, 10147, 153040, 202410, 5040, 1, 1, 1, 8, 406, 40176, 2224955, 20933840, 9135630, 40320, 1, 1, 1, 9, 666, 132724, 22069251, 1047649905, 4662857360, 545007960, 362880, 1

Offset: 0

Alois P. Heinz, Apr 26 2015

Also the number of ordered factorizations of m^k into n factors, where m is a product of exactly n distinct primes and each factor is a product of k primes (counted with multiplicity). A(2,2) = 3: (2*3)^2 = 36 = 4*9 = 6*6 = 9*4.

			Square array A(n,k) begins:
  1,   1,      1,        1,          1,           1,            1, ...
  1,   1,      1,        1,          1,           1,            1, ...
  1,   2,      3,        4,          5,           6,            7, ...
  1,   6,     21,       55,        120,         231,          406, ...
  1,  24,    282,     2008,      10147,       40176,       132724, ...
  1, 120,   6210,   153040,    2224955,    22069251,    164176640, ...
  1, 720, 202410, 20933840, 1047649905, 30767936616, 602351808741, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce, A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
D. M. Jackson & G. H. J. van Rees, The enumeration of generalized double stochastic nonnegative integer square matrices, SIAM J. Comput., 4.4 (1975), 474-477. (Annotated scanned copy)
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.
Dennis Pixton, Ehrhart polynomials for n = 1, ..., 9
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]

Columns k=0-9 give: A000012, A000142, A000681, A001500, A172806, A172862, A172894, A172919, A172944, A172958.
Rows n=0+1, 2-9 give: A000012, A000027(k+1), A002817(k+1), A001496, A003438, A003439, A008552, A160318, A160319.
Main diagonal gives A110058.
Cf. A257463 (unordered factorizations), A333733 (non-isomorphic matrices), A008300 (binary matrices).

with(numtheory):
b:= proc(n, k) option remember; `if`(n=1, 1, add(
      `if`(bigomega(d)=k, b(n/d, k), 0), d=divisors(n)))
    end:
A:= (n, k)-> b(mul(ithprime(i), i=1..n)^k, k):
seq(seq(A(n, d-n), n=0..d), d=0..8);

b[n_, k_] := b[n, k] = If[n==1, 1, Sum[If[PrimeOmega[d]==k, b[n/d, k], 0], {d, Divisors[n]}]]; A[n_, k_] := b[Product[Prime[i], {i, 1, n}]^k, k]; Table[A[n, d-n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 20 2016, after Alois P. Heinz *)

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(h, p, q, v, e) = if(!p, if(!e, acc(q, v)), my(i=poldegree(p), t=pollead(p)); self()(k, p-t*x^i, q+t*x^i, v, e); for(m=1, h-i, for(j=1, min(t, e\m), self()(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(k, src[i, 1], 0, src[i, 2], k))); vecsum(Mat(M)[, 2])
} \\ Andrew Howroyd, Apr 04 2020

bigomega = sloane.A001222
@cached_function
def b(n, k):
    if n == 1:
        return 1
    return sum(b(n//d, k) if bigomega(d) == k else 0 for d in n.divisors())
def A(n, k):
    return b(prod(nth_prime(i) for i in (1..n))^k, k)
[A(n, d-n) for d in (0..10) for n in (0..d)] # Freddy Barrera, Dec 27 2018, translated from Maple

from sage.combinat.integer_matrices import IntegerMatrices
[IntegerMatrices([d-n]*n, [d-n]*n).cardinality() for d in (0..10) for n in (0..d)] # Freddy Barrera, Dec 27 2018

A333901 Array read by antidiagonals: T(n,k) is the number of n X k nonnegative integer matrices with all column sums n and row sums k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 7, 7, 1, 1, 1, 1, 19, 55, 19, 1, 1, 1, 1, 51, 415, 415, 51, 1, 1, 1, 1, 141, 3391, 10147, 3391, 141, 1, 1, 1, 1, 393, 28681, 261331, 261331, 28681, 393, 1, 1, 1, 1, 1107, 248137, 7100821, 22069251, 7100821, 248137, 1107, 1, 1

Offset: 0

Andrew Howroyd, Apr 18 2020

T(n,k) is the number of ordered factorizations of m^n into n factors, where m is a product of exactly k distinct primes and each factor is a product of k primes (counted with multiplicity).

			Array begins:
=======================================================
n\k | 0 1   2     3       4          5            6
----+--------------------------------------------------
  0 | 1 1   1     1       1          1            1 ...
  1 | 1 1   1     1       1          1            1 ...
  2 | 1 1   3     7      19         51          141 ...
  3 | 1 1   7    55     415       3391        28681 ...
  4 | 1 1  19   415   10147     261331      7100821 ...
  5 | 1 1  51  3391  261331   22069251   1985311701 ...
  6 | 1 1 141 28681 7100821 1985311701 602351808741 ...
  ...
The T(3,2) = 7 matrices are:
  [1 1]  [1 1]  [1 1]  [2 0]  [2 0]  [0 2]  [0 2]
  [1 1]  [2 0]  [0 2]  [1 1]  [0 2]  [1 1]  [2 0]
  [1 1]  [0 2]  [2 0]  [0 2]  [1 1]  [2 0]  [1 1]

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

Columns k=0..9 are A000012, A000012, A002426, A172743, A172816, A172868, A172904, A172931, A172947, A172961.
Main diagonal is A110058.
Cf. A257462, A257493.

T(n, k)={
  local(M=Map(Mat([k, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(h, p, q, v, e) = if(!p, if(!e, acc(q, v)), my(i=poldegree(p), t=pollead(p)); self()(n, p-t*x^i, q+t*x^i, v, e); for(m=1, h-i, for(j=1, min(t, e\m), self()(if(j==t, n, 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, src[i, 1], 0, src[i, 2], k))); vecsum(Mat(M)[, 2])
}
for(n=0, 7, for(k=0, 7, print1(T(n,k), ", ")); print)

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

A333734 Number of non-isomorphic n X n nonnegative integer 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, 43, 1856, 1217727, 8597641912, 646296747486387, 535435113671568180963, 5081029530811947425598907884, 570680215340337514993573217774604779, 779646755088025699677478853259568262608053838

Offset: 0

Andrew Howroyd, Apr 04 2020

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

Main diagonal of A333733 and A377060.

Cf. A110058.

a(11)-a(12) from Andrew Howroyd, Oct 14 2024

A361749 a(n) is the number of n X n matrices with nonnegative integer entries, row sums 1,2,...,n and column sums 1,2,...,n.

Original entry on oeis.org

1, 1, 2, 12, 261, 22645, 8264346, 13150070522, 93589674933872, 3036609755945925595, 455845471095088280120142, 320342093420041869298750385976, 1063978124653925432733949863518874116, 16835366182312565093823092118182447742597067

Offset: 0

Robert Israel, Mar 23 2023

nonn

			a(3) = 12 because there are 12 possible 3 X 3 matrices with nonnegative integer entries, row sums 1,2,3 and column sums 1,2,3:
  [ 0 0 1 ]   [ 0 0 1 ]   [ 0 0 1 ]   [ 0 0 1 ]
  [ 0 0 2 ]   [ 0 1 1 ]   [ 0 2 0 ]   [ 1 0 1 ]
  [ 1 2 0 ],  [ 1 1 1 ],  [ 1 0 2 ],  [ 0 2 1 ],
  .
  [ 0 0 1 ]   [ 0 1 0 ]   [ 0 1 0 ]   [ 0 1 0 ]
  [ 1 1 0 ]   [ 0 0 2 ]   [ 0 1 1 ]   [ 1 0 1 ]
  [ 0 1 2 ],  [ 1 1 1 ],  [ 1 0 2 ],  [ 0 1 2 ],
  .
  [ 0 1 0 ]   [ 1 0 0 ]   [ 1 0 0 ]   [ 1 0 0 ]
  [ 1 1 0 ]   [ 0 0 2 ]   [ 0 1 1 ]   [ 0 2 0 ]
  [ 0 0 3 ],  [ 0 2 1 ],  [ 0 1 2 ],  [ 0 0 3 ].

Andrew Howroyd, PARI Program, Mar 2023.

Cf. A000681, A110058.

G:= proc(L,R,k) option remember;
# number of solutions with first k entries of first row 0
local m,n,i;
m:= nops(L); n:= nops(R);
if m <= 1 then return 1 fi;
if L[1] > convert(R[k+1..n],`+`) then return 0 fi;
if k = n-1 then return procname(L[2..-1],subsop(n = R[n]-L[1], R),0) fi;
add(procname(subsop(1=L[1]-i, L), subsop(k+1=R[k+1]-i, R), k+1), i=0..min(L[1],R[k+1]))
end proc:
seq(G([$1..n],[$1..n],0), n=0..8);

a(10)-a(13) from Andrew Howroyd, Mar 29 2023

a(0)=1 prepended by Alois P. Heinz, Jun 26 2023

cp's OEIS Frontend

A257493 Number A(n,k) of n X n nonnegative integer matrices with all row and column sums equal to k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Sage

A333901 Array read by antidiagonals: T(n,k) is the number of n X k nonnegative integer matrices with all column sums n and row sums k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Examples

Crossrefs

Extensions

A361749 a(n) is the number of n X n matrices with nonnegative integer entries, row sums 1,2,...,n and column sums 1,2,...,n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Extensions