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