A355226 Irregular triangle read by rows where T(n,k) is the number of independent sets of size k in the n-halved cube graph.

1, 1, 1, 2, 1, 4, 1, 8, 4, 1, 16, 40, 1, 32, 256, 480, 120, 1, 64, 1344, 11200, 36400, 40320, 13440, 1920, 240, 1, 128, 6336, 156800, 2104480, 15644160, 63672000, 136970880, 147748560, 76396800, 21087360, 4273920, 840000, 161280, 28800, 3840, 240

Offset

1,4

Comments

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-halved graph has alpha(G) = A005864(n). The independence polynomial for the n-halved cube is given by Sum_{k=0..alpha(G)} T(n,k)*t^k.

Since 0 <= k <= alpha(G), row n has length A005864(n) + 1.

Links

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

Eric Weisstein's World of Mathematics, Independence polynomial

Eric Weisstein's World of Mathematics, Halved cube graph

Example

Triangle begins:
    k = 0   1   2
n = 1:  1,  1
n = 2:  1,  2
n = 3:  1,  4
n = 4:  1,  8,  4
n = 5:  1, 16, 40
The 4-halved cube graph has independence polynomial 1 + 8*t + 4*t^2.

Prog

(Sage) from sage.graphs.independent_sets import IndependentSets
from collections import Counter
def row(n):
    if n == 1:
        g = graphs.CompleteGraph(1)
    else:
        g = graphs.HalfCube(n)
    setCounts = Counter()
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    outList = [0] * len(setCounts)
    for n in range(0, len(setCounts)):
        outList[n] = setCounts[n]
    return outList

Crossrefs

Row sums are A288943.

Cf. A005864, A355558.

Sequence in context: A146679 A146221 A147457 * A107061 A112481 A134851

Adjacent sequences: A355223 A355224 A355225 * A355227 A355228 A355229

Keyword

nonn,tabf

Author

Christopher Flippen, Jun 24 2022

Status

approved