cp's OEIS Frontend

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

%I A354802 #39 Jun 27 2025 22:01:15
%S A354802 1,1,1,2,1,4,2,1,8,16,8,2,1,16,88,208,228,128,56,16,2,1,32,416,2880,
%T A354802 11760,29856,48960,54304,44240,29920,17952,9088,3672,1120,240,32,2,1,
%U A354802 64,1824,30720,342400,2682432,15328064,65515840,213464240,538811200,1070860384,1708551424,2245780976,2517976640,2509047680
%N A354802 Irregular triangle read by rows where T(n,k) is the number of independent sets of size k in the n-hypercube graph.
%C A354802 The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-hypercube has alpha(G) = 1 for n = 0 and alpha(G) = 2^(n-1) for n >= 1. The independence polynomial for the n-hypercube is given by Sum_{k=0..alpha(G)} T(n,k)*t^k.
%C A354802 Since 0 <= k <= alpha(G), row n has length 2^(n-1) + 1 except for n = 0 which has length 2.
%C A354802 Jenssen, Perkins and Potukuchi proved asymptotics for independent sets of given size.
%H A354802 Christopher Flippen, <a href="/A354802/b354802.txt">Table of n, a(n) for n = 0..71</a>
%H A354802 M. Jenssen, W. Perkins and A. Potukuchi, <a href="https://doi.org/10.1017/S0963548321000559">Independent sets of a given size and structure in the hypercube</a>, Combinatorics, Probability and Computing, 2022, 1-19; see also <a href="https://arxiv.org/abs/2106.09709">arXiv:2106.09709</a> [math.CO], 2021-2022.
%H A354802 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube graph</a>
%H A354802 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence polynomial</a>
%e A354802 Triangle begins:
%e A354802   n=0: 1, 1
%e A354802   n=1: 1, 2
%e A354802   n=2: 1, 4, 2
%e A354802   n=3: 1, 8, 16, 8, 2
%e A354802   n=4: 1, 16, 88, 208, 228, 128, 56, 16, 2
%e A354802 The 3-hypercube graph has independence polynomial 1 + 8*t + 16*t^2 + 8*t^3 + 2*t^4.
%o A354802 (Sage) from sage.graphs.independent_sets import IndependentSets
%o A354802 def row(n):
%o A354802     if n == 0:
%o A354802         g = graphs.CompleteGraph(1)
%o A354802         setCounts = [0, 0]
%o A354802     else:
%o A354802         g = graphs.CubeGraph(n)
%o A354802         setCounts = [0] * (pow(2,n - 1) + 1)
%o A354802     for Iset in IndependentSets(g):
%o A354802         setCounts[len(Iset)] += 1
%o A354802     return setCounts
%o A354802 # _Christopher Flippen_ and Scott Taylor, Jun 06 2022
%Y A354802 Cf. A027624 (row sums), A354082 (alternating sums).
%K A354802 nonn,tabf
%O A354802 0,4
%A A354802 _Christopher Flippen_, Jun 06 2022