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,2

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.

Links

Table of n, a(n) for n=1..16.

Eric Weisstein's World of Mathematics, Induced Subgraph

Eric Weisstein's World of Mathematics, Polyomino

Example

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

Crossrefs

Cf. A059525, A268758, A287689.

Sequence in context: A020013 A283326 A221540 * A121120 A183681 A326985

Adjacent sequences: A331875 A331876 A331877 * A331879 A331880 A331881

Keyword

nonn

Author

Andrew Howroyd, May 03 2020

Status

approved