当前位置：网站首页>[combinatorics] dislocation problem (recursive formula | general term formula | derivation process)*

[combinatorics] dislocation problem (recursive formula | general term formula | derivation process)*

2022-07-03 18:30:00 【Programmer community】

List of articles

One 、 Wrong way
Two 、 Derivation of recurrence formula for staggered arrangement problem
3、 ... and 、 Derive the staggered formula

One 、 Wrong way

$n$ A different letter And

$n$ Different envelopes , take

$n$ The number of schemes with wrong envelopes in each letter ;

Dislocation ( Derangement ) , Therefore, we use

(

)

D(n)

$D (n)$ Express

$n$ Staggered arrangement of elements ;

If there is

$1$ letter ,

n= 1

$n = 1$ , At this time, it is not allowed to arrange wrongly ,

(

)

D(1) = 0

$D (1) = 0$ ;

If there is

$2$ letter ,

n= 2

$n = 2$ , At this time, the wrong arrangement can be completed by exchanging , Yes

$1$ Kind of plan ,

(

)

D(2) = 1

$D (2) = 1$ ;

Insert picture description here

If there is

$3$ letter ,

1,2,3

$1, 2, 3$ Three letters and three envelopes ,

If
If
$D (3) = 2$

If there is

$4$ letter , At this time, it is difficult to calculate ,

$9$ Methods ,

(

)

D(4) = 9

$D (4) = 9$

If there is

$5$ letter

⋯

\cdots

$\dots$ ,

(

)

D(5) = 44

$D (5) = 44$

⋮

\vdots

$⋮$

If there is

$n$ letter

⋯

\cdots

$\dots$ ,

(

)

(

−

)

(

−

)

(

−

)

(

−

)

⋯

(

−

)

∑

(

−

)

D(n) = n! ( \cfrac{(-1)^0}{0!} + \cfrac{(-1)^1}{1!} + \cfrac{(-1)^2}{2!} + \cfrac{(-1)^3}{3!} + \cdots + \cfrac{(-1)^n}{n!} ) = n! \sum\limits_{k=0}^{n}\cfrac{(-1)^k}{k!}

$D (n) = n! (\frac{( - 1 ) ^{0}}{0 !} + \frac{( - 1 ) ^{1}}{1 !} + \frac{( - 1 ) ^{2}}{2 !} + \frac{( - 1 ) ^{3}}{3 !} + \dots + \frac{( - 1 ) ^{n}}{n !}) = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}$

Two 、 Derivation of recurrence formula for staggered arrangement problem

Observe the above rules , Derive the recurrence formula ;

If there is

$n$ letter , Any letter needs to be misplaced , The number of staggered schemes is

(

)

D(n)

$D (n)$ ;

1 . Step by step counting principle : Use Step by step counting principle , Statistics first The arrangement of the first letter , And then we'll talk about it The number of arrangement methods of other letters ;

( 1 ) First step : First find a letter

$a$ come out , This letter cannot be placed in its own place , Can only be placed in the rest

−

n-1

$n - 1$ In a position , So there is

−

n-1

$n - 1$ To arrange ;

( 2 ) The second step : Now let's talk about the rest except

$a$ The wrong arrangement of the position of other letters except ;

2 . Classification and counting principle

Suppose the first letter

$a$ Occupy

$b$ The location of , So at this time

$b$ There are two ways to put it in which envelope ,

$b$ Put it in

$a$ Location , or

$b$ Not put in

$a$ Location ;

( 1 ) The first category : The first is to put

$a$ Location , here

$b$ Put it in

$a$ Location , be left over

−

n-2

$n - 2$ The letter is wrongly arranged , The number of options is

(

−

)

D(n-2)

$D (n - 2)$

( 2 ) The second category : The second situation is

$b$ I didn't go

$a$ The location of , that

$b$ May appear in addition to

$a$ Anywhere except ,

$b$ Yes

−

n-2

$n - 2$ There are four places to go , Can't go to

a,b

$a, b$ Location , All other elements have

−

n-2

$n - 2$ There are four places to go (

a,b

$a, b$ Position cannot go ) , In this case It's equivalent to dividing

$a$ The wrong arrangement of other elements besides , namely

−

n-1

$n - 1$ Dislocation of elements , The number of options is

(

−

)

D(n-1)

$D (n - 1)$ ; * ( Core derivation logic ) *

( 3 ) The law of addition : Summarize the above classification and counting principles , Use The law of addition , The result is

(

−

)

(

−

)

D(n -1) + D(n-2)

$D (n - 1) + D (n - 2)$

3 . product rule : Summarize the above step-by-step counting principle , Use product rule , The result is

(

)

(

−

)

(

−

)

(

−

)

D(n) = (n-1) (D(n -1) + D(n-2))

$D (n) = (n - 1) (D (n - 1) + D (n - 2))$

3、 ... and 、 Derive the staggered formula

The recursive formula :

(

)

(

−

)

(

−

)

(

−

)

D(n) = (n-1) (D(n -1) + D(n-2))

$D (n) = (n - 1) (D (n - 1) + D (n - 2))$

initial value :

(

)

(

)

D(1) = 0 , D(2) = 1

$D (1) = 0, D (2) = 1$

Use Recurrence equation , Generating functions to solve recursive equations , Principle of tolerance and exclusion , The following formula can be derived :

(

)

(

−

)

(

−

)

(

−

)

(

−

)

⋯

(

−

)

∑

(

−

)

D(n) = n! ( \cfrac{(-1)^0}{0!} + \cfrac{(-1)^1}{1!} + \cfrac{(-1)^2}{2!} + \cfrac{(-1)^3}{3!} + \cdots + \cfrac{(-1)^n}{n!} ) = n! \sum\limits_{k=0}^{n}\cfrac{(-1)^k}{k!}

$D (n) = n! (\frac{( - 1 ) ^{0}}{0 !} + \frac{( - 1 ) ^{1}}{1 !} + \frac{( - 1 ) ^{2}}{2 !} + \frac{( - 1 ) ^{3}}{3 !} + \dots + \frac{( - 1 ) ^{n}}{n !}) = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}$

Reference resources :

Baidu Encyclopedia - The staggered formula
【 Combinatorial mathematics 】 Recurrence equation ( Summary of the solution process of recursive equations | Homogeneous | Heavy root | Nonhomogeneous | The characteristic root is 1 | Exponential form | The bottom is the exponential form of the characteristic root ) **
【 Combinatorial mathematics 】 Generating function ( Generate function application scenarios | Solving recursive equations using generating functions )
【 Set theory 】 Principle of tolerance and exclusion ( The inclusion exclusion principle | Example )

原网站

版权声明
本文为[Programmer community]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202150237318813.html