A257493 - OEIS

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.

%I #57 Jun 23 2023 04:09:03

%S 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,

%T 120,2008,6210,720,1,1,1,7,231,10147,153040,202410,5040,1,1,1,8,406,

%U 40176,2224955,20933840,9135630,40320,1,1,1,9,666,132724,22069251,1047649905,4662857360,545007960,362880,1

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

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

%H Alois P. Heinz, <a href="/A257493/b257493.txt">Antidiagonals n = 0..20, flattened</a>

%H E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce, <a href="https://arxiv.org/abs/1508.03673">A generalization of Eulerian numbers via rook placements</a>, arXiv:1508.03673 [math.CO], 2015.

%H D. M. Jackson & G. H. J. van Rees, <a href="/A002817/a002817.pdf">The enumeration of generalized double stochastic nonnegative integer square matrices</a>, SIAM J. Comput., 4.4 (1975), 474-477. (Annotated scanned copy)

%H Richard J. Mathar, <a href="https://arxiv.org/abs/1903.12477">2-regular Digraphs of the Lovelock Lagrangian</a>, arXiv:1903.12477 [math.GM], 2019.

%H Dennis Pixton, <a href="http://people.math.binghamton.edu/dennis/Birkhoff/polynomials.html">Ehrhart polynomials for n = 1, ..., 9</a>

%H M. L. Stein and P. R. Stein, <a href="/A001496/a001496.pdf">Enumeration of Stochastic Matrices with Integer Elements</a>, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 2, 3, 4, 5, 6, 7, ...

%e 1, 6, 21, 55, 120, 231, 406, ...

%e 1, 24, 282, 2008, 10147, 40176, 132724, ...

%e 1, 120, 6210, 153040, 2224955, 22069251, 164176640, ...

%e 1, 720, 202410, 20933840, 1047649905, 30767936616, 602351808741, ...

%p with(numtheory):

%p b:= proc(n, k) option remember; `if`(n=1, 1, add(

%p `if`(bigomega(d)=k, b(n/d, k), 0), d=divisors(n)))

%p end:

%p A:= (n, k)-> b(mul(ithprime(i), i=1..n)^k, k):

%p seq(seq(A(n, d-n), n=0..d), d=0..8);

%t 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_ *)

%o (Sage)

%o bigomega = sloane.A001222

%o @cached_function

%o def b(n, k):

%o if n == 1:

%o return 1

%o return sum(b(n//d, k) if bigomega(d) == k else 0 for d in n.divisors())

%o def A(n, k):

%o return b(prod(nth_prime(i) for i in (1..n))^k, k)

%o [A(n, d-n) for d in (0..10) for n in (0..d)] # _Freddy Barrera_, Dec 27 2018, translated from Maple

%o (Sage)

%o from sage.combinat.integer_matrices import IntegerMatrices

%o [IntegerMatrices([d-n]*n, [d-n]*n).cardinality() for d in (0..10) for n in (0..d)] # _Freddy Barrera_, Dec 27 2018

%o (PARI)

%o T(n, k)={

%o local(M=Map(Mat([n, 1])));

%o my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));

%o 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)))));

%o 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])

%o } \\ _Andrew Howroyd_, Apr 04 2020

%Y Columns k=0-9 give: A000012, A000142, A000681, A001500, A172806, A172862, A172894, A172919, A172944, A172958.

%Y Rows n=0+1, 2-9 give: A000012, A000027(k+1), A002817(k+1), A001496, A003438, A003439, A008552, A160318, A160319.

%Y Main diagonal gives A110058.

%Y Cf. A257463 (unordered factorizations), A333733 (non-isomorphic matrices), A008300 (binary matrices).

%K nonn,tabl

%O 0,9

%A _Alois P. Heinz_, Apr 26 2015