1 Permutation and combination

1.1 array

\[A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}
\]

Definition ： from n The choice is m An ordered sequence of numbers , The number of different series .
explain ： from n Choose one of them , Yes n Seed selection , Choose the second , from n-1 Choose from , Yes n-1 Seed selection , And so on , Mathematical combination of basis Multiplication principle So the formula is $n(n-1)(n-2)...(n-m+1)$.

1.2 Combine

\[C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}
\]

Definition ： from n individual Choose from m Of which , The number of different sets .
explain ： The case of removing selected repeating elements from the arrangement is combination , such as {1,2,3}、{2,3,1} identical , So the formula is $ \frac{A_n^m}{A_mm}$, From n individual Selected from m individual , Remove after arrangement m Number of full permutations .
in addition ：$C_n^m$ Another way of writing is ： $\binom{n}{m}$, pronounce as n choose m.
inference ：
1. $\binom{n}{m}+\binom{n}{m-1}=\binom{m+1}{i}$ ,( Also called Pascal's law ), It is easy to prove after entering the formula and reducing points .

binomial theorem

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

prove ：

\[ When n=1 when ,a+b= \sum_{i=0}^1\binom{1}{i}a^{1-i}b^i=\binom{1}{0}a^1b^0+\binom{1}{1}a^0b^1=a+b , The formula holds
\]

\[ hypothesis n=m The time formula holds , set up n=m+1, Then there are ：
\]

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

\[= a\sum_{i=0}^m\binom{m}{i}a^{m-i}b^i+b\sum_{j=0}^m\binom{m}{j}a^{m-j}b^j
\]

\[= \sum_{i=0}^m\binom{m}{i}a^{m+1-i}b^i+\sum_{j=0}^m\binom{m}{j}a^{m-j}b^{j+1}, Propose when i=0 When and when j=m The item when
\]

\[= a^{m+1}+ \sum_{i=1}^m\binom{m}{i}a^{m+1-i}b^i +b^{m+1} +\sum_{j=0}^{m-1}\binom{m}{j}a^{m-j}b^{j+1} , Make j=i-1
\]

\[= a^{m+1} +b^{m+1}+ \sum_{i=1}^m\binom{m}{i}a^{m+1-i}b^i+\sum_{i=1}^{m}\binom{m}{i-1}a^{m+1-j}b^i
\]

\[=a^{m+1} +b^{m+1}+ \sum_{i=1}^m\Bigg[\binom{m}{i}+\binom{m}{i-1}\Bigg]a^{m+1-i}b^i, according to ：\binom{n}{m}+\binom{n}{m-1}=\binom{m+1}{i}
\]

\[=a^{m+1} +b^{m+1}+ \sum_{i=1}^m\binom{m+1}{i}a^{m+1-i}b^i
\]

\[= \sum_{i=0}^{m+1}\binom{m+1}{i}a^{m+1-i}b^i
\]

inference ：
- $ C_n^0+C_n1+C_n^2\cdots+C_nn=(1+1)ⁿ⁼²n $
- $ C_n^0-C_n1+C_n^2-C_n3\cdots +C_n^n=(1-1)n=(0)^n$

Lucas Theorem

if p Prime number , For any integer $ 1 \le m \le n $ Yes ：

\[\binom{n}{m} \equiv \binom{n ~ mod ~ p}{m ~ mod ~ p}\binom{n/p}{m/p} (mod~p)
\]

It is difficult to prove , Knowledge of generating functions is needed , You can have a look if you are interested . Don't ask me. , I will not .

Using this formula, we can take the module of the more troublesome combinatorial numbers .

Pigeon nest theorem

Definition ： take n+1 An object , Divided into n Group , Then at least one group has two （ Or more ） The object .
Extension ： take n An object , Divided into k Group , Then there is at least one group , Contains greater than or equal to $\lceil \frac{n}{k} \rceil$ Items .
Example ： Here you are. n A positive integer $A=\{a_1,a_2...a_n\}$, And a positive integer c, ask , Can you find one A Subset B,B The sum of the elements in is c Multiple , If you can, output their number .$1 \le c \le n \le 10^5 ,1 \le a_i \le 10^5$.
- solution ： set up A The prefixes and are $ sum_i $ ,
\[ If you have any sum_l \equiv sum_r~(mod~c)
\]
\[ namely sum_l -sum_r\equiv0 ~(mod~c)
\]
\[ that \sum_{i=l+1}^ra_i\equiv0 ~(mod~c)
\]
\[ therefore \sum_{i=l+1}^ra_i That is the solution
\]
\[ The number of prefixes and is n , model c In the case of 0 The situation of , All in all c-1 In this case ,n>c-1
\]
\[ According to the pigeon nest theorem There must be sum_l \equiv sum_r~(mod~c)
\]
\[ in summary ： The problem will always be solved , The solution is \{ a_{l+1},a_{l+2},\cdots ,a_r |sum_l \equiv sum_r~(mod~c) \}
\]

The inclusion exclusion theorem

Definition ：$$ Equipped with _n A collection of _{S_i} , _{|S_i|} Express _{S_i} Size , Yes ：$$
\[\left| \bigcup_{i=1}^nS_i \right|=\sum_{i=1}^{n}|S_i|-\sum_{1 \le i < j \le n}|S_i\cap S_j|+\sum_{1 \le i < j <k \le n}|S_i\cap S_j\cap S_k|- \cdots
\]
\[+(-1)^{m-1}\sum_{a_i<a_{i+1}}\left| \bigcap_{i=1}^mS_{a_i} \right|+ \cdots + (-1)^{n-1}\left| \bigcap_{i=1}^nS_i \right|
\]
The formula looks so complicated 、 It's scary , But it's actually a very simple theorem .

As shown in the figure below, there are collections A、B、C：

Obviously there is ：
\[|A\cup B\cup C|= |A|+|B|+|C|-|A\cap B|-|A\cap C| -|B\cap C|+|A\cap B\cap C|
\]
Extend this problem to the general situation , It is the well-known principle of inclusion and exclusion .
prove ：
\[ set up ~T_i~ For the elements ~a_i~ In collection ~S_1,S_2,\cdots ,S_n~ Is the number of times
\]
\[ Because the inclusion exclusion theorem formula is equivalent to ~1-n~ All combinations of , That is, the complete set of combinatorial numbers , At this point, we choose the containing element in the complete set ~a_i~ The combination of
\]
\[ So in the inclusion exclusion theorem formula , Medium element ~a_i~ The number of occurrences is zero ：
\]
\[\sum_{j=1}^{T_i} (-1)^{i-1}\binom{T_i}{j}
\]
\[ According to the binomial theorem :(1-1)^n=\sum_{i=0}^{n}\binom{n}{i}(-1)^{i} , Yes ：
\]
\[0= 1-\sum_{i=1}^{n} (-1)^{i-1}\binom{n}{i}
\]
\[ namely ：\sum_{i=1}^{n} (-1)^{i-1}\binom{n}{i}=1
\]
\[ therefore \sum_{j=1}^{T_i} (-1)^{i-1}\binom{T_i}{j} =1, Element ~a_i~ The number of occurrences is zero ~1
\]
\[ That is to say, in the formula of the inclusion exclusion theorem, the number of occurrences of any element is ~1 , Then merging is union .
\]
Example ： Interval coprime problem , The number of Coprime pairs in two intervals , The range of the two intervals shall not exceed $10^6$.

Before considering this problem, let's consider a sub problem of it , a number $x$ And an interval $[l,r]$ The coprime problem of . Deal with this problem , The simplest way must be to traverse the interval and then use $gcd$ , The complexity is $O(NlogN)$,n Is the interval length , Add another interval that $O(N^2logN)$, Obviously too slow , At this time, we can think in reverse , Conversion problem , We can consider finding the number of non coprime , Then subtract the number of non coprime from all the numbers . Not mutually prime, that is , There are common factors , If the problem is transformed into finding the number of common factors , That's easy to deal with , For example, if all calculations have factors 2, namely 2 The number of multiples of , Just say the division of interval numbers 2 Just fine , That is, as long as $O(1)$ The number of numbers with a certain factor in the interval can be calculated by the complexity of , That is to say, we can count first $x$ Factoring , obtain $ m $ Factor $ a_1,a_2,\cdots ,a_m $, For a certain factor, we can find the interval $[l,r]$ in , Inclusion factor $ a_i $ The number of $ b_i $, If one factor is $a_1=3$ , Interval is $ [5,18] $ , So the corresponding $ b_1=\lfloor \frac{18-5+1}{3} \rfloor=5, That is to say {6,9,12,15,18} this 5 Number , Yes $ $b

_i=\lfloor \frac{r-l+1}{a_i} \rfloor $

It seems that we put all $ b_i $ Together, we can solve this problem , But in fact, if you put $ b_i $ Add up , The final answer will be a lot more , For example, at the same time 2 and 3 As a number of factors , If we just add , that 6 The multiple of is multiplied , And if there is 2 and 6 It's a factor , that 6 It must also be a factor , That would be even more troublesome . To solve this problem , We also need to break down the problem again , We will $ x $ Split into prime factors $ p_1,p_2,\cdots,p_k $, set up $k$ Set of copies $S_1,S_2,\cdots ,S_k$ , $S_i$ Indicates that the interval contains factors $p_i$ A set of numbers of . according to The inclusion exclusion theorem At this point, there is the value we require, that is ：
\[\left| \bigcup_{i=1}^kS_i \right| =\sum_{j=1}^k \left((-1)^{j-1}\sum_{a_i<a_{i+1}}\left| \bigcap_{i=1}^jS_{a_i} \right| \right)
\]
\[ set up \sum_{a_i<a_{i+1}}\left| \bigcap_{i=1}^jS_{a_i} \right| by A_j
\]
\[ Yes ：\left| \bigcup_{i=1}^kS_i \right| =\sum_{j=1}^k (-1)^{j-1} A_j
\]
\[ set up function ~f(x), Express ~x~ Quantity of qualitative factors
\]
\[ Yes ：A_j=\sum_{f(a_i)=j} b_i
\]
there $A_j$ The practical meaning of is that the interval contains a qualitative factor greater than or equal to $j$ Number of , So we find out the number of its prime factor for each factor, corresponding to its $b_i$ Add up to $A_j$ And then we can find out $A_j$ Value . Put it another way , Factors are all non empty combinations of prime factors , What we ask $b_i$ That is, under this combination, how many intervals there are and how many corresponding numbers , For example, if you combine all the factors in pairs $b_i$ Value accumulation , Then we can find out how many numbers in the interval contain two or more prime factors , And then through The inclusion exclusion theorem duplicate removal , We can get the solution .

How complex is this method ？ Let's first observe the steps of this method
1. Yes $x$ Decomposing prime factor
2. Make a full combination of prime factors , And then calculate the corresponding $b_i$ The value is added to $A_j$ On .
3. Calculate the formula of inclusion exclusion theorem , Get the number of non coprime pairs .
4. Subtract the amount calculated above from the range of the interval , Get the solution .
step 1 Use Pollard-rho The algorithm decomposes the prime factor , The complexity is $O(n^{\frac{1}{4}})$, step 2 Make a full combination of prime factors , hypothesis $x$ by $ p_1^{n_1}p_2{n_2}\cdots p_n^{n_k} $ All in all $ (n_1+1)(n_2+1)\cdots (n_k+1) -1$ In this case , reduce 1 Because 1 Although it is a factor , But it's not ,k Is the kind and quantity of qualitative factors , in consideration of $1081080=2×2×2×3×3×3×5×7×11×13,256$, And calculate the corresponding $b_i$ The complexity of the value is $O(1)$, By looking up the table （http://wwwhomes.uni-bielefeld.de/achim/highly.txt ）, It is found that its growth is lower than $O(n^{\frac{1}{4}})$ but $ 10^6 $ Less than $O(n^{\frac{1}{4}})$, stay . step 3 Calculate staggered addition and subtraction , Complexity $ O(k) $ . step 4 Complexity $O(1)$. in summary , The data range is $ 10^6 $ when , The worst case requires hundreds of operations , In the scope of universality, complexity can be regarded as $O(n^{\frac{1}{4}})$.
We are $O(n^{\frac{1}{4}})$ The coprime pairs of a number for an interval are found in the complexity of , That interval is the same as the coprime pair of an interval , Just solve every number in the interval , The complexity is $O(n^{\frac{5}{4}})$.

in addition

There are many other things about combinatorial numbers, such as ：

Carter LAN number
stirling numbers
Bell count
Bernoulli number
Permutation and combination of multiple sets
Non contiguous arrangement
Dislocation arrangement
Circular arrangement

These are some classic counting models , You don't have to be able to prove or deduce , But know what kind of problems they can solve , What is their model .

If you are interested in combinatorial counting , You can learn generating functions （ The generating function ）

ACM More related articles on getting started with combinatorial counting

HDU4609 FFT+ Combination count
HDU4609 FFT+ Combination count Portal :http://acm.hdu.edu.cn/showproblem.php?pid=4609 The question : find n The probability that three sticks from one stick can form a triangle Answer key : ...
bzoj 2281 [Sdoi2011] Black and white （ game + Combination count ）
Black and white (game) [ Problem description ] Small A And small B I think of a new game . The game is in a 1*n On the chessboard of , There are... On the chessboard k A chess piece , Half black , Half white . On the far left is the white chessman , On the far right is the black chessman , The color of adjacent pieces ...
BZOJ 4555: [Tjoi2016&Heoi2016] Sum up [ Divide and conquer FFT Combination count | Polynomial inverse ]
4555: [Tjoi2016&Heoi2016] Sum up The question : seek \[ \sum_{i=0}^n \sum_{j=0}^i S(i,j)\cdot 2^j\cdot j! \\ S It's the second kind of Stirling ...
BZOJ 4555: [Tjoi2016&Heoi2016] Sum up [FFT Combination count Principle of tolerance and exclusion ]
4555: [Tjoi2016&Heoi2016] Sum up The question : seek \[ \sum_{i=0}^n \sum_{j=0}^i S(i,j)\cdot 2^j\cdot j! \\ S It's the second kind of Stirling ...
【BZOJ5491】[HNOI2019] polygon （ simulation , Combination count ）
[HNOI2019] polygon ( simulation , Combination count ) Topic Luogu Answer key I want to swear all of a sudden , Originally, my examination room has been cut , result WA A few points , Just taking a look at the code, I forgot to take the mold . First of all, we find that the terminal state must be all points to $n$ Even the edge ( ...
[ summary ] Number theory is related to combinatorial mathematics （ Theorem & prove & The board ）
0 Write it at the front 0.0 Preface Because I'm too busy , Cause some things to forget as soon as they learn , I'd like to write this article to record the math related problems that make me headache most . Some of the quoted text annotates the original link , If it violates your rights and interests , Please let me know : If there is an error in the article , Please let me know . ...
【BZOJ5323】[JXOI2018] game （ Combination count , Linear sieve ）
[BZOJ5323][JXOI2018] game ( Combination count , Linear sieve ) Topic BZOJ Luogu Answer key Obviously, the only positions to be considered are those in $[l,r]$ There is no number of any divisor in . Suppose such a number has $x$ individual , So what's left ...
【BZOJ5305】[HAOI2018] apple （ Combination count ）
[BZOJ5305][HAOI2018] apple ( Combination count ) Topic BZOJ Luogu Answer key Consider the contribution calculated for each edge . The contribution of each side is $size*(n-size)$. For a point $u$, If it had a big tree ...
【BZOJ3142】[HNOI2013] The sequence （ Combination count ）
[BZOJ3142][HNOI2013] The sequence ( Combination count ) Topic BZOJ Luogu Answer key The only consideration is to assign a value to $k-1$ God , Assume that this $k-1$ God, it's allocated , The first $i$ Heaven is $a_i$, false ...
【BZOJ4005】[JLOI2015] What about lying to me （ A class , Combination count ）
[BZOJ4005][JLOI2015] What about lying to me ( A class , Combination count ) Topic BZOJ Luogu Answer key lalaxu #include<iostream> using namespace std; ...

Random recommendation

opencv2 Use the mouse to draw a rectangle and intercept and save the image of the rectangular area
Preface I haven't written a blog for a long time , Today, I wrote an article about opencv2 Mouse response operation in the article . Mouse operation belongs to user interface design , I used to use Qt To do it , But if you only need a simple mouse , Keyboard operation , Call directly opencv Library functions have not tasted ...
First try “ Qiniuyun ”-- Zero base uses seven cattle clouds to cooperate UEditor Upload and browse pictures （.NET piece ）
( Registering and creating storage space will not be introduced , A handful of information on the Internet , Try to understand a little by yourself ) As a mature rookie , If you encounter a new problem , The first step, of course, is to Baidu first ... I saw N A post about the use of qiniu cloud , It means it's still circled , I understand ...
How to use App Studio Quickly customize your own Universal Windows App
I've introduced to you before App Studio This artifact can help you make one quickly Windows Phone 8 Application , Today I'm writing an article about App Studio My article is because ,App Studio the ...
C# LLSQL Quick query framework
This paper introduces a new type query method , similar linq,lambda grammar , Similar standard sql Usage habits , Supports anonymous types , Generic , At present, we support mssql,mysql, Switching only requires DatabaseConfig.DatabaseType ...
phpstorm Align arrays automatically =>, Auto space
After writing the code, you can click in the menu code-reformat code, Shortcut keys are option+command+L
C# Eval stay asp.net The usage and function of
Eval( " ") and Bind( " ") These two are one-way bindings , A two-way binding ,bind It's two-way binding , But it needs data source support ASP.NET 2.0 Improved data binding operation in template ...
POJ3974 Palindrome
The copyright of this article belongs to ljh2000 And blog park , Welcome to reprint , But keep this statement , And give a link to the original , Thank You for Your Cooperation . The author of this article :ljh2000 The author blog :http://www.cnblogs.com/ljh2000-jump/ ...
《Algorithms 4th Edition》 Reading notes ——2.4 Priority queue (priority queue)-Ⅶ（ extend ： The implementation of heap sorting ）
2.4.5 Heap sort We can turn any priority queue into a sort method . Insert all elements into a finite queue to find the smallest element , Then repeat the operation of deleting the smallest elements to delete them in order . The priority queue implemented with an unordered array is equivalent to an interpolation ...
[1] Report Fusioncharts
Graphic report of fusioncharts
Qt Child window and parent window blocking problem
In the graphic interface , Software designers usually need to limit the active window to one . When a window is active , Its parent window is blocked or partially blocked by it , At this time, clicking on the parent window with the mouse is useless . The key to the problem is to set the subwindow to mode : void MainWi ...