A028657 Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k = 0..n.
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, 1, 7, 34, 87, 87, 34, 7, 1, 1, 8, 50, 190, 317, 190, 50, 8, 1, 1, 9, 70, 386, 1053, 1053, 386, 70, 9, 1, 1, 10, 95, 734, 3250, 5624, 3250, 734, 95, 10, 1, 1, 11, 125, 1324, 9343, 28576, 28576, 9343, 1324, 125, 11, 1
Offset: 0
Examples
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
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.
- Index to OEIS entries related to number of inequivalent matrices modulo permutation of row and columns.
Crossrefs
Programs
-
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 *) -
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 -
PARI
A028657(n,k)=A353585(2, n, k) \\ M. F. Hasler, May 01 2022
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]
Comments