OFFSET
0,5
COMMENTS
Also, row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color; the color classes are not interchangeable.
Also the number of principal transversal matroids (also known as fundamental transversal matroids) of size n and rank k (originally enumerated by Brylawski). - Gordon F. Royle, Oct 30 2007
This sequence is also obtained if we read the array A(m,n) = number of inequivalent m X n binary matrices by antidiagonals, where equivalence means permutations of rows or columns (m>=0, n>=0) [Kerber]. - N. J. A. Sloane, Sep 01 2013
REFERENCES
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
LINKS
Alois P. Heinz, Rows n = 0..45, flattened (first 20 rows from R. W. Robinson)
Thomas H. Brylawski, An affine representation for transversal geometries, Studies in Appl. Math. 54 (1975), no. 2, 143-160.
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning, B 5 (1978), 31-43. See Table 1.
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning B: Urban Analytics and City Science, 5 (1978), 31-43. [Annotated scanned copy] See Table 1.
M. A. Harrison, On the number of classes of binary matrices, IEEE Trans. Computers, 22 (1973), 1048-1051.
Vladeta Jovovic, Binary matrices up to row and column permutations
A. Kerber, Experimentelle Mathematik, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]
B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.
Carlos Simpson, Learning proofs for the classification of nilpotent semigroups, arXiv:2106.03015 [cs.LG], 2021.
FORMULA
A(m,n) = Sum_{p in P(m), q in P(n)} 2^Sum_{i in p, j in q} gcd(i,j) / (N(p) N(q)) where P(m) are the partition of m (see e.g., A036036), N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p. [corrected by Anders Kaseorg, Oct 04 2024]
EXAMPLE
The triangle T(n,k) begins:
1;
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 7, 4, 1;
1, 5, 13, 13, 5, 1;
1, 6, 22, 36, 22, 6, 1;
...
For example, there are 36 graphs on 6 nodes with a distinguished bipartite block with 3 nodes.
The array A(m,n) (m>=0, n>=0) (see Comments) begins:
1 1 1 1 1 1 1 1 1 ...
1 2 3 4 5 6 7 8 9 ...
1 3 7 13 22 34 50 70 95 ...
1 4 13 36 87 190 386 734 1324 ...
1 5 22 87 317 1053 3250 9343 25207 ...
1 6 34 190 1053 5624 28576 136758 613894 ...
1 7 50 386 3250 28576 251610 2141733 17256831 ...
1 8 70 734 9343 136758 2141733 33642660 508147108 ...
1 9 95 1324 25207 613894 17256831 508147108 14685630688 ...
... - N. J. A. Sloane, Sep 01 2013
MAPLE
b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
{seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
end:
g:= proc(n, k) option remember; add(add(2^add(add(igcd(i, j)*
coeff(s, x, i)* coeff(t, x, j), j=1..degree(t)),
i=1..degree(s))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
i=1..degree(s))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
i=1..degree(t)), t=b(n+k$2)), s=b(n$2))
end:
A:= (n, k)-> g(min(n, k), abs(n-k)):
seq(seq(A(n, d-n), n=0..d), d=0..14); # Alois P. Heinz, Aug 01 2014
MATHEMATICA
b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Union[ Flatten[ Table[ Function[ {p}, p + j*x^i] /@ b[n - i*j, i-1], {j, 0, n/i}]]]]];
g[n_, k_] := g[n, k] = Sum[ Sum[ 2^Sum[ Sum[GCD[i, j] * Coefficient[s, x, i] * Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}] / Product[i^Coefficient[s, x, i] * Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}] / Product[i^Coefficient[t, x, i] * Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n+k, n+k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n-k]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)
PROG
(PARI)
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t)={sum(j=1, #q, gcd(t, q[j]))}
A(n, m)={my(s=0); forpart(q=m, s+=permcount(q)*polcoef(exp(sum(t=1, n, 2^K(q, t)/t*x^t) + O(x*x^n)), n)); s/m!}
{ for(r=0, 10, for(k=0, r, print1(A(r-k, k), ", ")); print) } \\ Andrew Howroyd, Mar 25 2020
(PARI) \\ G(k, x) gives k-th column as rational function (see Jovovic link).
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
Fix(q, x)={my(v=divisors(lcm(Vec(q))), u=apply(t->2^sum(j=1, #q, gcd(t, q[j])), v)); 1/prod(i=1, #v, my(t=v[i]); (1-x^t)^(sum(j=1, i, my(d=t/v[j]); if(!frac(d), moebius(d)*u[j]))/t))}
G(m, x)={my(s=0); forpart(q=m, s+=permcount(q)*Fix(q, x)); s/m!}
T(n, k)={my(m=max(k, n-k)); polcoef(G(n-m, x + O(x*x^m)), m)} \\ Andrew Howroyd, Mar 26 2020
KEYWORD
nonn,tabl
AUTHOR
Vladeta Jovovic, Jun 16 2000
STATUS
approved