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

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-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.

Examples

			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.
		

Links

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

Crossrefs

Row sums are A288943.

Cf. A005864, A355558.

Programs

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