A059525 -id:A059525 - cp's OEIS frontend

A331878 Number of (non-null) connected induced subgraphs in a right-triangular graph with n vertices on each side.

1, 6, 32, 242, 3389, 94204, 5152184, 550554052, 114558123057, 46273463018266, 36187365370984792, 54676438562307219806, 159361336209506075254061, 894922393831489478287443136, 9673844907264825614989071514624, 201139020197000279384599867300494336

Offset: 1

Andrew Howroyd, May 03 2020

nonn

a(n) is the number of lower triangular n X n binary arrays with all 1's connected.

a(n) is the number of ways to place a fixed polyomino on an n X n grid with all squares above the main diagonal unoccupied.

			The graphs for n = 2 and n = 3 are illustrated below:
                   o
        o          |
        |          o---o
        o---o      |   |
                   o---o---o
.
The a(2) = 6 connected induced subgraphs are:
     X     o     o     X     o     X
     o o   X o   o X   X o   X X   X X

Eric Weisstein's World of Mathematics, Induced Subgraph
Eric Weisstein's World of Mathematics, Polyomino

Cf. A059525, A268758, A287689.

A362517 Number of vertex cuts in the n X n grid graph.

Original entry on oeis.org

0, 2, 293, 54029, 31252554, 66987393994, 558077003446645, 18395727255104656873, 2415871083397827261386598, 1267366225909683571167215895590, 2658305260824415112030141755123193237, 22300450681634123362049304128770788322086749, 748286719216207999401963616395813243234643176461730

Offset: 1

Eric W. Weisstein, Apr 23 2023

nonn

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Vertex Cut

Cf. A059525.

a(n) = 2^(n^2) - 1 - A059525(n). - Pontus von Brömssen, Apr 23 2023

More terms (based on data in A059525) from Pontus von Brömssen, Apr 23 2023

cp's OEIS Frontend

A331878 Number of (non-null) connected induced subgraphs in a right-triangular graph with n vertices on each side.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs