Intereting Posts

Injection of union into disjoint union
Show that every large integer has a large prime-power factor
How can I prove it to be a well-defined binary operation?
Norm of the linear functional
Proof by induction that if $n \in \mathbb N$ then it can be written as sum of different Fibonacci numbers
A question on a compact space
Kostrikin's Definition of Tensor Product
$\int_{-\infty}^{\infty}{e^x+1\over (e^x-x+1)^2+\pi^2}\mathrm dx=\int_{-\infty}^{\infty}{e^x+1\over (e^x+x+1)^2+\pi^2}\mathrm dx=1$
Derive a formula to find the number of trailing zeroes in $n!$
Time until a consecutive sequence of ones in a random bit sequence
What's special about the first vector
Does the Frattini subgroup $\Phi(G)$ contain the intersection $Z(G)\cap $.
When does a polynomial take all possible residues modulo any integer?
Presheaf which is not a sheaf — holomorphic functions which admit a holomorphic square root
Defining a Perplexing Two-Dimensional Sequence Explicitly

It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is called *binomial inversion*, for obvious reasons.

Many nice elegant proofs exist (my favorite uses exponential generating functions of $f_n$ and $g_n$), and also many applications (such as proving that if polynomial $f$ of degree $n$ assumes integers values on $0,1,\cdots,n$, then $f(i) \in \mathbb{Z}$ for all integers $i$).

What I’m interested is the following:

- Multiplying three factorials with three binomials in polynomial identity
- Closed-form expression for $\sum_{k=0}^n\binom{n}kk^p$ for integers $n,\,p$
- Show this equality (The factorial as an alternate sum with binomial coefficients).
- Combinatorially prove that $\sum_{i=0}^n {n \choose i} 2^i = 3^n $
- How to prove that $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ is $0$ for $j < p$ and $p!$ for $j = p$
- $\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof

- A nice inclusion-exclusion proof – similar to interpreting Möbius inversion as inclusion-exclusion.
- If $f_0 = g_0 = 0$ and $i | f_i$ for $i>1$, we get, by the Binomial Inversion, that $i | g_i$ (reason: $i\binom{n}{i} = n\binom{n-1}{i-1}$). Is there a nice combinatorial interpretation of this phenomena? Nice applications?
- Are there any more famous/cool inversions (I know of Möbius inversion, binomial inversion, and the discrete derivative inversion $a_i \to a_{i+1}-a_{i})$?

- (combinatorics) prove that on average, n-permutations have Hn cycles without mathematical induction.
- Vandermonde-like identities
- Improvised Question: Combination of selection of pens
- Using generating functions to find a formula for the Tower of Hanoi numbers
- What is the probability of having a pentagon in 6 points
- ${n \choose k} \bmod m$ using Chinese remainder theorem?
- Unique matrix of zeros and ones
- Is $\lfloor n!/e\rfloor$ always even for $n\in\mathbb N$?
- All the ternary n-words with an even sum of digits and a zero.
- Number of solutions of Frobenius equation

These kinds of inverse relations are equivalent to orthogonal relations between sets of numbers.

Suppose you have two triangular sets of numbers $a_{n,k}$ and $b_{n,k}$, each defined for $k = 0, 1, \ldots, n$, such that $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm}.$$ Then $a_{n,k}$ and $b_{n,k}$ are orthogonal, and they have the inverse property you are asking for in (3); i.e., if $f_n = \sum_{k=0}^n a_{n,k} g_k$ then $g_n = \sum_{k=0}^n b_{n,k} f_k$, and vice versa.

*Proof*: $$\sum_{k=0}^n b_{n,k} f_k = \sum_{k=0}^n b_{n,k} \sum_{m=0}^k a_{k,m} g_m = \sum_{m=0}^n \left(\sum_{k=m}^n b_{n,k} a_{k,m}\right) g_m = g_n.$$

Thus binomial inversion follows from the “beautiful identity” $$\sum_{k=m}^n (-1)^{k+m} \binom{n}{k} \binom{k}{m} = \delta_{nm}.$$

Since the orthogonal relation and the inverse relation are equivalent, perhaps the proof of this identity given by Aryabhata or the proof by Yuval Filmus can be considered a combinatorial proof of the inverse relation you describe for binomial coefficients.

**Other examples**

The Lah numbers $L(n,k)$ satisfy $$\sum_{k=m}^n (-1)^{k+m} L(n,k) L(k,m) = \delta_{nm},$$ and so, like the binomial coefficients, are (up to sign) self-orthogonal and have the inverse relation

$$f_n = \sum_{k=0}^n L(n,k) g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} L(n,k) f_k.$$

The two kinds of Stirling numbers, $\left[ n \atop k \right]$ and $\left\{ n \atop k \right\}$, are orthogonal, satisfying

$$\sum_{k=m}^n (-1)^{k+m} \left[ n \atop k \right] \left\{ k \atop m \right\} = \delta_{nm}$$

and

$$\sum_{k=m}^n (-1)^{k+m} \left\{ n \atop k \right\} \left[ k \atop m \right] = \delta_{nm}.$$

Thus they satisfy the inverse relation

$$f_n = \sum_{k=0}^n \left[ n \atop k \right] g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} \left\{ n \atop k \right\} f_k.$$

John Riordan wrote a paper “Inverse Relations and Combinatorial Identities” (*American Mathematical Monthly* 71 (5), May 1964, pp. 485–498) and devoted two of the six chapters of his text *Combinatorial Identities* to these kinds of inverse relations. For example, he shows how inverse relations can be derived from Chebyshev polynomials (since they are orthogonal) and Legendre polynomials (since they are also orthogonal). See the article or the book for many more examples.

**Additional comments and consequences**

The proof using the orthogonal relation can also be applied with respect to the upper index to obtain inverse relations based on the upper index rather than the lower. Thus, for example, we also have (provided, of course, that the sums converge) $$f_n = \sum_{k=n}^\infty \binom{k}{n} g_k \Leftrightarrow g_n = \sum_{k=n}^\infty (-1)^{k+n} \binom{k}{n} f_k,$$

as well as the same kind of thing for the Lah numbers, Stirling numbers, and the other examples.

In addition, these orthogonal relations mean that matrices consisting of orthogonal numbers are inverses. Thus, for example, if $A$ and $B$ are $n \times n$ matrices such that $A_{ij} = \binom{i}{j}$ and $B_{ij} = (-1)^{i+j} \binom{i}{j}$ then the orthogonal relationship implies that $AB = I$. This, of course, means that $BA = I$ as well, and so every orthogonal relationship goes both ways; i.e., $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm} \Leftrightarrow \sum_{k=m}^n a_{n,k} b_{k,m} = \delta_{nm}.$$

For more on inverse matrices consisting of combinatorial numbers, see my answer to the question “Stirling numbers and inverse matrices.”

This identity, Möbius inversion, and the “fundamental theorem of discrete calculus” are all special cases of Möbius inversion on a poset.

- In this identity the relevant poset is the poset of finite subsets of $\mathbb{N}$.
- In classical Möbius inversion it’s the poset $\mathbb{N}$ under division.
- In discrete calculus it’s the poset $\mathbb{Z}_{\ge 0}$ under the usual order.

This beautiful theory was first described by Gian-Carlo Rota in On the Foundations of Combinatorial Theory I, and elaborated on in many other papers. If you like exponential generating functions, you will love On the Foundations of Combinatorial Theory VI. These papers were quite a revelation to me a few years ago and I hope you will enjoy them as well!

A modern reference is Stanley’s Enumerative Combinatorics Vol. I, Chapter 3 (incidentally I believe Stanley was a student of Rota’s). Here is the appropriate specialization of the general result.

**Proposition:** Let $g : \mathcal{P}_{\text{fin}}(\mathbb{N}) \to R$ be a function from the poset of finite subsets of $\mathbb{N}$ to a commutative ring $R$. Let

$$f(T) = \sum_{S \subseteq T} g(S).$$

Then

$$g(T) = \sum_{S \subseteq T} (-1)^{|S| – |T|} f(S)$$

where $|S|$ denotes the size of $S$. (The special case you state is for when $g$ only depends on $|S|$.)

*Proof.* This is actually a slightly more general form of inclusion-exclusion. It suffices to exchange the order of summation in

$$\sum_{S \subseteq T} (-1)^{|S| – |T|} \sum_{R \subseteq S} g(R) = \sum_{R \subseteq T} g(R) \sum_{R \subseteq S \subseteq T} (-1)^{|S| – |T|}$$

and observe that the resulting coefficient is equal to $(1 – 1)^{|R| – |T|}$, which is equal to $0$ unless $R = T$ in which case it is equal to $1$. Of course I can mumble my way through the standard inclusion-exclusion proof as well: start with $f(T)$, which has too many terms, so subtract the terms $f(T – \{ t \})$, but we’ve subtracted the other terms too many times, so add back the terms $f(T – \{ t_1, t_2 \})$…

A fundamental observation about Möbius functions in general is that they are multiplicative under product of posets. The posets I’ve named above are all products of chains, so one can quickly compute their Möbius functions simply by computing the Möbius function of a chain.

- Examples when vector $(X,Y)$ is not normal 2D distribution, but X and Y are.
- decimal representation of $2^m$ starts with a particular finite sequence of decimal digits
- Gradient is NOT the direction that points to the minimum or maximum
- Terminology help for a set relation: for sets $X, Y$, not necessarily disjoint, such that neither is a subset of the other.
- an example of a continuous function whose Fourier series diverges at a dense set of points
- Isomorphic quotient groups
- I understand what a division ring is, but cannot find any examples. Can anyone give me one?
- Is there a general formula for the derivative of $\exp(A(x))$ when $A(x)$ is a matrix?
- If $R$ is a commutative ring with unity and $R$ has only one maximal ideal then show that the equation $x^2=x$ has only two solutions
- Homework: No field extension is “degree 4 away from an algebraic closure”
- Equation to check if a set of vertices form a real polygon?
- Simplifying an Arctan equation
- Find the probability function of $X_1+X_2$ in geometric distribution
- Is sum of square of primes a square of prime?
- Joint cdf and pdf of the max and min of independent exponential RVs