Binomial Inversion Study Notes

preamble

Ten thousand words long! Here are some of my thoughts and insights, the tutorials on the internet are too scribbled.

besidesA new inversion formula was found！

summarize

Binomial inversion is used to transform two functions with a special relationship\(f\) respond in singing\(g\), thus facilitating the solution of the problem. In general, direct computation satisfies exactly\(n\) The answer to the limit is not easy to find, but it can be calculated that "at least" / "at most" satisfy\(n\) The answer to the restriction, using binomial inversion, is to find the answer that "exactly" satisfies\(n\) A restricted answer.

Those who want to read the conclusion directly canPoke me.。

Proof & Derivation

Some introductory reasoning

quotation marks\(1\): Binomial Theorem

The ordinary binomial theorem is:

\[\large (a + b) ^ n = \sum _ {i = 0} ^ n \binom{n}{i} a^i b^{n-i} \]

The proof can be done by mathematical induction without expansion. This article mainly utilizes\(a = -1, b = 1\) The special circumstances of the case, i.e:

\[\begin{aligned} & \quad \ \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i \\ &= \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i 1^{n-i} \\ &= \Big (1 + (-1) \Big )^n \\ &= 0 ^ n \end{aligned} \]

Noting that when\(n = 0\) of the time, it makes no sense. Observing the original equation reveals that at this point\(\dbinom{0}{0} (-1)^0 = 1\). So there we have it:

\[\large \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i = [n = 0] \]

quotation marks\(2\): Multi-step tolerance

sign\(S_i\)（\(1 \leq i \leq n\)) denotes a set, we have:

\[\large \left \vert \bigcup_{i = 1}^{n} S_i \right \vert = \sum _ {1 \leq i \leq n} \Big \vert S_i \Big \vert - \sum _ {1 \leq i \lt j \leq n} \Big \vert S_i \cap S_j \Big \vert + \cdots + (-1) ^ {n - 1} \Bigg \vert \bigcap _ {i = 1} ^ n S_i \Bigg \vert \]

To wit:

\[\large \left \vert \bigcup_{i = 1}^{n} S_i \right \vert = \sum _ {m = 1} ^ n (-1) ^ {m - 1} \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \]

Proving this equation is equivalent to proving that\(\forall x \in \bigcup \limits_{i = 1}^{n} S_i\)It's on the right.\(\sum \limits _ {a_i < a_{i + 1}} \Bigg \vert \bigcap \limits _ {i = 1} ^ m S_{a_i} \Bigg \vert\) The sum of the calculated coefficients is\(1\). Remember that all of the items that contain\(x\) The set of\(T_1, \ldots, T_m\)（\(m \neq 0\)), then there is:

\[\begin{aligned} & \quad \ \Big \vert \{ T_i \mid 1 \leq i \leq m \} \Big \vert - \Big \vert \{ T_i \cap T_j \mid 1 \leq i \lt j \leq m \} \Big \vert + \cdots \\ &= \binom{m}{1} - \binom{m}{2} + \cdots + \cdots (-1) ^ {m - 1} \binom{m}{m} \\ &= \sum _ {i = 1} ^ {m} (-1)^{i - 1} \binom{m}{i} \\ &= - \sum _ {i = 1} ^ {m} (-1)^i \binom{m}{i} \\ &= \binom{m}{0} - \sum _ {i = 1} ^ {m} (-1)^i \binom{m}{i} \\ &= 1 - [m = 0] \\ &= 1 \end{aligned} \]

Therefore, it is established.

quotation marks\(3\): Number of combinations

We consider the transformation\(\dbinom{n}{i} \dbinom{i}{j}\). Its combinatorial significance is that\(n\) Choose one of the small balls\(i\) One, and then from the\(i\) Select from among\(j\) of the number of programs. We can also start with the\(n\) Select from among\(j\) and then from the remaining\(n - j\) choose from among\(i - j\) Individuals. Expressed as:

\[\dbinom{n}{i} \dbinom{i}{j} = \binom{n}{j} \binom{n - j}{i - j} \]

And of course it can be proved algebraically:

\[\begin{aligned} \dbinom{n}{i} \dbinom{i}{j} &= \frac{n!}{i! (n-i)!} \frac{i!}{j! (i-j)!} \\ &= \frac{n!}{(n - i)! (i - j)! j!} \\ &= \frac{n! (n - j)!}{(n - i)! (i - j)! (n - j)! j!} \\ &= \frac{n!}{j! (n - j)!} \frac{(n - j)!}{(n - i)! \Big ((n - j) - (n - i) \Big)!} \\ &= \binom{n}{j} \binom{n - j}{i - j} \end{aligned} \]

quotation marks\(4\)：\(-1\) idempotent characterization of

\((-1) ^ {a + b} = (-1) ^ {a - b}\)It's not a problem. What's the point of proving it?

\[\begin{aligned} 2b &\equiv 0 & \pmod {2} \\ b &\equiv -b & \pmod {2} \\ a + b &\equiv a - b & \pmod {2} \end{aligned} \]

mould\(0\)

\[\large f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i) \]

tolerance tolerance proof

may wish to remember\(\overline{S_i}\) indicate\(S_i\) The complementary set, there:

\[\begin{aligned} \left \vert \bigcap_{i = 1}^{n} \overline{S_i} \right \vert &= \left \vert \bigcup_{i = 1}^{n} S_i \right \vert - \left \vert \bigcup_{i = 1}^{n} \overline{S_i} \right \vert \\ &= \left \vert \bigcup_{i = 1}^{n} S_i \right \vert - \sum _ {m = 1} ^ n (-1) ^ {m - 1} \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\ &= \left \vert \bigcup_{i = 1}^{n} S_i \right \vert + \sum _ {m = 1} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\ &= \sum _ {m = 0} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\ \end{aligned} \]

due to\(\overline{\ \overline{S_i}\ } = S_i\), so getting a similar eq:

\[\left \vert \bigcap_{i = 1}^{n} S_i \right \vert = \sum _ {m = 0} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m \overline{S_{a_i}} \Bigg \vert \]

The form is found to be very similar, but one step short of construction. Let's assume that we are able to early out a set of\(S_i\)such that any\(k\) The intersection of the sets is equal in size.

may wish to remember\(f(x)\) denote any\(x\) The size of the intersection of the complementary sets, for the original set the same notation\(g(x)\), the above equations can be rewritten as respectively:

\[f(n) = \sum _ {i = 0} ^ n (-1) ^ i \binom{n}{i} g(i) \]

\[g(n) = \sum _ {i = 0} ^ n (-1) ^ i \binom{n}{i} f(i) \]

I.e., evidence.

algebraic proof

Tolerance is more abstract, try an algebraic proof. We put\(g\) bring to\(f\) Go in and get:

\[\begin{aligned} f(x) &= \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} \sum _ {j = 0} ^ i (-1) ^ j \binom{i}{j} f(j) \\ &= \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{j}{i} \binom{x}{j} \\ &= \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x}{i} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ {2i + j} \binom{x - i}{j} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ j \binom{x - i}{j} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) [x - i = 0] \\ &= f(x) \end{aligned} \]

I.e., evidence.

mould\(1\)"at least"\(\Leftrightarrow\) "As it happens."

\[\large f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(i) \]

Consider practical implications in order to solve real problems. Consider having\(n\) limitations.\(f(x)\) means that at least one of them satisfies\(x\) limitations.\(g(x)\) means that it satisfies exactly\(x\) Limitations.

Noting that.\(f\) It's not that simple.\(g\) of the prefix sum, as it will be counted repeatedly.

\(g(x)\) that is, our answer, and the\(f(x)\) It is the result that we have derived by other algorithms.

Typically, we would admire\(x\) The restriction must be satisfied, and the remaining restrictions may or may not be satisfied, so that the restriction can be solved without having to think about the restriction\(f\)。

Consider how to use\(g\) express\(f\). There are two ways of thinking about it:

We consider begging for\(g(x)\) The process of The initial order\(g(x) \gets f(x)\), which is clearly not true. Let's consider a\(i > x\)，\(g(i)\) exist\(f(x)\) The number of contributions is\(\dbinom{i}{x}\)So get on with it:

\[g(x) = f(x) - \sum _ {i = x + 1} ^ n \binom{i}{x} g(i) \]

It's there when you move the item:

\[\begin{aligned} f(x) &= g(x) + \sum _ {i = x + 1} ^ n \binom{i}{x} g(i) \\ &= \sum _ {i = x} ^ n \binom{i}{x} g(i) \end{aligned} \]
A more direct way of thinking about this is that we consider enumerating the chimera\(x\) After the limitations must be met, there are\(i - x\) limit is also satisfied, i.e., a total of\(i\) limitations are satisfied, where either\(x\) All of them can be counted, multiplied by\(\dbinom{i}{x}\) After that, the summation can be done without weight or leakage:

\[f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \]

This is the same equation on the left. Prove that the equation on the right is right by bringing it in.

\[\begin{aligned} f(x) &= \sum _ {i = x} ^ n \binom{i}{x} \sum _ {j = i} ^ n (-1)^{j - i} \binom{j}{i} f(j) \\ &= \sum _ {i = x} ^ n f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{j}{x} \binom{i}{j} \\ &= \sum _ {i = x} ^ n f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{i}{x} \binom{i - x}{j - x} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{i - x}{j - x} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = 0} ^ {i - x} (-1) ^ {i - (j + x)} \binom{i - x}{j} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = 0} ^ {i - x} (-1) ^ {i - x - j} \binom{i - x}{j} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) [i - x = 0] \\ &= f(x) \end{aligned} \]

I.e., evidence.

mould\(2\): "up to"\(\Leftrightarrow\) "As it happens."

\[\large f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \Leftrightarrow g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i) \]

Of course we can just use the model\(1\) way to push the equation. Remember\(f(x)\) Indicates that up to meet\(x\) programs that are limited in number.\(g(x)\) Indicates just right.

first with\(g\) express\(f\)This can be enumerated and recognized.\(i \leq x\) limits, and finally summed to yield:

\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \]

Then take it to\(g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i)\) Center.

\[\begin{aligned} g(x) &= \sum _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} \sum _ {j = 0} ^ i \binom{i}{j} g(j) \\ &= \sum _ {i = 0} ^ x g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x}{j} \binom{j}{i} \\ &= \sum _ {i = 0} ^ x g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x}{i} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = 0} ^ {x - i} \binom{x - i}{j} (-1) ^ {x - (j + i)} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = 0} ^ {x - i} \binom{x - i}{j} (-1) ^ {x - i - j} 1 ^ {j} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) [x - i = 0] \\ &= g(x) \end{aligned} \]

Get the proof.

Of course, without considering the practical implications of the problem, the use of models\(0\) can also be proved. Setting\(h(x) = (-1) ^ x g(x)\)There:

\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} h(i) \]

Then there is:

\[g(x) = \frac{h(x)}{(-1) ^ x} = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i) \]

Then:

\[\begin{aligned} h(x) &= \sum _ {i = 0} ^ x (-1) ^ {x + i} \binom{x}{i} f(i) \\ &= \sum _ {i = 0} ^ x (-1) ^ {x - i} \binom{x}{i} f(i) \\ \end{aligned} \]

commander-in-chief (military)\(h\) regarded as propositional in the\(g\)That is to say, the evidence.

More to think about

Noting that "up to the satisfaction\(x\) condition" can be viewed as "at least not satisfying the\(n - x\) conditions"; similarly, "satisfy at least\(x\) The term "at most" can be viewed as "at most".\(n - x\) conditions" can then be deduced from each other to form a new pair of inverse formulas, which I would like to call the forms\(2\)。

mould\(1\)"at least"\(\Leftrightarrow\) "As it happens."

\[\large f(x) = \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \Leftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i) \]

sign\(f(x) = f'(n - x)\), which means that it satisfies at least\(x\) conditions, of which\(f'\) would be consistent with the model\(2\) up. There's\(f'(x) = \sum \limits _ {i = 0} ^ x \dbinom{x}{i} g'(i)\)which\(g'(x)\) means that it does not satisfy exactly\(x\) A condition that is equivalent to\(g(n - x)\), i.e., it satisfies exactly\(n - x\) A condition that can be obtained:

\[\begin{aligned} f(n - x) &= \sum _ {i = 0} ^ x \binom{x}{i} g(n - i) \\ f(x) &= \sum _ {i = 0} ^ {n - x} \binom{n - x}{i} g(n - i) \\ &= \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \\ \end{aligned} \]

due to\(g'(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f'(i)\)So there:

\[\begin{aligned} g(n - x) &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{x}{i} f(n - i) \\ g(x) &= \sum _ {i = 0} ^ {n - x} (-1)^{(n - x) - i} \binom{n - x}{i} f(n - i) \\ &= \sum _ {i = x} ^ n (-1)^{(n - x) - (n - i)} \binom{n - x}{n - i} f(i) \\ &= \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i) \\ \end{aligned} \]

So it stands.

mould\(2\): "up to"\(\Leftrightarrow\) "As it happens."

\[\large f(x) = \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \Leftrightarrow g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i) \]

Similarly, the notation\(f(x) = f'(n - x)\)that indicates that at most the fulfillment of the\(x\) conditions, of which\(f'\) would be consistent with the model\(1\) up. There's\(f'(x) = \sum \limits _ {i = x} ^ n \dbinom{i}{x} g'(i)\)which\(g'(x)\) means that it does not satisfy exactly\(x\) conditions that are equivalent to\(g(n - x)\), i.e., it satisfies exactly\(n - x\) A condition. Available:

\[\begin{aligned} f(n - x) &= \sum \limits _ {i = x} ^ n \dbinom{i}{x} g(n - i) \\ f(x) &= \sum \limits _ {i = n - x} ^ n \dbinom{i}{n - x} g(n - i) \\ &= \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \\ \end{aligned} \]

due to\(g'(x) = \sum \limits_ {i = x} ^ n (-1)^{i - x} \dbinom{i}{x} f'(i)\)So there:

\[\begin{aligned} g(n - x) &= \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(n - i) \\ g(x) &= \sum _ {i = n - x} ^ n (-1)^{i - (n - x)} \binom{i}{n - x} f(n - i) \\ &= \sum _ {i = 0} ^ x (-1)^{(n - i) - (n - x)} \binom{n - i}{n - x} f(i) \\ &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i) \\ \end{aligned} \]

So it stands.

Examples & Exercises

I'll write more when I have time.

reach a verdict

mould\(0\)

\[\Large f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i) \]

mould\(1\)"at least"\(\Leftrightarrow\) "As it happens."

formality\(1\)

\[\Large f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(i) \]

formality\(2\)

\[\Large f(x) = \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \Leftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i) \]

mould\(2\): "up to"\(\Leftrightarrow\) "As it happens."

formality\(1\)

\[\Large f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i) \]

formality\(2\)

\[\Large f(x) = \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i) \]