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

Author

Christopher Flippen, Jun 24 2022

Keywords

• nonn
• tabf

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.

Examples

			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.
		

Links

• Eric Weisstein's World of Mathematics, Independence polynomial
• Eric Weisstein's World of Mathematics, Folded cube graph

Crossrefs

Row sums are A290888.

Cf. A058622, A355559.

Programs

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