A055609 -id:A055609 - cp's OEIS frontend

A058481 a(n) = 3^n - 2.

1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047, 177145, 531439, 1594321, 4782967, 14348905, 43046719, 129140161, 387420487, 1162261465, 3486784399, 10460353201, 31381059607, 94143178825, 282429536479, 847288609441

Offset: 1

Vladeta Jovovic, Nov 26 2000

a(n) = number of 2 X n binary matrices with no zero rows or columns.
a(n)^2 + 2*a(n+1) + 1 is a square number, i.e., a(n)^2 + 2*a(n+1) + 1 = (a(n)+3)^2: for n=2, a(2)^2 + 2*a(3) + 1 = 7^2 + 2*25 + 1 = 100 = (7+3)^2; for n=3, a(3)^2 + 2*a(4) + 1 = 25^2 + 2*79 + 1 = 784 = (25+3)^2. - Bruno Berselli, Apr 23 2010
Sum of n-th row of triangle of powers of 3: 1; 3 1 3; 9 3 1 3 9; 27 9 3 1 3 9 27; ... . - Philippe Deléham, Feb 24 2014
a(n) = least k such that k*3^n + 1 is a square. Thus, the square is given by (3^n-1)^2. - Derek Orr, Mar 23 2014
Binomial transform of A058481: (1, 6, 12, 24, 48, 96, ...) and second binomial transform of (1, 5, 1, 5, 1, 5, ...). - Gary W. Adamson, Aug 24 2016
Number of ordered pairs of nonempty sets whose union is [n]. a(2) = 7: ({1,2},{1,2}), ({1,2},{1}), ({1,2},{2}), ({1},{1,2}), ({1},{2}), ({2},{1,2}), ({2},{1}). If "nonempty" is omitted we get A000244. - Manfred Boergens, Mar 29 2023

			G.f. = x + 7*x^2 + 25*x^3 + 79*x^4 + 241*x^5 + 727*x^6 + 2185*x^7 + 6559*x^8 + ...
a(1) = 1;
a(2) = 3 + 1 + 3 = 7;
a(3) = 9 + 3 + 1 + 3 + 9 = 25;
a(4) = 27 + 9 + 3 + 1 + 3 + 9 + 27 = 79; etc. - _Philippe Deléham_, Feb 24 2014

G. C. Greubel, Table of n, a(n) for n = 1..1000
John Elias, Illustration: Union of Triple-Sierpinski Triangles
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A055602, A024206 (unlabeled case), A055609, A058482, A000244.

Cf. A003462, A007051, A034472, A024023, A067771, A029858, A134931, A115099, A100774, A079004.

A058481:=n->3^n-2; seq(A058481(n), n=1..30); # Wesley Ivan Hurt, Mar 24 2014

a=1;lst={a};Do[a=a*3+4;AppendTo[lst,a],{n,0,5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 25 2008 *)
3^Range[30]-2  (* Harvey P. Dale, Mar 28 2011 *)
LinearRecurrence[{4, -3}, {1, 7}, 25] (* G. C. Greubel, Aug 25 2016 *)

a(n)=3^n-2 \\ Charles R Greathouse IV, Feb 06 2017

{a(n) = if( n<1, 0, 3^n - 2)}; /* Michael Somos, Feb 17 2017 */

Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m} (-1)^j*C(m, j)*(2^(m-j)-1)^n.
From Mohammad K. Azarian, Jan 14 2009: (Start)
G.f.: 1/(1-3*x)-2/(1-x)+1.
E.g.f.: e^(3*x)-2*(e^x)+1. (End)
a(n) = 3*a(n-1) + 4 (with a(1)=1). - Vincenzo Librandi, Aug 07 2010
a(n) = 4*a(n-1) - 3*a(n-2). - G. C. Greubel, Aug 25 2016

More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000

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

A056152 Triangular array giving number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block with k=1..n-1 vertices, up to isomorphism.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 5, 1, 1, 8, 17, 8, 1, 1, 11, 42, 42, 11, 1, 1, 15, 91, 179, 91, 15, 1, 1, 19, 180, 633, 633, 180, 19, 1, 1, 24, 328, 2001, 3835, 2001, 328, 24, 1, 1, 29, 565, 5745, 20755, 20755, 5745, 565, 29, 1, 1, 35, 930, 15274, 102089, 200082, 102089

Offset: 2

Vladeta Jovovic, Jul 29 2000

Also table read by rows: for 0 < k < n, a(n, k) = number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block with k vertices, up to isomorphism.
a(n, k) is the number of isomorphism classes of finite subdirectly irreducible almost distributive lattices in which the N-quotient has k upper covers and (n - k) lower covers. - David Wasserman, Feb 11 2002
Also, 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.

			Triangle begins:
  1;
  1,  1;
  1,  3,   1;
  1,  5,   5,   1;
  1,  8,  17,   8,  1;
  1, 11,  42,  42,  11,  1;
  1, 15,  91, 179,  91,  15,  1;
  1, 19, 180, 633, 633, 180, 19, 1;
  ...
There are 17 bipartite graphs with 6 vertices, no isolated vertices and a distinguished bipartite block with 3 vertices, or equivalently, there are 17 3 X 3 binary matrices with no zero rows or columns, up to row and column permutation:
[0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1]
[0 0 1] [0 0 1] [0 1 0] [0 1 0] [0 1 0] [0 1 1] [0 1 1] [0 1 1] [1 1 0]
[1 1 0] [1 1 1] [1 0 0] [1 0 1] [1 1 1] [1 0 1] [1 1 0] [1 1 1] [1 1 0]
and
[0 0 1] [0 0 1] [0 1 1] [0 1 1] [0 1 1] [0 1 1] [0 1 1] [1 1 1]
[1 1 0] [1 1 1] [0 1 1] [0 1 1] [1 0 1] [1 0 1] [1 1 1] [1 1 1]
[1 1 1] [1 1 1] [1 0 1] [1 1 1] [1 1 0] [1 1 1] [1 1 1] [1 1 1].

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.

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.

Columns k=1..6 are A000012, A024206, A055609, A055082, A055083, A055084.
Row sums give A055192.
See A122083 for another version of this triangle.
Cf. A049312, A048194, A028657, A049311.

A005745 Number of n-covers of an unlabeled 3-set.

Original entry on oeis.org

1, 6, 23, 65, 156, 336, 664, 1229, 2159, 3629, 5877, 9221, 14070, 20951, 30530, 43634, 61283, 84725, 115461, 155294, 206368, 271210, 352784, 454550, 580509, 735280, 924163, 1153207, 1429292, 1760218, 2154776, 2622859, 3175555, 3825247

Offset: 1

N. J. A. Sloane, Simon Plouffe

Number of n X 3 binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Vladeta Jovovic, Binary matrices up to row and column permutations

A diagonal of A055080.
First differences give A055609.
Cf. A002623, A002727.
Cf. A005744, A005746, A005747, A005748, A005771.

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

a(n) = A002727(n) - A002623(n).

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)^4).

More terms from Vladeta Jovovic, May 26 2000

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

A058482 Number of 3 X n binary matrices with no zero rows or columns.

Original entry on oeis.org

1, 25, 265, 2161, 16081, 115465, 816985, 5745121, 40294561, 282298105, 1976795305, 13839692881, 96884227441, 678208723945, 4747518463225, 33232801429441, 232630126566721, 1628412435648985, 11398891698588745, 79792255837258801, 558545832702224401

Offset: 1

Vladeta Jovovic, Nov 26 2000

Index entries for linear recurrences with constant coefficients, signature (11,-31,21).

Cf. A055602, A024206, A055609 (unlabeled case), A058481, column 3 of A183109 and A218695.

LinearRecurrence[{11,-31,21},{1,25,265},30] (* Harvey P. Dale, Aug 15 2014 *)

a(n) = 7^n-3*3^n+3 \\ Charles R Greathouse IV, Feb 10 2017

Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m}(-1)^j*C(m, j)*(2^(m-j)-1)^n.
a(n) = 7^n-3*3^n+3.
a(n) = 11*a(n-1)-31*a(n-2)+21*a(n-3). G.f.: -x*(21*x^2+14*x+1) / ((x-1)*(3*x-1)*(7*x-1)). - Colin Barker, Jul 10 2013

More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000

More terms from Colin Barker, Jul 10 2013

cp's OEIS Frontend

A058481 a(n) = 3^n - 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

A056152 Triangular array giving number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block with k=1..n-1 vertices, up to isomorphism.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A005745 Number of n-covers of an unlabeled 3-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

A058482 Number of 3 X n binary matrices with no zero rows or columns.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica