cp's OEIS Frontend

A327913 Array read by antidiagonals: T(n,m) is the number of distinct unordered row and column sums of n X m binary matrices.

%I A327913 #57 Apr 09 2021 06:36:20
%S A327913 1,1,1,1,2,1,1,3,3,1,1,4,7,4,1,1,5,13,13,5,1,1,6,22,34,22,6,1,1,7,34,
%T A327913 76,76,34,7,1,1,8,50,152,221,152,50,8,1,1,9,70,280,557,557,280,70,9,1,
%U A327913 1,10,95,482,1264,1736,1264,482,95,10,1,1,11,125,787,2630,4766,4766,2630,787,125,11,1
%N A327913 Array read by antidiagonals: T(n,m) is the number of distinct unordered row and column sums of n X m binary matrices.
%C A327913 Only matrices in which both row and columns sums are weakly increasing need to be considered. If order is also considered then the number of possibilities is given by A328887(n, m).
%H A327913 Andrew Howroyd, <a href="/A327913/b327913.txt">Table of n, a(n) for n = 0..1325</a>
%H A327913 Manfred Krause, <a href="https://doi.org/10.2307%2F2975191">A simple proof of the Gale-Ryser theorem</a>, American Mathematical Monthly, 1996.
%H A327913 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Ryser_theorem">Gale-Ryser theorem</a>
%e A327913 Array begins:
%e A327913 =============================================
%e A327913 n\m | 0 1  2   3    4     5     6      7
%e A327913 ----+----------------------------------------
%e A327913   0 | 1 1  1   1    1     1     1      1 ...
%e A327913   1 | 1 2  3   4    5     6     7      8 ...
%e A327913   2 | 1 3  7  13   22    34    50     70 ...
%e A327913   3 | 1 4 13  34   76   152   280    482 ...
%e A327913   4 | 1 5 22  76  221   557  1264   2630 ...
%e A327913   5 | 1 6 34 152  557  1736  4766  11812 ...
%e A327913   6 | 1 7 50 280 1264  4766 15584  45356 ...
%e A327913   7 | 1 8 70 482 2630 11812 45356 153228 ...
%e A327913   ...
%e A327913 T(2,2) = 7. The following 7 matrices each have different row/column sums.
%e A327913   [0 0]  [0 0]  [0 1]  [0 0]  [0 1]  [0 1]  [1 1]
%e A327913   [0 0]  [0 1]  [1 0]  [1 1]  [0 1]  [1 1]  [1 1]
%o A327913 (PARI)
%o A327913 T(n,m)={local(Cache=Map());
%o A327913   my(F(b, c, t, w)=my(hk=Vecsmall([b, c, t, w]), z);
%o A327913      if(!mapisdefined(Cache, hk, &z),
%o A327913        z = if(w&&c, sum(i=0, b, sum(j=ceil((t+i)/w), min(t+i, c), self()(i, j, t+i-j, w-1))), !t);
%o A327913      mapput(Cache, hk, z)); z);
%o A327913    F(n, n, 0, m)
%o A327913 }
%o A327913 (Python) # After PARI implementation.
%o A327913 from functools import cache
%o A327913 @cache
%o A327913 def F(b, c, t, w):
%o A327913     if w == 0:
%o A327913         return 1 if t == 0 else 0
%o A327913     return sum(
%o A327913         sum(
%o A327913             F(i, j, t + i - j, w - 1)
%o A327913             for j in range((t + i - 1) // w, min(t + i, c) + 1)
%o A327913         )
%o A327913         for i in range(b + 1)
%o A327913     )
%o A327913 A327913 = lambda n, m: F(n, n, 0, m)
%o A327913 for n in range(10):
%o A327913     print([A327913(n, m) for m in range(0, 8)]) # _Peter Luschny_, Apr 09 2021
%Y A327913 Main diagonal is A029894.
%Y A327913 Cf. A028657 (nonequivalent binary n X m matrices).
%Y A327913 Cf. A318396, A328887.
%K A327913 nonn,tabl
%O A327913 0,5
%A A327913 _Andrew Howroyd_, Oct 30 2019