login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028657 Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k=0..n. 13
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 (list; table; graph; refs; listen; history; text; internal format)
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.

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.

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 33642 660508 147108 ...

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 *)

CROSSREFS

Row sums give A049312.

A246106 is a very similar array.

Cf. A055080, A049312, A242093.

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

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

Sequence in context: A094526 A088699 A101515 * A053534 A104881 A171699

Adjacent sequences:  A028654 A028655 A028656 * A028658 A028659 A028660

KEYWORD

nonn,tabl

AUTHOR

Vladeta Jovovic, Jun 16 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 08:45 EDT 2019. Contains 328056 sequences. (Running on oeis4.)