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

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, 11760, 29856, 48960, 54304, 44240, 29920, 17952, 9088, 3672, 1120, 240, 32, 2, 1, 64, 1824, 30720, 342400, 2682432, 15328064, 65515840, 213464240, 538811200, 1070860384, 1708551424, 2245780976, 2517976640, 2509047680

Offset: 0

Author

Christopher Flippen, Jun 06 2022

Keywords

• nonn
• tabf

Comments

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.

Since 0 <= k <= alpha(G), row n has length 2^(n-1) + 1 except for n = 0 which has length 2.

Jenssen, Perkins and Potukuchi proved asymptotics for independent sets of given size.

Examples

			Triangle begins:
  n=0: 1, 1
  n=1: 1, 2
  n=2: 1, 4, 2
  n=3: 1, 8, 16, 8, 2
  n=4: 1, 16, 88, 208, 228, 128, 56, 16, 2
The 3-hypercube graph has independence polynomial 1 + 8*t + 16*t^2 + 8*t^3 + 2*t^4.
		

Links

• Christopher Flippen, Table of n, a(n) for n = 0..71
• M. Jenssen, W. Perkins and A. Potukuchi, Independent sets of a given size and structure in the hypercube, Combinatorics, Probability and Computing, 2022, 1-19; see also arXiv:2106.09709 [math.CO], 2021-2022.
• Eric Weisstein's World of Mathematics, Hypercube graph
• Eric Weisstein's World of Mathematics, Independence polynomial

Crossrefs

Cf. A027624 (row sums), A354082 (alternating sums).

Programs

Sage

from sage.graphs.independent_sets import IndependentSets
def row(n):
    if n == 0:
        g = graphs.CompleteGraph(1)
        setCounts = [0, 0]
    else:
        g = graphs.CubeGraph(n)
        setCounts = [0] * (pow(2,n - 1) + 1)
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    return setCounts
# Christopher Flippen and Scott Taylor, Jun 06 2022