A056152 -id:A056152 - cp's OEIS frontend

A055609 Number of 3 X n binary matrices with no zero rows or columns, up to row and column permutation.

1, 5, 17, 42, 91, 180, 328, 565, 930, 1470, 2248, 3344, 4849, 6881, 9579, 13104, 17649, 23442, 30736, 39833, 51074, 64842, 81574, 101766, 125959, 154771, 188883, 229044, 276085, 330926, 394558, 468083, 552696, 649692, 760482, 886602, 1029691, 1191539, 1374065, 1579326

Offset: 1

Vladeta Jovovic, Jun 03 2000

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3, -1, -3, -1, 3, 6, -6, -3, 1, 3, 1, -3, 1).

Column k=3 of A056152.

Cf. A024206, A002623, A002727.

Vec((G(3, x) - G(2, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

G.f.: x*(x^8-x^7-x^6-2*x^5+2*x^4+x^3-3*x^2-2*x-1)/((x^3-1)^2*(x^2-1)^2*(x-1)^3).

Terms a(37) and beyond from Andrew Howroyd, Mar 25 2020

A055192 Number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block, up to isomorphism.

Original entry on oeis.org

1, 2, 5, 12, 35, 108, 393, 1666, 8543, 54190, 436740, 4565450, 62930604, 1156277748, 28509174012, 946786816168, 42448800498744, 2573207315483554, 211180300735118954, 23490473719472829824, 3545759835559406756008, 727077827560669587718290

Offset: 2

Vladeta Jovovic, Jun 18 2000

nonn

Also the number of connected split graphs on n vertices (cf. A048194). - Falk Hüffner, Dec 01 2015

Inverse Euler transform is A007776. - Andrew Howroyd, Oct 03 2018

Alois P. Heinz, Table of n, a(n) for n = 2..40

Equals second differences of A049312.
Cf. A007776, A024206, A055609, A055082, A055083, A055084.
Row sums of A056152 and also of A122083.

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[ Map[ 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]];
A049312[d_] := Sum[A[n, d - n], {n, 0, d}];
Differences[Table[A049312[n], {n, 0, 23}], 2] (* Jean-François Alcover, Sep 05 2019, after Alois P. Heinz in A049312 *)

A218695 Square array A(h,k) = (2^h-1)A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 7, 1, 1, 25, 25, 1, 1, 79, 265, 79, 1, 1, 241, 2161, 2161, 241, 1, 1, 727, 16081, 41503, 16081, 727, 1, 1, 2185, 115465, 693601, 693601, 115465, 2185, 1, 1, 6559, 816985, 10924399, 24997921, 10924399, 816985, 6559, 1

Offset: 1

M. F. Hasler, Nov 04 2012

This symmetric table is defined in the Kreweras papers, used also in A223911. Its upper or lower triangular part equals A183109, which might provide a simpler formula.
Number of h X k binary matrices with no zero rows or columns. - Andrew Howroyd, Mar 29 2023
A(h,k) is the number of coverings of [h] by tuples (A_1,...,A_k) in P([h])^k with nonempty A_j, with P(.) denoting the power set. For the disjoint case see A019538. For tuples with "nonempty" omitted see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). - Manfred Boergens, May 26 2024

			Array A(h,k) begins:
=====================================================
h\k | 1   2      3        4         5           6 ...
----+------------------------------------------------
  1 | 1   1      1        1         1           1 ...
  2 | 1   7     25       79       241         727 ...
  3 | 1  25    265     2161     16081      115465 ...
  4 | 1  79   2161    41503    693601    10924399 ...
  5 | 1 241  16081   693601  24997921   831719761 ...
  6 | 1 727 115465 10924399 831719761 57366997447 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
G. Kreweras, Dénombrements systématiques de relations binaires externes, Math. Sci. Humaines 26 (1969) 5-15.
G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.

Columns 1..3 are A000012, A058481, A058482.
Main diagonal is A048291.
Cf. A019538, A056152 (unlabeled case), A052332, A092477, A183109, A223911, A329943.

c(h,k)={(h<2 || k<2) & return(1); sum(i=1,h-1,binomial(h,h-i)*2^i*c(i,k-1))+(2^h-1)*c(h,k-1)}
/* For better performance when h and k are large, insert the following memoization code before "sum(...)": cM=='cM & cM=matrix(h,k); my(s=matsize(cM));
s[1] >= h & s[2] >= k & cM[h,k] & return(cM[h,k]);
s[1]

A(m, n) = sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n ) \\ Andrew Howroyd, Mar 29 2023

From Andrew Howroyd, Mar 29 2023: (Start)
A(h, k) = Sum_{i=0..h} (-1)^(h-i) * binomial(h, i) * (2^i-1)^k.
A052332(n) = Sum_{i=1..n-1} binomial(n,i)*A(i, n-i) for n > 0. (End)

A055084 Number of 6 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 15, 180, 2001, 20755, 200082, 1781941, 14637962, 111011667, 779695050, 5093379110, 31092553357, 178203364143, 963217652830, 4930357535218, 23989343505296, 111335037107474, 494383391324356, 2106346854756098

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500

Column k=6 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(6, x) - G(5, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 8, 42, 179, 633, 2001, 5745, 15274, 38000, 89331, 199715, 427184, 878152, 1741964, 3345562, 6239390, 11327863, 20065972, 34747460, 58924066, 98002370, 160086580, 257148244, 406637336, 633669040, 973971441, 1477810227, 2215179768, 3282598034, 4811946882

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000
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.
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]

Column k=4 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(4, x) - G(3, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Terms a(21) and beyond from Andrew Howroyd, Mar 25 2020

A055083 Number of 5 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 11, 91, 633, 3835, 20755, 102089, 461272, 1930310, 7534742, 27602968, 95428291, 312864361, 976985630, 2917175450, 8357692894, 23046527311, 61337188725, 157950527167, 394427897066, 957058104818, 2260601179661, 5206447640059, 11709619965923, 25752660738209

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Column k=5 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(5, x) - G(4, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Terms a(21) and beyond from Andrew Howroyd, Mar 25 2020

A122083 Triangle read by rows in which row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color, with no isolated nodes; the color classes are not interchangeable.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 3, 1, 0, 0, 1, 5, 5, 1, 0, 0, 1, 8, 17, 8, 1, 0, 0, 1, 11, 42, 42, 11, 1, 0, 0, 1, 15, 91, 179, 91, 15, 1, 0, 0, 1, 19, 180, 633, 633, 180, 19, 1, 0, 0, 1, 24, 328, 2001, 3835, 2001, 328, 24, 1, 0, 0, 1, 29, 565, 5745, 20755, 20755

Offset: 0

N. J. A. Sloane, Oct 19 2006

			K M N Gives the number N of unlabeled bicolored graphs with no isolated nodes and having K nodes of one color and M nodes of the other color.
0 0 1
Total( 0)= 1
0 1 0
1 0 0
Total( 1)= 0
0 2 0
1 1 1
2 0 0
Total( 2)= 1
0 3 0
1 2 1
2 1 1
3 0 0
Total( 3)= 2
0 4 0
1 3 1
2 2 3
3 1 1
4 0 0
Total( 4)= 5
0 5 0
1 4 1
2 3 5
3 2 5
4 1 1
5 0 0
Total( 5)= 12
0 6 0
1 5 1
2 4 8
3 3 17
4 2 8
5 1 1
6 0 0
Total( 6)= 35

J. G. Lee, Almost Distributive Lattice Varieties, Algebra Universalis, 21 (1985), 280-304.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

R. W. Robinson, First 20 rows, flattened
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 2.
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 2.

Row sums give A055192. See A056152 for a version of this triangle with the bounding zeros in each row.

cp's OEIS Frontend

A055609 Number of 3 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A055192 Number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block, up to isomorphism.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A218695 Square array A(h,k) = (2^h-1)*A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)*2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A055084 Number of 6 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A055083 Number of 5 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A122083 Triangle read by rows in which row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color, with no isolated nodes; the color classes are not interchangeable.

Views

Author

Keywords

Examples

References

Links

Crossrefs

A218695 Square array A(h,k) = (2^h-1)A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.