Recently, my students encountered some problems about the wrong formula when they were brushing HDU questions. As someone who has experienced it, I write this blog to guide them ~~~

If there are n elements in a sequence, there are n! Kind of arrangement method. If all the original elements are not in their original positions when the arrangement is made, the arrangement is called a mismatch. The number of slips refers to the number of slips in a sequence of n elements.

D(n)=(n-1)(D(n-1)+D(n-2)) in particular,D(1)=0,D(2)=1;

Error formula: D(n)=(n!) [(-1)^0/0!+(-1)^1/(1!)+(-1)^2/(2!)+(-1)^3/(3!)+……+(-1)^n/(n!)] ; Where n! =n*(n-1)*(n-2)*…… 3 times 2 times 1 in particular has 0 factorial. 1 = 1! = 1

First, let’s explain the recursion formula:

A triangulation formula for n different elements can be divided into two steps:

Step 1: Assuming we misarrange the first element, it can choose one of the elements from 2 to n, which is a total of N-1 choices.

Step 2: misarrange the other N-1 elements, also need to be divided into cases and types. Because it depends on the result of the first step, if the first element falls in the KTH position, the second step needs to misarrange element K, and different mispositions of element K will lead to different situations:

1. If the k element falls exactly where the first element is, then the first element and the KTH element can be completely removed, because they have just swapped places and the other elements have not changed yet. If we misarrange the remaining n-2 elements, then we get D(n-2) misarrange.

2. If the k element does not occupy the position of the first element, we can temporarily remove the first element in the position of k, and only the k element and the original n-2 elements will be generated. At this point, we can regard the original position of the first element as the original position of the current k element, because the k element cannot be placed in the original position, so it is equivalent to the original N -2 elements and k total n-1 elements are completely misarranged. So there are D of n minus 1 ways. The second case I hope you understand carefully! It’s easy to understand with a picture

 

So, we have D(n-2)+D(n-1) ways to do step two, according to the principle of addition.

According to the multiplication principle, D(n)=(n-1)(D(n-1)+D(n-2)). The recursion is explained.

Now let’s push the triangulation formula

Suppose D of n is equal to n factorial. N of N, then we get N factorial from the recursive formula above. N (N) = (N – 1)/(N – 2), N (N – 2) + (N – 1)! N (N – 1)], equation on the right side of the merger, we can get

n! N(n)=(n-1)! N(n-2)+(n-1)! The N minus one cancels out the N minus one factorial. So nN(n)= n (n-2)+ n (n-1)

So there are both sides minus the nN (n – 1) get: nN (n) – nN (n – 1) = (n – 1) n (n – 1) + n (n – 2) – nN (n – 1) : n (n (n) – n (n – 1)) = n (n – 1) + n (n – 2) \

Is (N (N) – N (N – 1))/(N (N – 1) – N (N – 2)) = (1)/N.

Similarly there are (N (N – 1) – N (N – 2))/(N (N – 2) – N (N – 3)) = (1)/(N – 1);

            (N(n-2)-N(n-3))/(N(n-3)-N(n-4))=(-1)/(n-2);

.

            (N(3)-N(2))/(N(2)-N(1))=(-1)/3;

So we have n minus 2 equations, and we can multiply the left-hand side, multiply the right-hand side, because they cancel out, so the equation that we get is 1, 2

(N) (N) – N (N – 1))/(N (2) – N (1)) = (1) ^ (N – 2)/(N * (N – 1) * (N – 2) * (N – 3) *… 4 * 3] equation 1 \

And since minus 1 to the n minus 2 is equal to minus 1 to the n, equation 2 and n is equal to D over 2 factorial. =1/2 N(1)=D(1)/1! =0 so N(2) -n (1)=1/2 Equation 3 Substituting these two equations 2 and 3 into equation 1 above we can get:

N (N) – N (N – 1) = (1) ^ N/(N * (N – 1) * (N – 2) * (N – 3) *… * 4 * 3 * 2] is: N (N) – N (N – 1) = (1) ^ N/N!

So there are N (N) = (1) ^ 2/2! +… (-1)^(n-1)/(n-1)! +(-1)^n/n! And D of n is equal to n factorial. N(n)

D (n) = n! [(-1)^2/2!+…(-1)^(n-1)/(n-1)!+(-1)^n/n! ] Have to the

Application of the misalignment formula:

 

N letters in n envelopes, how many different ways to put them all wrong, and let’s call the total number of misplaced elements f(n).

 

Method one:

 

Someone writes n letters and n envelopes, and if all the letters are in the wrong envelopes. How many different ways can all the letters be in the wrong envelope?

 

** When N=1 and 2, it is easy to obtain the solution ~, assuming that F(n-1) and F(n-2) have been obtained, focusing on the following situation: **

 

**1. When there are N letters, the first N-1 letter can have N-1 or N-2 wrong letters. 支那

 

**2. The former, for each kind of wrong packing, can be taken from the n-1 letter and the N letter wrong packing, so =F(n-1) * (n-1). 支那

 

3. The latter is simple, only the correct letter and the NTH letter exchange envelope, the correct letter can be any of the previous n-1 letter, so = F(n-2) * (n-1).

 

Basic form: d[1]=0; D [n]= (n-1)*(d[n-1] + D [n-2])

 

Method 2:

 

Suppose there are n letters, the first letter can be put in any envelope of (2-n), there are n-1 ways to put it, let the first letter be put in the KTH envelope, if the KTH letter is put in the first envelope, then we just need to misarrange the remaining N-2, namely F (n-2), if the KTH letter is not put in the first envelope, You can view the position of the first letter as the “KTH position”, that is, the n-1 letter is misarranged, which is f(n-1).

 

F (n)=(n-1)*(f(n-1)+f(n-2))

 

The following is the program implementation:

 

1 #include<stdio.h> 2 int fun(int); 3 int main() 4 { 5 int n,res; 6 printf("input a number:"); 7 scanf("%d",&n); 8 res=fun(n); 9 printf("There are %d cases.\n",res); 10 return 0; 11 } 12 int fun(int n) 13 { 14 if(n==1) 15 return 0; 16 if(n==2) 17 return 1; 18 return (n-1)*(fun(n-1)+fun(n-2)); 19}Copy the code