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

Author

Andrew Howroyd, May 03 2020

Keywords

• nonn

Comments

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.

Examples

			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
		

Links

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

Crossrefs

Cf. A059525, A268758, A287689.