combination count

Swap the summing order:

$\sum_{i=1}^{n} \sigma_{0}(i)=\sum_{i=1}^{n} \sum_{d \mid i} 1=\sum_{d=1}^{n} \sum_{i=1}^{n}[d \mid i]=\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor $
given sequence$a$, find the interval sum of all its intervals: the answer is $\sum_{i=1}^{n} a_{i} \times i \times(n-i+1) $.

Binomial theorem:

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

Common combinatorial identities:

\[\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \quad(n \geq m \geq k) \]

Start with$n$choose among$m$one, and then selected from$m$Choose from among$k$indivual$\Longleftrightarrow$Start with$n$Choose the final one$k$one, and then from the rest$n-k$Among them, select the one selected in the first step but not selected in the second step.$m-k$indivual.

\[i\binom{n}{i} = n\binom{n-1}{i-1} \]

use$\binom{n}{m}= \frac{n!}{m!(n-m)!}$Expand it to get the proof.

\[\sum_{j=w}^{k} \binom{x}{j} = \sum_{i=1}{x}\binom{i-1}{w-1}\binom{n-i}{k-w} \]

equivalent to starting from$n$elements selected from$k$one, but before$x$elements must be selected at least$w$; this is equivalent to the selected$w$elements are located at$x$Before.

\[\sum_{i=0}^{m} \binom{n+i}{i} = \binom{n+m+1}{n+1} \]

inspection$n+m+1$Yuanji$n+1$The last element of the primitive subset.

\[\sum_{i=0}^{n} \binom{n}{i}\binom{m}{k-i} = \binom{n+m}{k} \]

from$n+m$before selecting elements$k$, before the inspection$n$The number of selected numbers among elements.

Common models:

have$n$kind of goods, no.$i$There are kinds of items$a_i$If we think that the same items are indistinguishable from each other, then we will$\sum a_i$The number of arrangements for each item is

\[\frac{(\sum_{i=1}^n a_i)!}{\prod a_i!} \]

Will$n$identical items are divided into disorderly$m$groups, the number of plans in which each group is non-empty: equivalent to the previous$n-1$Insert into empty slot$m-1$boards, so the number of plans is$\binom{n-1}{m-1}$。

If you do not require each group to be non-empty, consider adding one to each group directly. The number of options is$\binom{n+m-1}{m-1}$。

Find the equation$\sum_{i=1}^m x_i = n, x_i \in \mathbb{Z}, x_i \geq 0$The number of integer solutions of :$\binom{n+m-1}{m-1}$。

If the sequence is given again$y_1...m$,Require$x_i \geq y_i$？
Equivalent to$\sum_{i=1}^m (x_i - y_i) = n - \sum_{i=1}^m y_i$, so the number of plans is$\binom{n+m-\sum_{i=1}^m y_i-1}{m-1}$。

if requested$x_i \leq y_i$Woolen cloth? There are two approaches at this time:

DP：$f(i, j)$before expression$i$The sum of the numbers is$j$Number of scenarios, transfers using prefixes and optimizations.$O(nm)$
Tolerance: imperial decree$S \subseteq \{1, 2, \cdots, m\}$If the restrictions within are not met, the rest will be ignored and converted into requirements.$x_i > y_i$situation.$O(2^m \times \text{poly}(m))$

Find how long it is$2n$legal bracket sequence. The answer is recorded as$C_n$, this is Cattleya's number.

Think of the left bracket as going to the right, and the bracket as going up, then this corresponds to a$(0,0)$arrive$(n,n)$path, and cannot pass through$y=x$(but can be touched).

There are total paths$\binom{2n}{n}$Kind of, consider how to count the number of options that pass through, that is, touch$y=x+1$This straight line.

where we last touched$(p, p+1)$Bundle$(0,0) \rightarrow (p, p+1)$Fold this part over and find that it only corresponds to one$(-1,1) \rightarrow (n,n)$path, so the number of options is$\binom{2n}{n-1}$. So we have the following relationship

\[C_n = \binom{2n}{n} - \binom{2n}{n-1} \]

This is Cattleya's number.

On the other hand, from the perspective of the bracket sequence, we can also give another recursive formula: enumerate the position of the right bracket matched by the first left bracket as$2k$,have

\[C_n = \sum_{k=1}^{n} C_{k-1} C_{n-k} \]

in$C_0 = 1$。

Cattleya number$C_n$Commonly used routines

When the diagonals do not intersect, a$n$The number of ways to divide a convex polygon area with strip edges into triangular areas, that is, the number of triangulation schemes.
A size of$n$stack, push them into the stack one by one$1, 2, \cdots, n$, but it can be popped out of the stack at any time. How many pop-out sequences are there?
$n$The number of unlabeled rooted binary trees with nodes.