A333901 -id:A333901 - cp's OEIS frontend

A334549 Array read by antidiagonals: T(n,k) is the number of {-1,0,1} n X k matrices with all rows and columns summing to zero.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 7, 7, 1, 1, 1, 1, 19, 31, 19, 1, 1, 1, 1, 51, 175, 175, 51, 1, 1, 1, 1, 141, 991, 2371, 991, 141, 1, 1, 1, 1, 393, 5881, 32611, 32611, 5881, 393, 1, 1, 1, 1, 1107, 35617, 481381, 1084851, 481381, 35617, 1107, 1, 1

Offset: 0

Andrew Howroyd, May 09 2020

Equivalently, the number of n X k 0..2 arrays with row sums k and column sums n.

			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 1   3     7      19         51          141          393 ...
  3 | 1 1   7    31     175        991         5881        35617 ...
  4 | 1 1  19   175    2371      32611       481381      7343449 ...
  5 | 1 1  51   991   32611    1084851     39612501   1509893001 ...
  6 | 1 1 141  5881  481381   39612501   3680774301 360255871641 ...
  7 | 1 1 393 35617 7343449 1509893001 360255871641 ...
     ...
The T(3,2) = 7 matrices are:
  [0 0]  [ 0  0]  [ 0  0]  [ 1 -1]  [-1  1]  [ 1 -1]  [-1  1]
  [0 0]  [ 1 -1]  [-1  1]  [ 0  0]  [ 0  0]  [-1  1]  [ 1 -1]
  [0 0]  [-1  1]  [ 1 -1]  [-1  1]  [ 1 -1]  [ 0  0]  [ 0  0]

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

Columns k=0..14 are A000012, A000012, A002426, A172634, A172642, A172639, A172633, A172636, A172638, A172641, A172637, A172644, A172640, A172643, A172635.
Main diagonal is A172645.
Cf. A008300, A333901, A376935, A377063 (up to row permutations).

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

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 4, 2, 1, 1, 1, 1, 10, 10, 3, 1, 1, 1, 1, 26, 70, 25, 3, 1, 1, 1, 1, 71, 566, 465, 49, 4, 1, 1, 1, 1, 197, 4781, 11131, 2505, 103, 4, 1, 1, 1, 1, 554, 41357, 297381, 190131, 12652, 184, 5, 1, 1, 1, 1, 1570, 364470, 8349223, 16669641, 2928876, 57232, 331, 5, 1, 1

Offset: 0

Alois P. Heinz, Apr 24 2015

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

			A(4,2) = 3: (2*3)^4 = 1296 = 6*6*6*6 = 9*6*6*4 = 9*9*4*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) = 10: (2*3*5*7)^2 = 44100 = 210*210 = 225*196 = 294*150 = 315*140 = 350*126 = 441*100 = 490*90 = 525*84 = 735*60 = 1225*36.
Square array A(n,k) begins:
  1, 1, 1,  1,    1,      1, ...
  1, 1, 1,  1,    1,      1, ...
  1, 1, 2,  4,   10,     26, ...
  1, 1, 2, 10,   70,    566, ...
  1, 1, 3, 25,  465,  11131, ...
  1, 1, 3, 49, 2505, 190131, ...

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

Columns k=0+1, 2-5 give: A000012, A008619, A254233, A257114, A257518.
Rows n=0+1, 2-3 give: A000012, A257520, A333902.
Main diagonal gives A334286.
Cf. A257463, A333901 (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) minus {1}))
    end:
A:= (n, k)-> b(mul(ithprime(i), i=1..k)^n$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, Sum[If[d > i || PrimeOmega[d] != k, 0, b[n/d, d, k]], {d, Divisors[n] // Rest}]]; A[n_, k_] := Module[ {p = Product[Prime[i], {i, 1, k}]^n}, b[p, p, k]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 8}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 6, 6, 1, 1, 20, 90, 20, 1, 1, 70, 1860, 1860, 70, 1, 1, 252, 44730, 297200, 44730, 252, 1, 1, 924, 1172556, 60871300, 60871300, 1172556, 924, 1, 1, 3432, 32496156, 14367744720, 116963796250, 14367744720, 32496156, 3432, 1, 1, 12870, 936369720, 3718394156400, 273957842462220, 273957842462220, 3718394156400, 936369720, 12870, 1

Offset: 0

Andrew Howroyd, Oct 11 2024

T(n,k) is the number of 2*n X 2*k {-1,1} matrices with all rows and columns summing to zero.

			Array begins:
========================================================================
n\k | 0   1       2           3               4                   5 ...
----+------------------------------------------------------------------
  0 | 1   1       1           1               1                   1 ...
  1 | 1   2       6          20              70                 252 ...
  2 | 1   6      90        1860           44730             1172556 ...
  3 | 1  20    1860      297200        60871300         14367744720 ...
  4 | 1  70   44730    60871300    116963796250     273957842462220 ...
  5 | 1 252 1172556 14367744720 273957842462220 6736218287430460752 ...
  ...

Nikolai Beluhov, Powers of 2 in Balanced Grid Colourings, arXiv:2504.21451 [math.CO], 2025.
Robert Dougherty-Bliss, Christoph Koutschan, Natalya Ter-Saakov, and Doron Zeilberger, The (Symbolic and Numeric) Computational Challenges of Counting 0-1 Balanced Matrices, arXiv:2410.07435 [math.CO], 2024.

Main diagonal is A058527.
Columns 0..9 are A000012, A000984, A002896, A172556, A172555, A172557, A172558, A172559, A172560, A172554.
Cf. A008300, A195644, A333901, A334549, A377007 (up to permutations of rows and columns).

T(n, k)={
  local(M=Map(Mat([2*k, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(i, p, v, e) = if(i<0, if(!e, acc(p, v)), my(t=polcoef(p,i)); for(j=0, min(t, e), self()(i-1, p+j*(x-1)*x^i, binomial(t, j)*v, e-j))));
  for(r=1, 2*n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(n-1, src[i, 1], src[i, 2], k))); vecsum(Mat(M)[,2]);
}

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

A377060 Array read by antidiagonals: T(n,k) is the number of inequivalent n X k nonnegative integer matrices with all column sums n and row sums k up to permutation of rows and columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 5, 3, 1, 1, 1, 1, 3, 9, 9, 3, 1, 1, 1, 1, 4, 14, 43, 14, 4, 1, 1, 1, 1, 4, 28, 147, 147, 28, 4, 1, 1, 1, 1, 5, 44, 661, 1856, 661, 44, 5, 1, 1, 1, 1, 5, 73, 2649, 25888, 25888, 2649, 73, 5, 1, 1

Offset: 0

Andrew Howroyd, Oct 14 2024

Terms may be computed without generating each matrix by enumerating the number of matrices by column sum sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A333901. Burnside's lemma can be used to extend this method to the unlabeled case. This seems to require looping over partitions for both rows and columns.

			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 1 2  2    3      3        4          4 ...
  3 | 1 1 2  5    9     14       28         44 ...
  4 | 1 1 3  9   43    147      661       2649 ...
  5 | 1 1 3 14  147   1856    25888     346691 ...
  6 | 1 1 4 28  661  25888  1217727   55138002 ...
  7 | 1 1 4 44 2649 346691 55138002 8597641912 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..324 (first 25 antidiagonals)

Main diagonal is A333734.
Columns k=0..4 are A000012, A000012, A008619, A377061, A377062.
Cf. A333733, A333901, A377007.

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

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

A172743 Number of n X 3 0..3 arrays with row sums 3 and column sums n.

Original entry on oeis.org

1, 7, 55, 415, 3391, 28681, 248137, 2186815, 19546975, 176703337, 1612210777, 14823083089, 137176167025, 1276548044695, 11936862061495, 112092031526335, 1056512066133055, 9991003788000025, 94760438267696425, 901154863603211665

Offset: 1

R. H. Hardin, Feb 06 2010

nonn

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

Column k=3 of A333901.

A172816 Number of n X 4 0..4 arrays with row sums 4 and column sums n.

Original entry on oeis.org

1, 19, 415, 10147, 261331, 7100821, 200148649, 5796870115, 171475190227, 5158851352489, 157366288875709, 4855940642591941, 151309409779981285, 4754260599949620163, 150466404665460290335, 4792275283921293214435

Offset: 1

R. H. Hardin, Feb 06 2010

nonn

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

Column k=4 of A333901.

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

Original entry on oeis.org

1, 51, 3391, 261331, 22069251, 1985311701, 187403959401, 18343212299091, 1846780916614531, 190172119451839801, 19947450199250403501, 2124709987334672961301, 229273855680211513815541

Offset: 1

R. H. Hardin, Feb 06 2010

nonn

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

Column k=5 of A333901.

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

Original entry on oeis.org

1, 141, 28681, 7100821, 1985311701, 602351808741, 193953937375521, 65338547748658101, 22800663583664571781, 8184214105554904614241, 3006271871518328730143421, 1125711921752126203903372141

Offset: 1

R. H. Hardin, Feb 06 2010

nonn

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

Column k=6 of A333901.

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

Original entry on oeis.org

1, 393, 248137, 200148649, 187403959401, 193953937375521, 215717608046511873, 253310893747894263177, 310323674631037864285609, 393277602707575435993011793, 512421117125922437799936404913

Offset: 1

R. H. Hardin, Feb 06 2010

nonn

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

Column k=7 of A333901.

cp's OEIS Frontend

A334549 Array read by antidiagonals: T(n,k) is the number of {-1,0,1} n X k matrices with all rows and columns summing to zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A376935 Array read by antidiagonals: T(n,k) is the number of 2*n X 2*k binary matrices with all row sums k and column sums n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A377060 Array read by antidiagonals: T(n,k) is the number of inequivalent n X k nonnegative integer matrices with all column sums n and row sums k up to permutation of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A172743 Number of n X 3 0..3 arrays with row sums 3 and column sums n.

Views

Author

Keywords

Links

Crossrefs

A172816 Number of n X 4 0..4 arrays with row sums 4 and column sums n.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

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