login
Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k = 0..n.
34

%I #92 Oct 05 2024 08:56:57

%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,36,22,6,1,1,7,34,

%T 87,87,34,7,1,1,8,50,190,317,190,50,8,1,1,9,70,386,1053,1053,386,70,9,

%U 1,1,10,95,734,3250,5624,3250,734,95,10,1,1,11,125,1324,9343,28576,28576,9343,1324,125,11,1

%N Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k = 0..n.

%C 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.

%C 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

%C 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

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

%H Alois P. Heinz, <a href="/A028657/b028657.txt">Rows n = 0..45, flattened</a> (first 20 rows from R. W. Robinson)

%H Thomas H. Brylawski, <a href="https://doi.org/10.1002/sapm1975542143">An affine representation for transversal geometries</a>, Studies in Appl. Math. 54 (1975), no. 2, 143-160.

%H F. Harary, L. March and R. W. Robinson, <a href="https://doi.org/10.1068/b050031">On enumerating certain design problems in terms of bicolored graphs with no isolates</a>, Environment and Planning, B 5 (1978), 31-43. See Table 1.

%H F. Harary, L. March and R. W. Robinson, <a href="/A007139/a007139.pdf">On enumerating certain design problems in terms of bicolored graphs with no isolates</a>, Environment and Planning B: Urban Analytics and City Science, 5 (1978), 31-43. [Annotated scanned copy] See Table 1.

%H M. A. Harrison, <a href="http://doi.org/10.1109/T-C.1973.223649">On the number of classes of binary matrices</a>, IEEE Trans. Computers, 22 (1973), 1048-1051.

%H Vladeta Jovovic, <a href="/A005748/a005748.pdf">Binary matrices up to row and column permutations</a>

%H A. Kerber, <a href="/A002727/a002727.pdf">Experimentelle Mathematik</a>, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]

%H B. Misek, <a href="http://dml.cz/dmlcz/108444">On the number of classes of strongly equivalent incidence matrices</a>, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.

%H Carlos Simpson, <a href="https://arxiv.org/abs/2106.03015">Learning proofs for the classification of nilpotent semigroups</a>, arXiv:2106.03015 [cs.LG], 2021.

%H <a href="/index/Mat#inequiv">Index to OEIS entries related to number of inequivalent matrices modulo permutation of row and columns</a>.

%F 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]

%e The triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 3, 3, 1;

%e 1, 4, 7, 4, 1;

%e 1, 5, 13, 13, 5, 1;

%e 1, 6, 22, 36, 22, 6, 1;

%e ...

%e For example, there are 36 graphs on 6 nodes with a distinguished bipartite block with 3 nodes.

%e The array A(m,n) (m>=0, n>=0) (see Comments) begins:

%e 1 1 1 1 1 1 1 1 1 ...

%e 1 2 3 4 5 6 7 8 9 ...

%e 1 3 7 13 22 34 50 70 95 ...

%e 1 4 13 36 87 190 386 734 1324 ...

%e 1 5 22 87 317 1053 3250 9343 25207 ...

%e 1 6 34 190 1053 5624 28576 136758 613894 ...

%e 1 7 50 386 3250 28576 251610 2141733 17256831 ...

%e 1 8 70 734 9343 136758 2141733 33642660 508147108 ...

%e 1 9 95 1324 25207 613894 17256831 508147108 14685630688 ...

%e ... - _N. J. A. Sloane_, Sep 01 2013

%p b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},

%p {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))

%p end:

%p g:= proc(n, k) option remember; add(add(2^add(add(igcd(i, j)*

%p coeff(s, x, i)* coeff(t, x, j), j=1..degree(t)),

%p i=1..degree(s))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,

%p i=1..degree(s))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,

%p i=1..degree(t)), t=b(n+k$2)), s=b(n$2))

%p end:

%p A:= (n, k)-> g(min(n, k), abs(n-k)):

%p seq(seq(A(n, d-n), n=0..d), d=0..14); # _Alois P. Heinz_, Aug 01 2014

%t 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}]]]]];

%t 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]}];

%t A[n_, k_] := g[Min[n, k], Abs[n-k]];

%t Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Jan 28 2015, after _Alois P. Heinz_ *)

%o (PARI)

%o 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}

%o K(q, t)={sum(j=1, #q, gcd(t, q[j]))}

%o 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!}

%o { for(r=0, 10, for(k=0, r, print1(A(r-k,k), ", ")); print) } \\ _Andrew Howroyd_, Mar 25 2020

%o (PARI) \\ G(k,x) gives k-th column as rational function (see Jovovic link).

%o 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}

%o 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))}

%o G(m,x)={my(s=0); forpart(q=m, s+=permcount(q)*Fix(q,x)); s/m!}

%o T(n,k)={my(m=max(k, n-k)); polcoef(G(n-m, x + O(x*x^m)), m)} \\ _Andrew Howroyd_, Mar 26 2020

%o (PARI) A028657(n,k)=A353585(2, n, k) \\ _M. F. Hasler_, May 01 2022

%Y Row sums give A049312.

%Y A246106 is a very similar array.

%Y Cf. A055080, A049312, A052265, A242093.

%Y Diagonals of the array A(m,n) give A002724, A002725, A002728.

%Y Rows (or columns) give A002623, A002727, A006148, A052264.

%Y A(n,k) = A353585(2, n, k).

%K nonn,tabl

%O 0,5

%A _Vladeta Jovovic_, Jun 16 2000