danielz.fyi

Falling factorials

Properties1
descriptionSome notes on an interesting combinatorial operation.

4 min read

The falling factorial (𝑛)𝑘 is defined as

𝑛(𝑛−1)(𝑛−2)…(𝑛−𝑘+1)

When 𝑛 is a non-negative integer, we can interpret (𝑛)𝑘 combinatorially as the number of ways to select and order 𝑘 elements from an 𝑛-element set. For instance, when 𝑛=3 and 𝑘=2, we have (3)2=6 ways to select and order two elements from {1,2,3}:

  1. [1,2]
  2. [2,1]
  3. [1,3]
  4. [3,1]
  5. [2,3]
  6. [3,2]

Discrete calculus

Falling factorials (𝑛)𝑘 provide a nice discrete analogue to the power functions 𝑥𝑘. In particular, consider the difference

Δ(𝑛)𝑘=(𝑛+1)𝑘−(𝑛)𝑘=(𝑛+1𝑛−𝑘+1−1)(𝑛)𝑘=𝑘𝑛−𝑘+1⋅(𝑛)𝑘=𝑘⋅(𝑛)𝑘−1,

just like how

dd𝑥𝑥𝑘=𝑘𝑥𝑘−1.

We can also interpret the identity

(𝑛+1)𝑘−(𝑛)𝑘=𝑘⋅(𝑛)𝑘−1

from a combinatorial perspective. If we have (𝑛+1) balls, (𝑛+1)𝑘 denotes the number of ways to select and permute 𝑘 of them, while (𝑛)𝑘 represents the same quantity but restricted only to the first 𝑛 balls. Therefore, the selections that are included by the former but not the latter are precisely those that include the (𝑛+1)st ball.

To count the number of selections that contain the (𝑛+1)st ball, we note that we may first select and order 𝑘−1 other balls among the first 𝑛, then place the (𝑛+1)st ball at any position among them. This results in (𝑛)𝑘−1⋅𝑘 ways, as desired.

Stirling numbers

Problem 1
How can we express 𝑛𝑘 as a weighted sum of falling factorials (𝑛)𝑘,(𝑛)𝑘−1,…,(𝑛)1?

For instance, we may express 𝑛2=(𝑛)2+(𝑛)1 or 𝑛3=(𝑛)3+3(𝑛)2+(𝑛)1, but how does this generalize?

Again, we offer a combinatorial interpretation. Imagine 𝑛𝑘 as the number of ways to assign each label from 1 to 𝑘 to exactly one of 𝑛 balls; one ball could be labelled multiple times or not at all.

We now decompose 𝑛𝑘 into cases based on how many balls have at least one label. For instance, when 𝑘=3:

  1. If we want all balls labelled, there are exactly (𝑛)𝑘=(𝑛)3 ways by definition.
  2. If we want two balls labelled, we may first pick and order the balls in (𝑛)2 ways. We must then distribute the 3 labels into 2 indistinguishable, non-empty sets, and the number of ways to do this is precisely the Sterling number 𝑆(𝑛,2). Thus, the number of labellings that lead to exactly 2 labelled balls is (𝑛)2⋅𝑆(3,2).
  3. By the same logic, there are exactly (𝑛)3⋅𝑆(3,3) ways to label 3 distinct balls.

So in general, we have that

𝑛𝑘=(𝑛)𝑘⋅𝑆(𝑘,𝑘)+(𝑛)𝑘−1⋅𝑆(𝑘,𝑘−1)+(𝑛)𝑘−2⋅𝑆(𝑘,𝑘−2)+…+(𝑛)1⋅𝑆(𝑘,1)=∑𝑘𝑖=1(𝑛)𝑖⋅𝑆(𝑘,𝑖)
Problem 2
Four people each call one of four technicians, independently and uniformly at random. What’s theprobability that exactly 𝑖 distinct technicians are called, for 𝑖=1,2,3,4?

We decompose

44=𝑆(4,4)⋅(4)4+𝑆(4,3)⋅(4)3+𝑆(4,2)⋅(4)2+𝑆(4,1)⋅(4)1=(4)4+6⋅(4)3+7⋅(4)2+(4)1

Note that per our argument above, each of these summands correspond to one of our desired cases:

  • There are (4)4=24 ways for 𝑖=4 technicians to be called.
  • There are 6⋅(4)3=144 ways for 𝑖=3 technicians to be called.
  • There are 7⋅(4)2=84 ways for 𝑖=2 technicians to be called.
  • There are (4)1=4 ways for 𝑖=1 technician to be called.

Graph View

Backlinks