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

1, 2, 1, 4, 1, 8, 12, 8, 2, 1, 16, 80, 160, 120, 16, 1, 32, 400, 2560, 9280, 20256, 28960, 31520, 29880, 24320, 16336, 8768, 3640, 1120, 240, 32, 2, 1, 64, 1792, 29120, 307440, 2239552, 11682944, 44769920, 128380880, 279211520, 464621248, 593908224, 582529360, 435648640, 245610720, 102886976, 31658620, 7189056, 1239840, 165760, 17584, 1408, 64

Offset

2,2

Comments

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

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

Links

Table of n, a(n) for n=2..56.

Eric Weisstein's World of Mathematics, Independence polynomial

Eric Weisstein's World of Mathematics, Folded cube graph

Example

Triangle begins:
    k = 1   2   3    4    5   6
n = 2:  1,  2
n = 3:  1,  4
n = 4:  1,  8, 12,   8,   2
n = 5:  1, 16, 80, 160, 120, 16
The 5-folded cube graph has independence polynomial 1 + 16*t + 80*t^2 + 160*t^3 + 120*t^4 + 16*t^5.

Prog

(Sage) from sage.graphs.independent_sets import IndependentSets
def row(n):
    g = graphs.FoldedCubeGraph(n)
    if n % 2 == 0:
        setCounts = [0] * (pow(2, n-2) + 1)
    else:
        size = int(pow(2, n-2) - 1/4 * (1-pow(-1, n)) * math.comb(n-1, 1/2 * (n-1)) + 1)
        setCounts = [0] * size
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    return setCounts

Crossrefs

Cf. A058622.

Sequence in context: A107061 A112481 A134851 * A264148 A038001 A147080

Adjacent sequences: A355224 A355225 A355226 * A355228 A355229 A355230

Keyword

nonn,tabf

Author

Christopher Flippen, Jun 24 2022

Status

approved