

A355227


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,2


COMMENTS

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


LINKS



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 5folded 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, n2) + 1)
else:
size = int(pow(2, n2)  1/4 * (1pow(1, n)) * math.comb(n1, 1/2 * (n1)) + 1)
setCounts = [0] * size
for Iset in IndependentSets(g):
setCounts[len(Iset)] += 1
return setCounts


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



