A257493 -id:A257493 - cp's OEIS frontend

A257463 Number A(n,k) of 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); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 3, 10, 17, 1, 1, 1, 1, 3, 23, 93, 73, 1, 1, 1, 1, 4, 40, 465, 1417, 388, 1, 1, 1, 1, 4, 73, 1746, 19834, 32152, 2461, 1, 1, 1, 1, 5, 114, 5741, 190131, 1532489, 1016489, 18155, 1, 1

Offset: 0

Alois P. Heinz, Apr 24 2015

Also number of ways to partition the multiset consisting of k copies each of 1, 2, ..., n into n multisets of size k.

			A(4,2) = 17: (2*3*5*7)^2 = 44100 = 15*15*14*14 = 21*15*14*10 = 21*21*10*10 = 25*14*14*9 = 25*21*14*6 = 25*21*21*4 = 35*14*10*9 = 35*15*14*6 = 35*21*10*6 = 35*21*15*4 = 35*35*6*6 = 35*35*9*4 = 49*10*10*9 = 49*15*10*6 = 49*15*15*4 = 49*25*6*6 = 49*25*9*4.
A(3,3) = 10: (2*3*5)^3 = 2700 = 30*30*30 = 45*30*20 = 50*27*20 = 50*30*18 = 50*45*12 = 75*20*18 = 75*30*12 = 75*45*8 = 125*18*12 = 125*27*8.
A(2,4) = 3: (2*3)^4 = 1296 = 36*36 = 54*24 = 81*16.
Square array A(n,k) begins:
  1, 1,   1,     1,       1,        1,         1, ...
  1, 1,   1,     1,       1,        1,         1, ...
  1, 1,   2,     2,       3,        3,         4, ...
  1, 1,   5,    10,      23,       40,        73, ...
  1, 1,  17,    93,     465,     1746,      5741, ...
  1, 1,  73,  1417,   19834,   190131,   1398547, ...
  1, 1, 388, 32152, 1532489, 43816115, 848597563, ...

Andrew Howroyd, Antidiagonals n = 0..27, flattened (antidiagonals 0..12 from Alois P. Heinz)
P. A. MacMahon, Combinations derived from m identical sets of n different letters and their connexion with general magic squares, Proc. London Math. Soc., 17 (1917), 25-41. The array is on page 40.
Math StackExchange, Number of ways to partition 40 balls with 4 colors into 4 baskets
Marko Riedel, Maple program to compute array from cycle indices

Columns k=0+1, 2-4 give: A000012, A002135, A254243, A268668.
Rows n=0+1, 2-5 give: A000012, A008619, A257464, A253259, A253263.
Main diagonal gives A334286.
Cf. A257462, A257493 (ordered factorizations).

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

b[n_, i_, k_] := b[n, i, k] = If[n==1, 1, DivisorSum[n, If[#>i || PrimeOmega[#] != k, 0, b[n/#, #, k]]&]];
A[n_, k_] := b[p = Product[Prime[i], {i, 1, n}]^k, p, k];
Table[A[n, d-n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, Mar 20 2017, translated from Maple *)

A195644 T(n,k) is the number of lower triangles of an n X n 0..k array with all row sums equal to the length of the row and all column sums equal to the length of the column.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 15, 1, 1, 1, 3, 19, 199, 1, 1, 1, 3, 19, 379, 6247, 1, 1, 1, 3, 19, 391, 22506, 505623, 1, 1, 1, 3, 19, 391, 25428, 4063437, 105997283, 1, 1, 1, 3, 19, 391, 25532, 5422820, 2303397986, 58923059879, 1, 1, 1, 3, 19, 391, 25532, 5536654

Offset: 1

R. H. Hardin, Sep 21 2011

			Table starts:
  1         1          1          1          1          1 ...
  1         1          1          1          1          1 ...
  1         3          3          3          3          3 ...
  1        15         19         19         19         19 ...
  1       199        379        391        391        391 ...
  1      6247      22506      25428      25532      25532 ...
  1    505623    4063437    5422820    5536654    5539434 ...
  1 105997283 2303397986 3868544673 4102276124 4116036800 ...
  ...
Some solutions for n=5, k=4:
..1..........1..........1..........1..........1..........1..........1
..1.1........1.1........2.0........2.0........2.0........2.0........2.0
..3.0.0......3.0.0......0.1.2......2.1.0......0.1.2......2.0.1......1.2.0
..0.1.1.2....0.1.1.2....1.1.0.2....0.1.1.2....1.1.0.2....0.0.2.2....1.2.1.0
..0.2.2.0.1..0.2.2.0.1..1.2.1.0.1..0.2.2.0.1..1.2.1.0.1..0.4.0.0.1..0.0.2.2.1

R. H. Hardin, Table of n, a(n) for n = 1..102

Columns 1..7 are A000012, A195515, A195639, A195640, A195641, A195642, A195643.
Main diagonal is A195638.
Cf. A195522, A257493.

\\ adapted from program for A257493.
T(n, k)={
  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(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, min(k, 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] + x^(r-1), 0, src[i, 2], r))); vecsum(Mat(M)[, 2])
} \\ Andrew Howroyd, May 16 2020

T(n,k) = T(n,k-1) for k >= n, n >= 2. - Andrew Howroyd, May 16 2020

A003438 Number of 5 X 5 matrices with nonnegative integer entries and row and column sums equal to n.

Original entry on oeis.org

1, 120, 6210, 153040, 2224955, 22069251, 164176640, 976395820, 4855258305, 20856798285, 79315936751, 272095118010, 854560160105, 2486299719645, 6765755480415, 17356306529251, 42250330784180, 98137852369965

Offset: 0

N. J. A. Sloane

Number of 5 X 5 stochastic matrices of integers.

D. M. Jackson and G. H. J. van Rees, The enumeration of generalized double stochastic nonnegative integer square matrices, SIAM J. Comput., 4 (1975), 474-477.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, p. 234.

T. D. Noe, Table of n, a(n) for n = 0..1000
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)
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]
Index entries for linear recurrences with constant coefficients, signature (17, -136, 680, -2380, 6188, -12376, 19448, -24310, 24310, -19448, 12376, -6188, 2380, -680, 136, -17, 1).

Cf. A002817, A001496, A019298.
Cf. A001496, A005466, A058391.
Row n=5 of A257493.

CoefficientList[Series[(1+103x+4306x^2+63110x^3+388615x^4+1115068x^5+ 1575669x^6+1115068x^7+388615x^8+63110x^9+4306x^10+103x^11+x^12)/ (1-x)^17,{x,0,30}],x] (* Harvey P. Dale, Aug 17 2013 *)

G.f.: (1 + 103*x + 4306*x^2 + 63110*x^3 + 388615*x^4 + 1115068*x^5 + 1575669*x^6 + 1115068*x^7 + 388615*x^8 + 63110*x^9 + 4306*x^10 + 103*x^11 + x^12)/(1-x)^17.

a(n) = Sum_{j=0..6} A005466(j) * binomial(4+j+n, 4+2*j). - Andrew Howroyd, Apr 09 2020

More terms from Vladeta Jovovic, Feb 06 2000

A037302 Normalized volume of Birkhoff polytope of n X n doubly-stochastic square matrices. If the volume is v(n), then a(n) = ((n-1)^2)! * v(n) / n^(n-1).

Original entry on oeis.org

1, 1, 3, 352, 4718075, 14666561365176, 17832560768358341943028, 12816077964079346687829905128694016, 7658969897501574748537755050756794492337074203099, 5091038988117504946842559205930853037841762820367901333706255223000

Offset: 1

Günter M. Ziegler (ziegler(AT)math.tu-berlin.de)

The Birkhoff polytope is an (n-1)^2-dimensional polytope in n^2-dimensional space; its vertices are the n! permutation matrices.

Is a(n) divisible by n^2 for all n>=4? - Dean Hickerson, Nov 27 2002

			a(2)=1: The polytope of 2 X 2 matrices is the line segment from (1,0;0,1) to (0,1;1,0), with length v(2)=2, so a(2) = 1! * 2 / 2^1 = 1.

Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope
Matthias Beck, Stanley's Major Contributions to Ehrhart Theory, arXiv preprint arXiv:1407.0255 [math.CO], 2014.
Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, arXiv:math/0202267 [math.CO], 2002-2005.
Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom. 30 (2003), no. 4, 623-637.
Petter Brändén, Jonathan Leake, and Igor Pak, Lower bounds for contingency tables via Lorentzian polynomials, arXiv:2008.05907 [math.CO], 2020.
C. S. Chan and D. P. Robbins, On the volume of the polytope of doubly stochastic matrices, arXiv:math/9806076 [math.CO], 1998.
C. S. Chan and D. P. Robbins, On the volume of the polytope of doubly stochastic matrices, Exper. Math. 8 (1999), 291-300.
Jesús A. De Loera, Fu Liu, and Ruriko Yoshida, A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin. 30 (2009), no. 1, 113-139.
R. P. Stanley, Decompositions of rational convex polytopes, Annals of Discrete Math. 6 (1980), 333-342.

Numerator and denominator of v(n) are in A078524 and A078525.
Row sums of A259473.
Cf. A257493.

a(n) = ((n-1)^2)!*A078524(n)/(n^(n-1)*A078525(n)). - Andrew Howroyd, Apr 11 2020

v(9) computed by Matthias Beck (matthias(AT)math.binghamton.edu) and Dennis Pixton (dennis(AT)math.binghamton.edu), Feb 25 2002
Edited by Dean Hickerson, Nov 27 2002
a(10) is based on a calculation of v(10) by Matthias Beck (matthias(AT)math.binghamton.edu) and Dennis Pixton (dennis(AT)math.binghamton.edu) from Mar 13 2002 to May 18 2003

A110058 Number of nonnegative integer matrices of order n for which all row and column sums equal n.

Original entry on oeis.org

1, 1, 3, 55, 10147, 22069251, 602351808741, 215717608046511873, 1046591482728407939338275, 70417932475495769964322670258947, 66880713903767740581650957184096513655153, 909176713758393122455793478657031533216492953328933, 178876969166665269546249744608783223036842010760723370462856181, 514016665650183402309555825250370336139392333285719205357202846243695510965

Offset: 0

Brendan McKay, Sep 04 2005

nonn

Computed by a method that involves summing a multivariate generating function over roots of unity.

			a(2) = 3 due to the matrices [1,1 | 1,1], [0,2 | 2,0] and [2,0 | 0,2].

E. R. Canfield, B. D. McKay, Asymptotic enumeration of integer matrices with large equal row and column sums, Combinatorica 30 (6) (2010) 655-680

Cf. A058407, A058410, A058391.

Main diagonal of A257493 and A333901.

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

log a(n) = 2(log 2)*n^2 - n*(log n) - n*(log 4*Pi) + (log n) + O(1). - Igor Pak, May 15 2019

a(0)=1 prepended by Alois P. Heinz, Apr 26 2015

A172862 Number of n X n 0..5 arrays with row sums 5 and column sums 5.

Original entry on oeis.org

1, 1, 6, 231, 40176, 22069251, 30767936616, 94161778046406, 569304690994400256, 6274236760589024662176, 118285830126660123474844752, 3623440212198461411381072575512, 172850452498398420310370097345242112

Offset: 0

R. H. Hardin, Feb 06 2010

nonn

R. H. Hardin, Table of n, a(n) for n = 0..35
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]

Column k=5 of A257493.

A172894 Number of n X n 0..6 arrays with row sums 6 and column sums 6.

Original entry on oeis.org

1, 1, 7, 406, 132724, 164176640, 602351808741, 5562418293759978, 114601242382721619224, 4801114002903931560293544, 379957050243738294456427057200, 53499490664883668314419655562118240

Offset: 0

R. H. Hardin, Feb 06 2010

nonn

R. H. Hardin, Table of n, a(n) for n = 0..25

Column k=6 of A257493.

A172919 Number of n X n 0..7 arrays with row sums 7 and column sums 7.

Original entry on oeis.org

1, 1, 8, 666, 381424, 976395820, 8575979362560, 215717608046511873, 13590707419428422843904, 1933216160887575268614599040, 571506744082785127089569166384000

Offset: 0

R. H. Hardin, Feb 06 2010

nonn

R. H. Hardin, Table of n, a(n) for n = 0..20

Column k=7 of A257493.

A172944 Number of n X n 0..8 arrays with row sums 8 and column sums 8.

Original entry on oeis.org

1, 1, 9, 1035, 981541, 4855258305, 94459713879600, 5945968652327831925, 1046591482728407939338275, 459761347800901006933211075259, 460129061613105910803354676484897475

Offset: 0

R. H. Hardin, Feb 06 2010

nonn

R. H. Hardin, Table of n, a(n) for n = 0..17

Column k=8 of A257493.

A172958 Number of n X n 0..9 arrays with row sums 9 and column sums 9.

Original entry on oeis.org

1, 1, 10, 1540, 2309384, 20856798285, 842286559093240, 123538613356253145400, 56272722406349235035916800, 70417932475495769964322670258947, 219302242655748448462474951981229489200

Offset: 0

R. H. Hardin, Feb 06 2010

nonn

R. H. Hardin, Table of n, a(n) for n = 0..15

Column k=9 of A257493.

cp's OEIS Frontend

A257463 Number A(n,k) of 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); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A195644 T(n,k) is the number of lower triangles of an n X n 0..k array with all row sums equal to the length of the row and all column sums equal to the length of the column.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A003438 Number of 5 X 5 matrices with nonnegative integer entries and row and column sums equal to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A037302 Normalized volume of Birkhoff polytope of n X n doubly-stochastic square matrices. If the volume is v(n), then a(n) = ((n-1)^2)! * v(n) / n^(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A110058 Number of nonnegative integer matrices of order n for which all row and column sums equal n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions

A172862 Number of n X n 0..5 arrays with row sums 5 and column sums 5.

Views

Author

Keywords

Links

Crossrefs

A172894 Number of n X n 0..6 arrays with row sums 6 and column sums 6.

Views

Author

Keywords

Links

Crossrefs

A172919 Number of n X n 0..7 arrays with row sums 7 and column sums 7.

Views

Author

Keywords

Links

Crossrefs

A172944 Number of n X n 0..8 arrays with row sums 8 and column sums 8.

Views

Author

Keywords

Links

Crossrefs