§ Finite differences and Umbral calculus
Umbral calculus lays out a large collection of "umbral" / "shadowy"
coincidences across combinatorics and calculus. Here, I'll lay out some of
these that I learnt from Concrete Mathematics .
I hope to use this for myself to motivate a bunch of combinatorics. I'll
provide an interesting proof of why
using this umbral calculus.
§ Discrete Derivative: Forward difference
We begin by trying to build a discrete version of the derivative operator. The
f will be denoted using
f'. The forward difference
of is defined as:
Immediately, we can see that this operator is linear:
it obeys a slightly corrupted version of the chain rule, :
We need this new operator to shift the function's input from to .
§ Falling factorial as polynomials
cool, now that we seem to have a linear derivative operator that behaves
roughly sanely, let's test it out! The first reasonable target is a polynomial,
so let's try :
This is disappointing, it does not behave very well
:( However, there is
an analogue that does well. This is the falling factorial , defined as:
Let's try and apply our discrete difference :
These falling factorials look pretty unnatural though, why do we care?
Well, once we build some integral calculus, we can handle our problem
of using this calculus, by rewriting
in terms of these falling factorials.
§ Sums as discrete integrals
We want to think of as the correct variant of
. The most important property of an integral is
the fundamental theorem of calculus:
we can check if the assertion is true:
Sweet, so we just kicked a theory of calculus of the ground. Let's put
this to some use:
§ Gauss' famous formula from discrete calculus
Let's begin by deriving the closed form for naturals:
Let's now derive the closed form form the sum of squares of :
Trying to perform this process in general does beg a question: how do we
convert from into some combination of rising and falling factorials?
It turns out that Stirling Numbers will show up to aid this conversion.
But before that, let's see some more connections.
§ as the combinatorial version of
We want to find the analogue of the exponential function , which
satisfies the equation . Setting this up in the discrete case:
What does this buy us? It gives us a nice proof that .
It proceeds by taking the taylor of , "combinatorializing it", and then
§ Harmonic series as the combinatorial version of logarithm
In the continuous case, we have that . In the
discrete case, we get , the sum of the
first harmonic numbers. This explains why the harmonic numbers
keep showing up in different places across discrete math --- We're often
trying to integrate some kind of quantity.
This also may tell us that and are somewhat "weak inverses" of each other.
I haven't thought about this weak inverse thing too much.
§ Stirling numbers of the first kind for convering between polynomials and falling factorials
We can express where
are the (yet to be defined) unsigned stirling numbers of the first kind.
(aside: I wonder if this can be derived from some kind of mobius inversion).
We begin my in fact defining the stirling numbers of the first kind,
as the coefficients of the rising factorial:
The question as a combinatorialist is:
what do the unsigned striling numbers of the first kind, , count?
The answer is:
counts the number of permutations of elements with disjoint cycles.
There is a more evocative definition, which goes like this:
counts the number of ways to seat people at circular tables, such that no table is left empty.
For example, in the case of the permutations of the set ,
we have the permutations:
So, this gives the counts:
From the seating people perspective, here's how this goes:
These stirling numbers satisfy a recurrence:
- is the number of ways to seat 3 people at 1 table. The first person sits at the table in only one way . The second person can sit to the left or to the right of the first person, but this is symmetric: they too have only one way . Now the third person can sit to the left of the first person or to the left of the second person. So there are two ways . In total, there are only two ways. Key idea: On a circular table, it only matters who is to your left, since there is no difference between left and right. The second person has two choices: they
- is the number of ways to seat 3 people at 3 tables so that no table is empty. We are forced to place one person per table.
- is the number of ways to seat 3 people at 2 tables so that no table is empty. So we will need to have two people on the first table, and then the final personal on the second table. Once we pick which two people sit together in the first table, we are done, because for upto two people, it doesn't matter how they sit at a table, the situation is symmetric.
This can be seen combinatorially. If we want the number permutations of objects
with cycles, we can either:
Another cute fact of the unsigned stirling numbers of the first kind
is that since permutations are partitioned by their number of cycles, we have:
- Take the permutations of objects with cycles, , and then insert the new th object into a new cycle all by itself. That is, we create a new permutation where .
- Take the permutation of objects with cycles, and insert this new th object into any of the cycles. If the original permutation had
x -p-> y, we can insert this new object as
x -p-> * -p->y for any
x. Thus, there are choices of locations to inser
* --- as the image of all possible
xs. This gives us the term.