A123301 Triangle read by rows: T(n,k) is the number of specially labeled bicolored nonseparable graphs with k points in one color class and n-k points in the other class. "Special" means there are separate labels 1,2,...,k and 1,2,...,n-k for the two color classes (n >= 2, k = 1,...,n-1).
1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 34, 1, 0, 0, 1, 199, 199, 1, 0, 0, 1, 916, 7037, 916, 1, 0, 0, 1, 3889, 117071, 117071, 3889, 1, 0, 0, 1, 15982, 1535601, 6317926, 1535601, 15982, 1, 0, 0, 1, 64747, 18271947, 228842801, 228842801, 18271947
Offset: 2
Examples
Triangle begins: 1; 0, 0; 0, 1, 0; 0, 1, 1, 0; 0, 1, 34, 1, 0; 0, 1, 199, 199, 1, 0; 0, 1, 916, 7037, 916, 1, 0; 0, 1, 3889, 117071, 117071, 3889, 1, 0; ... Formatted as an array: ================================================= k/j | 1 2 3 4 5 6 --- +------------------------------------------- 1 | 1 0 0 0 0 0 ... 2 | 0 1 1 1 1 1 ... 3 | 0 1 34 199 916 3889 ... 4 | 0 1 199 7037 117071 1535601 ... 5 | 0 1 916 117071 6317926 228842801 ... 6 | 0 1 3889 1535601 228842801 21073662977 ... ...
References
- R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
Links
- Andrew Howroyd, Table of n, a(n) for n = 2..1276 (first 50 rows; first 24 rows from R. W. Robinson)
- F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
Programs
-
PARI
G(n)={sum(i=0, n, x^i*(sum(j=0, n, y^j*2^(i*j)/(i!*j!)) + O(y*y^n))) + O(x*x^n)} \\ this switches x/y halfway through because PARI only does serreverse in x. B(n)={my(p=log(G(n))); p=subst(deriv(p,y), x, serreverse(x*deriv(p,x))); p=substvec(p, [x,y], [y,x]); intformal(log(x/serreverse(x*p)))} M(n)={my(p=B(n)); matrix(n,n,i,j,polcoef(polcoef(p,j),i)*i!*j!)} { my(A=M(6)); for(n=1, #A~, print(A[n,])) } \\ Andrew Howroyd, Jan 04 2021
Formula
A004100(n) = (1/2) * Sum_{k=1..n-1} binomial(n,k)*T(n,k). - Andrew Howroyd, Jan 03 2021
Extensions
Offset corrected by Andrew Howroyd, Jan 04 2021