Introduction to ACM combination counting

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_m^m}\), 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_n^1+C_n^2\cdots+C_n^n=(1+1)^n=2^n\)
  • \(C_n^0-C_n^1+C_n^2-C_n^3\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 ）