A373034 Triangle read by rows: T(n,k) is the number of edge subsets E of the n-dimensional hypercube graph such that E contains a path between two given nodes at Hamming distance k, 0 <= k <= n.

1, 2, 1, 16, 9, 7, 4096, 2703, 2334, 2160, 4294967296, 3425712321, 3245350248, 3170502909, 3127853061

Offset

0,2

Comments

T(n,k)/A061301(n) is the probability that two given nodes at Hamming distance k in the n-dimensional hypercube graph are still connected after each edge has been independently deleted with probability 1/2.

The bunkbed conjecture holds for the n-dimensional hypercube graph with edge-probability 1/2 if and only if the (n+1)-st row is nonincreasing.

Links

Table of n, a(n) for n=0..14.

Wikipedia, Bunkbed conjecture.

Example

Triangle begins:
           1;
           2,          1;
          16,          9,          7;
        4096,       2703,       2334,       2160;
  4294967296, 3425712321, 3245350248, 3170502909, 3127853061;
  ...

Crossrefs

Cf. A061301 (first column), A372705, A373035 (main diagonal).

Sequence in context: A016447 A095850 A324610 * A247125 A290315 A113108

Adjacent sequences: A373031 A373032 A373033 * A373035 A373036 A373037

Keyword

nonn,tabl,more

Author

Pontus von Brömssen, May 20 2024

Status

approved