cp's OEIS Frontend

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.

%I A355227 #25 Feb 26 2024 15:37:43
%S A355227 1,2,1,4,1,8,12,8,2,1,16,80,160,120,16,1,32,400,2560,9280,20256,28960,
%T A355227 31520,29880,24320,16336,8768,3640,1120,240,32,2,1,64,1792,29120,
%U A355227 307440,2239552,11682944,44769920,128380880,279211520,464621248,593908224,582529360,435648640,245610720,102886976,31658620,7189056,1239840,165760,17584,1408,64
%N 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.
%C A355227 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.
%C A355227 Since 0 <= k <= alpha(G), row n has length A058622(n-1) + 1.
%H A355227 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence polynomial</a>
%H A355227 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FoldedCubeGraph.html">Folded cube graph</a>
%e A355227 Triangle begins:
%e A355227     k = 1   2   3    4    5   6
%e A355227 n = 2:  1,  2
%e A355227 n = 3:  1,  4
%e A355227 n = 4:  1,  8, 12,   8,   2
%e A355227 n = 5:  1, 16, 80, 160, 120, 16
%e A355227 The 5-folded cube graph has independence polynomial 1 + 16*t + 80*t^2 + 160*t^3 + 120*t^4 + 16*t^5.
%o A355227 (Sage) from sage.graphs.independent_sets import IndependentSets
%o A355227 def row(n):
%o A355227     g = graphs.FoldedCubeGraph(n)
%o A355227     if n % 2 == 0:
%o A355227         setCounts = [0] * (pow(2, n-2) + 1)
%o A355227     else:
%o A355227         size = int(pow(2, n-2) - 1/4 * (1-pow(-1,n)) * math.comb(n-1, 1/2 * (n-1)) + 1)
%o A355227         setCounts = [0] * size
%o A355227     for Iset in IndependentSets(g):
%o A355227         setCounts[len(Iset)] += 1
%o A355227     return setCounts
%Y A355227 Row sums are A290888.
%Y A355227 Cf. A058622, A355559.
%K A355227 nonn,tabf
%O A355227 2,2
%A A355227 _Christopher Flippen_, Jun 24 2022