Sums over hypercubes are strange. By a “hypercube,” I mean $\{x, y\}^n$ where $x$ and $y$ are distinct symbols. For example, take $x = -1$ and $y = 1$. If we define

for $v \in \{-1, 1\}^n$, then

Here’s another one:

And another:

Aren’t these weird? What’s going on here? I want to try and explain at least a small collection of these.

Products, products, products

Despite what I just said about hypercube sums being weird, they are actually quite natural objects. If you ever want to expand a product of binomials into a sum, then you are secretly thinking about hypercube sums. Given the product

any length-$n$ string consisting of two distinct symbols will tell you how to form one term in the expansion. For example, if L means “left,” and R means “right,” then the string LRL might correspond to the term $x^2 y$ in the product $(x + y)^3$.

We can write this formally like so:

This right-hand side has lots of flexibility: Pick any two values for the hypercube that might be convenient, then use them in the expression however you like. For example, given any function $f$,

This is a little too general to be interesting. Let’s see something more concrete.

Generating functions, generating functions, generating functions

In the land of generating functions, it is often natural to consider functions of the form $e^{D(x)}$, where $D(x)$ is some generating function such that $D(0) = 0$. These arise in the study of exponential families, and help count things like graphs and partitions of sets and so on¹. Here, these functions are just the proper form to generate our identities.

Let $D(x)$ be a generating function such that $D(0) = 0$. Consider the difference

where $a_k$ is some constant. If we set $d = [x] D(x)$, then

Multiplying the first $n$ of these differences yields

Only a single term of $x^n$ appears, so the coefficient on $x^n$ in this product is

On the other hand, from the previous section we can write our product as a convenient hypercube sum over $\{-1, 1\}^n$:

The sum in the exponential looks like an inner product, so let’s not shy away from that; define $(a, v) = \sum_{k = 1}^n a_k v_k$ for any two vectors of the appropriate length. Now we can write

If we equate coefficients with \eqref{product-side}, then we have a final identity

We are now within striking distance of excitement. Let’s see some examples to get the fire going.

Examples

The simplest possible example is $D(x) = 0$. The requisite coefficients in \eqref{ident} are

for $n \geq 1$. Thus \eqref{ident} reads

for $n \geq 1$.

Next up is $D(x) = x$. Our coefficients are

Since $d = 1$ here, equation \eqref{ident} yields

Define $w(v) = \sum_{k = 1}^n v_k$. Taking $a$ to be the all-ones sequence, our identity yields

Before we continue, let’s check some small cases. If $n = 1$, then this identity reduces to

Good. For $n = 2$, it is

It checks.

Let’s turn the heat up a little. If we set $D(x) = -\log(1 - x)$, then the generating function part of the summand in \eqref{ident} is $(1 - x)^{-(a, v)}.$ The binomial theorem tells us that

Since $d = 1$ here, equation \eqref{ident} now reads

If we rewrite that binomial coefficient, then we could also say

As before, taking $a$ to be the all-ones sequence yields interesting special cases:

These three examples are enough to generate all of the identities we stated in the previous section, but we have one more application to see.

More about exponential families

Let’s look at \eqref{ident} more closely². The equation is valid for any generating function $D(x)$ with $D(0) = 0$, but any generating function of the form $\exp(D(x))$ shouts “Exponential families!” until you listen. An exponential family is a sequence of “decks” of “cards” from which we form “hands.” The sequence $d_n$ is the number of cards in the $n$th deck for $n \geq 1$. We define $h(n, k)$ to be the number of hands of weight $n$ with $k$ cards. The bivariate, mixed-type generating function

is called the hand-enumerator of the exponential family, and the single-variable exponential generating function

is the deck-enumerator of the family. The exponential formula states that

This is supremely interesting to us, because the left-hand side of \eqref{ident} contains an expression of the form $e^{y D(x)}$ where $y = (a, v)$ is just some number. Thus, if we are working in an exponential family,

and plugging this into the full identity gives

For simplicity, let’s take $a$ to be the all-ones sequence, so that this reads

This is a very strange identity. It holds for all exponential families, yet the only parameter specific to the family on the right-hand side is $d$, the number of cards of weight $1$ in the family.

For example, \eqref{hand-sum} holds with $h(n, k)$ defined as the number of:

• labeled graphs with vertex set $[n]$ and $k$ connected components;
• permutations on $[n]$ with $k$ disjoint cycles; and
• partitions of $[n]$ into $k$ disjoint parts.

This identity is so general that it must have a combinatorial proof, yet it almost seems too general to believe that one could exist! I haven’t come up with one yet, but I hope to learn one eventually.

Here’s a notable example: Let $h(n, k)$ be the number of 2-regular graphs on $n$ vertices with $k$ connected components. Then

To be honest, I’m skeptical of these last few identities. Here is some code to at least numerically settle your stomach if you also have doubts:

import itertools
from sympy import binomial, factorial, log
from sympy.functions.combinatorial.numbers import stirling
from sympy.abc import x

def sgn(v):
    return (-1)**sum(1 for x in v if x == -1)

def prod(a, v):
    return sum(a[k] * v[k] for k in range(len(a)))

def norm(v):
    a = [1] * len(v)
    return prod(a, v)

def sgn_sum(a):
    n = len(a)
    vs = itertools.product([-1, 1], repeat=n)

    return sum(sgn(v) * prod(a, v)**n for v in vs)

def binomial_sum(a):
    n = len(a)
    vs = itertools.product([-1, 1], repeat=n)

    return sum(sgn(v) * binomial(-prod(a, v), n) for v in vs)

def exponential_family_sum(h, n):
    """
    This should always equal

        (2d)^n * n!

    where d is the size of the weight-1 deck of the exponential family.

    """
    vs = itertools.product([-1, 1], repeat=n)

    return sum(sgn(v) * h(n, k) * norm(v)**k for v in vs for k in range(1, n + 1))

def exponential_family_list(h, n):
    vs = itertools.product([-1, 1], repeat=n)

    return [sgn(v) * h(n, k) * norm(v)**k for v in vs for k in range(1, n + 1)]

def two_regular_hand(n, k):
    D = -(log(1 - x) + x + x**2 / 2) / 2

    needed_power = n // k + 1
    expr = (D.series(n=needed_power)**k / factorial(k)).expand()

    return factorial(n) * expr.coeff(x**n)

def two_regular_sum(n):
    return exponential_family_sum(two_regular_hand, n)

def stirling_sum(n, kind=2):
    return exponential_family_sum(lambda n, k: stirling(n, k, kind=kind), n)

Credits

I am out of easy examples, but I should say where these ideas originated.

This approach was merely a generalization of a single step (!) from a proof contained in David and Jonathan Borwein’s “Some Remarkable Properties of Sinc and Related Integrals”. Theorem 2 of this paper contains the identity

which, in the language of this post, is essentially

The proof of this identity is done in exactly the way we have described here, by first considering the product

as a hypercube sum, and then expanding the product’s factors and looking at the coefficient on $x$ in the end result. This is just taking $D(x) = x$ in \eqref{ident}.

From the exponential family perspective, this is the most boring family possible: It has a single nonempty deck with a single card. Even so, the identity shows that generating functions can make boring toys exciting again.