Combinatorial Math Study Notes

Better reading experience

update

2024-11-12 11:25 Fixed some formatting errors and added binomial inversion examples

2024-11-12 14:33 Improved proof of binomial inversion

basics

I. Principle of addition

Completing a job has$n$ Type of approach, paragraph$i$ The types of approaches are$a_i$ The number of scenarios to accomplish this work is$\sum\limits _{i=1}^n a_i$ Kind.

II. Principle of multiplication

Completing a job has$n$ Steps, No.$i$ The steps are$b_i$ The number of scenarios to accomplish this work is$\prod\limits _{i=1}^n b_i$ Kind.

Permutation and combination (basic)

I. Definitions

1. Number of arrangements: from$n$ Selection of objects$m$ The number of programs in which the objects are arranged in a column in a certain order is given by the$A_n ^m\ ($maybe$P_n^m)$ said.
$A_n^m=\dfrac{n!}{(n-m)!}$。

2. Number of combinations: from$n$ Selection of objects$m$ The number of programs for the objects (regardless of order), using the$\begin{pmatrix} n \\ m \end{pmatrix}$(or$C_n^m$) indicates that$\dbinom{n}{m}=\dfrac{A_n^m}{m!}=\dfrac{n!}{m!(n-m)!}$。

3. Plug-in method

currently available$n$ classifier for individual things or people, general, catch-all classifieridenticalThe elements of the requirement to classify them into$k$ Group.

Ensure that each groupAt least one elementHow many ways are there to divide it?

consider taking$k - 1$ The boards are inserted into the$n$ The elements are formed two by two$n - 1$ inside an empty space. Since the elements are identical, the answer is$\dbinom{n - 1}{k - 1}$。

The essence is to seek$x_1+x_2+\cdots+x_k=n$ The number of sets of positive integer solutions to the

each groupAllowed to be emptyHow many ways are there to divide it?

Add to the overall first$k$ to ensure that at least one of each group, the next treatment is the same as above, and the final equivalent of each group minus one to return it can be. The answer is$\dbinom{n+k-1}{k-1}$. Because.$\dbinom{n}{m}=\dbinom{n}{n-m}$The answer is$\dbinom{n+k-1}{n}$。

The essence is to seek$x_1+x_2+\cdots+x_k=n$ The number of groups of non-negative integer solutions of the

For the first$i$ Group.At least a share.$a_i$ classifier for individual things or people, general, catch-all classifier（$\sum\limits a_i\le n$), how many divisions are there?

The essence is to seek$x_1+x_2+\cdots+x_k=n$ The number of groups of integer solutions to the

Mimicking the third case, we set$x'_i=x_i-a_i$ to ensure that each group receives a minimum of$a_i$ One. Now it is equivalent to asking$x'_1+x'_2+\cdots+x'_k=n$ The integer solution of the

Process:

\[x'_1+x'_2+\cdots+x'_k=n \]

\[(x'_1+a_1)+(x'_2+a_2)+\cdots+(x'_k+a_k)=n \]

\[x_1+x_2+\cdots+x_k=n-a_1-a_2-\cdots-a_k \]

\[x_1+x_2+\cdots+x_k=n-\sum a_i \]

So the answer is$\dbinom{n-\sum a_i+k-1}{n-\sum a_i}$。

Example:$\ \ 1 \sim n$ these$n$ choose from a list of natural numbers$k$ The number of people who have made this$k$ The combinations of numbers in which no two numbers are adjacent to each other are$\dbinom {n-k+1}{k}$ Kind.

Proof: let the chosen$k$ The numbers were$x_1,x_2,\cdots,x_k (x_1\le x_2\le \cdots \le x_k)$set up$x'_i=x_i+i-1$then there must be$x'_1<x'_2<\cdots<x'_k\ \ (x'_k\le n)$, i.e., neither is adjacent to the other. Because$x'_k=x_k+k-1\le n$So.$x_k\le n-k+1$We just need to add a new section to the$1\sim n-k+1$ get a position by passing the imperial exam$k$ The answer is$\dbinom{n-k+1}{k}$ Kind.

the Binomial Theorem (math.)

element

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

show that

Use of mathematical induction.

Understand a quotation first:Pascal's Law, ie:

\[\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k} \]

Proof of Pascal's Law: assume that there is$n+1$ Individuals to be selected among$k$ Individuals, it's clear that the program has$\dbinom{n+1}{k}$ species; but unfortunately, the total number of$n+1$ One of us is dead, and now we're down to one.$n$ people, but it's still a good idea to pick$k$ Number of programs is now$\dbinom{n}{k-1}$ species; the number of scenarios we find missing must be related to the one that died, and then the number of scenarios we are missing is in the selection of the species of$k$ There's that dead guy in the personal, so we can still make our own choices.$k-1$ people, so the number of programs missing is$\dbinom{n}{k-1}$. So there we have it:

\[\dbinom{n+1}{k}-\dbinom{n}{k-1}=\dbinom{n}{k} \]

Switching down the order gets:

\[\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k} \]

Get the proof.

Now prove the binomial theorem.

(coll.) fail (a student)$n=1$ The original equation clearly holds when

Suppose that when$n=k$ When the original equation holds, let$n=k+1$：

\[(a+b)^{k+1}=a(a+b)^k+b(a+b)^k \]

\[=a\sum_{i=0}^k\dbinom{k}{i}a^{k-i}b^i+b\sum_{j=0}^k\dbinom{k}{j}a^{k-j}b^j \]

commander-in-chief (military)$a,b$ Ride in:

\[=\sum_{i=0}^k\dbinom{k}{i}a^{k-i+1}b^i+\sum_{j=0}^k\dbinom{k}{j}a^{k-j}b^{j+1} \]

Put the first half$i=1$ Presented at the time:

\[=a^{k+1}+\sum_{i=1}^k\dbinom{k}{i}a^{k-i}b^i+\sum_{j=0}^k\dbinom{k}{j}a^{k-j}b^{j+1} \]

commander-in-chief (military)$j$ create$i-1$:

\[=a^{k+1}+\sum_{i=1}^k\dbinom{k}{i}a^{k-i}b^i+\sum_{i=1}^{k+1}\dbinom{k}{i-1}a^{k-i+1}b^{i} \]

Take the second half.$i=k+1$ Presented at the time:

\[=a^{k+1}+\sum_{i=1}^k\dbinom{k}{i}a^{k-i}b^i+\sum_{i=1}^{k}\dbinom{k}{i-1}a^{k-i+1}b^{i}+b^{k+1} \]

Combine the two middle sums:

\[=a^{k+1}+b^{k+1}+\sum_{i=1}^k\left[\dbinom{k}{i}+\dbinom{k}{i-1}\right]a^{k-i}b^i \]

cribPascal's Law：

\[=a^{k+1}+b^{k+1}+\sum_{i=1}^k\dbinom{k+1}{i}a^{k-i}b^i \]

\[=\sum_{i=0}^{k+1}\dbinom{k+1}{i}a^{k-i}b^i \]

that's why when$n=k+1$ when the conclusion still holds. Thus for any$n\in \mathbb{N} ^{+}$and all of them can make the equation proved to be valid.
Get the proof.

Pigeon nest principle (drawer principle)

element

commander-in-chief (military)$n$ objects, divided into$k$ group, then there exists at least one subgroup containing a grouping greater than or equal to$\left \lceil \dfrac{n}{k} \right \rceil$ An item.

show that

Counterfactual.

Let each grouping contain less than$\left \lceil \dfrac{n}{k} \right \rceil$ objects, the sum of the$S\leq (\left \lceil \dfrac{n}{k} \right \rceil -1 ) \times k=k\left\lceil \dfrac{n}{k} \right\rceil-k < k(\dfrac{n}{k}+1)-k=n$ , contradiction.

the tolerant repulsion principle (physics)

element

found$U$ The elements in$n$ different properties, and the first$i$ A property is called$P_i$Possesses attributes$P_i$ of the elements of a set$S_i$So.

\[\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| \]

show that

Math induction, too lazy to write to fill in the holes later ()

Kirtland number (math.)

define

Defining the Catalan number$H_n$ denotes the distance on the coordinate axis from$(0,0)$ check on sth$(n,n)$ does not cross a straight line in the path of$y=x$ of the number of paths. The following figure shows an illegitimate scheme.

seek the law

As follows, it is possible for each illegal scheme to be used by putting in the first crossing of the$y=x$ The path after the point of the$y=x+1$ Make a symmetry thus constructing a self$(0,0)$ until$(n-1,n+1)$ The path.

Because there's a total of$2n$ Steps, so from$(0,0)$ until (a time)$(n,n)$ The total number of programs with$\dbinom{2n}{n}$ Species, from$(0,0)$ until (a time)$(n-1,n+1)$ The number of programs is$\dbinom{2n}{n-1}$ Kind.

In summary:

\[\begin{aligned} H_n&=\dbinom{2n}{n}-\dbinom{2n}{n-1}\\ &=\frac{(2n)!}{(n!)^2}-\frac{(2n)!}{(n+1)!(n-1)!}\\ &=\frac{(n+1)(2n)!}{n!(n+1)!}-\frac{n(2n)!}{n!(n+1)!}\\ &=\frac{(2n)!}{n!(n+1)!}\\ &=\frac{\dbinom{2n}{n}}{n+1}\\ \end{aligned}\]

recurrence formula

\[H_n = \sum_{i=0}^{n-1}H_iH_{n-i-1} \]

\[H_n = \frac{4n-2}{n+1}H_{n-1} \]

Proof:$(0,0)$ until (a time)$(n,n)$ The path can be divided into the following steps:

through (a gap)$(0,0)$ walk$(i,i)$The number of programs is$H_i$。
through (a gap)$(i,i)$ walk$(n-1,n-1)$The number of programs is$H_{n-i-1}$。
through (a gap)$(n-1,n-1)$ walk$(n,n)$The number of programs is$1$。

Enumerate each$i$The result is$H_n = \sum_{i=0}^{n-1}H_iH_{n-i-1}$。

\[\begin{aligned} & H_n = \frac{4n-2}{n+1}H_{n-1} \\ \iff & \frac{C_{2n}^n}{n+1} = \frac{4n-2}{n+1} \times \frac{C_{2n-2}^{n-1}}{n} \\ \iff & \frac{(2n)!}{(n+1)(n!)^2} = \frac{4n-2}{n+1} \times \frac{(2n-2)!}{n(n-1)!^2} \\ \iff & \frac{(2n)!}{n} = (4n-2) \times {(2n-2)!} \\ \iff & \frac{(2n)(2n-1)}{n} = 4n-2 \\ \iff & 4n-2 = 4n-2 \\ \end{aligned} \]

Therefore, the evidence is obtained.

combinatorial number property

Property 1

\[\dbinom{n}{m}=\dbinom{n}{n-m} \]

show that

Correctness is obviously understood in a combinatorial number sense in the sense of$n$ choose from among$m$ The equivalent of one in the$n$ the pick of the bunch$n-m$ One not selected.

Property 2

\[\dbinom{n}{m}=\dfrac{n}{m}\dbinom{n-1}{m-1} \]

show that

\[\begin{aligned} \dbinom{n}{m}&=\dfrac{n!}{m!(n-m)!}\\ &=\dfrac{n}{m}\times \dfrac{(n-1)!}{(m-1)!(n-m)!}\\ &=\dfrac{n}{m}\dbinom{n-1}{m-1} \end{aligned}\]

Property 3

\[\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1} \]

show that

That is, a slight transformation of Pascal's theorem, see above.

Property 4

\[\sum_{i=0}^{n}\dbinom{n}{i}=2^n \]

show that

commander-in-chief (military)$a=b=1$ Just bring in the binomial theorem.

\[\begin{aligned} 2^n&=(1+1)^n\\ &=\sum_{i=0}^n\dbinom{n}{i}1^{n-i}1^i\\ &=\sum_{i=0}^n\dbinom{n}{i} \end{aligned}\]

Property 5

\[\sum_{i=0}^{n}(-1)^i\dbinom{n}{i}=[n=0] \]

$[a]$ denote$a$ The answer when true is$1$otherwise$0$(Equivalent to abool）。

show that

Evidence is basically equivalent to nature$4$will$a=1,b=-1$ Just bring in the binomial theorem.

We believe here that$0^0=1$So.$n=0$ When the answer is$1$。

Specific proofs are omitted.

Property 6

\[\sum_{i=0}^{m}\dbinom{n}{i}\dbinom{m}{m-i}=\dbinom{n+m}{m}\tag{$n\ge m$} \]

show that

Consider understanding by combining number meanings.

Suppose that there are now$n$ Boys.$m$ A girl. We're going to start with this now.$n+m$ Individuals selected from$m$ individuals, the number of programs is clearly$\dbinom{n+m}{m}$.. Another way to think about it is to choose from the boys$i$ Selection of girls$m-i$ For each of the$i$ The number of programs is$\dbinom{n}{i}\dbinom{m}{m-i}$enumerate each$i$ That is the total number of programs.

Property 7

\[\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n} \]

show that

characteristic$6$ The special case of taking$m=n$ Ready to go.

Property 8

\[\sum_{i=0}^{n}i\dbinom{n}{i}=n2^{n-1} \]

show that

\[\begin{aligned} \sum_{i=1}^{n}i\dbinom{n}{i}&=n\cdot\sum_{i=1}^{n}\dfrac{i}{n}\dbinom{n}{i}\\ &=n\cdot\sum_{i=1}^{n}\dbinom{n-1}{i-1}\text{(applying property 2)}\\\\\\ &=n2^{n-1}\text{(applying property 4)}\\\\\ \end{aligned}\]

Property 9

\[\begin{aligned} \sum_{i=1}^{n}i^2\dbinom{n}{i}&=n(n+1)2^{n-2} \end{aligned}\]

show that

\[\begin{aligned} \sum_{i=1}^{n}i^2\dbinom{n}{i}&=n\cdot\sum_{i=1}^n\dfrac{i}{n}\dbinom{n}{i}\cdot i\\ &=n\cdot\sum_{i=1}^{n}i\dbinom{n-1}{i-1}\\ &=n\cdot\sum_{i=0}^{n-1}(i+1)\dbinom{n-1}{i}\\ &=n\cdot\sum_{i=0}^{n-1}i\dbinom{n-1}{i}+n\cdot\sum_{i=0}^{n-1}\dbinom{n-1}{i}\\ &=n\cdot\sum_{i=0}^{n-1}i\dbinom{n-1}{i}+n2^{n-1}\\ &=n(n-1)\cdot\sum_{i=0}^{n-1}\dfrac{i}{n-1}\dbinom{n-1}{i}+n2^{n-1}\\ &=n(n-1)\cdot\sum_{i=1}^{n-1}\dbinom{n-2}{i-1}+n2^{n-1}\\ &=n(n-1)2^{n-2}+n2^{n-1}\\ &=n(n+1)2^{n-2} \end{aligned}\]

Expansion: Proof of $$\begin{aligned}
\sum_{i=1}^{n}im\dbinom{n}{i}&=n^{{\overline{m}}2}
\end{aligned}$$。

Nature 10:

\[\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k} \]

show that

\[\begin{aligned} \binom{n}{r}\binom{r}{k} &= \dfrac{n!}{r!(n-r)!}\cdot\dfrac{r!}{k!(r-k)!}\\ &= \dfrac{n!}{(n-r)!\cdot k!\cdot(r-k)!}\\ &= \dfrac{n!(n-k)!}{(n-r)!\cdot k!\cdot (r-k)!\cdot(n-k)!}\\ &=\dfrac{n!}{k!(n-k)!}\cdot \dfrac{(n-k)!}{(r-k)!(n-r)!}\\ &=\dbinom{n}{k}\dbinom{n-k}{r-k} \end{aligned}\]

binomial inversion (math.)

element

Form 1

\[F_n=\sum_{i=0}^{n}(-1)^i{n\choose i}G_i \iff G_n=\sum_{i=0}^{n}(-1)^{i}{n\choose i}F_i \]

Form 2

\[F_n=\sum_{i=0}^{n}{n\choose i}G_i \iff G_n=\sum_{i=0}^{n}(-1)^{n-i}{n\choose i}F_i \]

show that

The form of form 1 is found to be symmetric, then we set an inversion factor.

Given a matrix$A_{n,i}=(-1)^i\begin{pmatrix} n \\ i \end{pmatrix}$, which now becomes a proof $$F_n=\sum_{i=0}^{n}A_{n,i}G_i \iff G_n=\sum_{i=0}^{n}A_{n,i}F_i$$, i.e., a proof that$A*A=I$。

\[\begin{aligned} (A*A)_{n,m}&=\sum_{t=1}^{\infty}{A_{n,t}}{A_{t,m}}\\ &=\sum_{t=m}^{n}(-1)^t{n \choose t}(-1)^m{t \choose m}\\ &=(-1)^m\sum_{t=m}^{n}(-1)^t{n \choose t}{t \choose m}\\ &=(-1)^m\sum_{t=m}^{n}(-1)^t(\dfrac{n!}{t!\times (n-t)!}\cdot\dfrac{t!}{m!\times (t-m)!})\\ &=(-1)^m\sum_{t=m}^{n}(-1)^t{n \choose m}{n-m \choose n-t}\\ &=(-1)^m{n \choose m}\sum_{t=m}^{n}(-1)^t{n-m \choose n-t}\\ &=(-1)^m{n \choose m}\sum_{t=0}^{n-m}(-1)^{t+m}+{n-m \choose n-t-m}\\ &=(-1)^{2m}{n \choose m}\sum_{t=0}^{n-m}(-1)^t+{n-m \choose t}\\ \end{aligned}\]

The latter piece is found to be the Binomial Theorem, so the original equation can be reduced to:

\[(-1)^{2m}{n \choose m}(1-1)^{n-m} \]

On closer inspection, this formula is only available in$n=m$ time value is$1$The rest of the time is$0$namely$[n=m]$which is the unit matrix$I$。

from this, it can be concluded that$A*A=I$ i.e. matrix (math.)$A$ self-reversing, thus yielding a proof of form I, while form II is obtained by moving the$-1$ can be deduced from the powers of the

example

CF997C Sky Full of Stars

even thoughCodeforces The question bank blew up, but it doesn't detract from the fact that this is a great question that can be used to practice binomial inverses (I think it can also be done with the principle of capacitated repulsion?). ..

Set up, we set up$F_{i,j}$ because of(say the) least there are$i$ classifier for objects in rows such as words$j$ The number of schemes with the same color in the column.$G_{i,j}$ because ofas it turns out there are$i$ classifier for objects in rows such as words$j$ The number of schemes with the same color in the column. Obviously, we have:

\[F_{x,y}=\sum_{i=x}^n\sum_{j=y}^n {n\choose i}{n\choose j}G_{i,j} \]

Found this.two-dimensional binomial inversion (math.) of classical formulas, which are obtained by inversion:

\[G_{x,y}=\sum_{i=x}^n\sum_{j=y}^n (-1)^{n-i}{n\choose i}(-1)^{n-j}{n\choose j}F_{i,j} \]

\[G_{x,y}=(-1)^{2n}\sum_{i=x}^n\sum_{j=y}^n (-1)^{i+j}{n\choose i}{n\choose j}F_{i,j} \]

And the answer we are asking for is the total number of programs$3^{n^2}-G_{0,0}$The problem is then transformed into finding the$F$, discussed next in categories.

(coll.) fail (a student)$ij \ne 0$ When, rows and columns of the same color must cross, so all rows and columns are of one color and the number of schemes is${n\choose i}{n\choose j}3^{(n-i)(n-j)+1}$。
(coll.) fail (a student)$ij = 0,i+j \ne 0$ When, rows and columns of the same color must cross, so all rows and columns are of one color and the number of schemes is${n\choose i+j}3^{i+j+(n-i-j)n}$。
(coll.) fail (a student)$i+j = 0$ When unlimited, the number of programs is$3^{n^2}$。

particle marking the following noun as a direct object$F$ Take it back and figure it out.$G_{0,0}$ Simply subtract one from the full program count.