当前位置：网站首页>[combinatorics] permutation and combination (two counting principles, examples of set permutation | examples of set permutation and circle permutation)

[combinatorics] permutation and combination (two counting principles, examples of set permutation | examples of set permutation and circle permutation)

2022-07-03 13:54:00 【Programmer community】

List of articles

One 、 Two counting principles 、 Set arrangement example
Two 、 Set arrangement 、 Example of circle arrangement

Arrange and combine reference blogs :

【 Combinatorial mathematics 】 Basic counting principle ( The principle of addition | Multiplication principle )
【 Combinatorial mathematics 】 Examples of permutation and combination of sets ( array | Combine | Circular arrangement | binomial theorem )
【 Combinatorial mathematics 】 Permutation and combination ( Arrange and combine content summary | Select the question | Set arrangement | Set combination )
【 Combinatorial mathematics 】 Permutation and combination ( Examples of permutations )
【 Combinatorial mathematics 】 Permutation and combination ( Multiset arrangement | Full Permutation of multiple sets | Multiset incomplete permutation The repetition of all elements is greater than the number of permutations | Multiset incomplete permutation The repetition of some elements is less than the number of permutations )
【 Combinatorial mathematics 】 Permutation and combination ( The combinatorial number of multiple sets | The repetition of all elements is greater than the number of combinations | The combinatorial number of multiple sets deduction 1 Division line derivation | The combinatorial number of multiple sets deduction 2 Derivation of the number of nonnegative integer solutions of indefinite equations )
【 Combinatorial mathematics 】 Permutation and combination ( Example of the number of combinations of multiple sets | Three counting models | Select the question | Multiple set combinatorial problem | Nonnegative integer solutions of indefinite equations )

One 、 Two counting principles 、 Set arrangement example

array

$26$ Letters , bring

a,b

$a, b$ There are

$7$ Letters , Find the number of permutation methods ;

Need to use Classification and counting principle ( The principle of addition ) , Step by step counting principle ( Multiplication principle ) ;

Category count ( The principle of addition ) : Yes
Step by step counting principle ( Multiplication principle ) : Yes $\times 4 \times 1 = 82×4×1=8 A plan ;$

1. First, use the step-by-step counting principle ,

First step : First construct with
$7$ A substructure of letters ;
The second step : take

The principle of counting by steps corresponds to the law of multiplication , The end result is Number of solutions in the first step multiply Number of schemes in the second step ;

2. First step calculation : First construct with

a,b

$a, b$ As boundary , There is... In the middle

$7$ A substructure of letters ;

In this substructure

$7$ Letters , It is equivalent to dividing

a,b

$a, b$ Other than

$24$ Choose from the letters

$7$ Arrange letters ,

One-to-one correspondence : It is equivalent to a set in which the elements are not repeated , Make an orderly selection , Corresponding to the arrangement of sets , Use the set arrangement formula to calculate ;

$24$ Choose from the letters

$7$ Arrange letters , The selection methods are

(

)

P(24, 7)

$P (24, 7)$ Kind of ;

This involves the principle of classification and counting ,

The first category is $P (24, 7) P(24, 7) P (24, 7) Kind of ;$
$b$ The situation after , The selection methods are
The second type is $P (24, 7) P(24, 7) P (24, 7) Kind of ;$
$a$ The situation after , The selection methods are

The principle of classification and counting corresponds to the law of addition , The total number of methods is The first category And The second category Add it up , The selection methods are

(

)

2\ P(24, 7)

$2 P (24, 7)$ Kind of ;

3. The second step is to calculate : take

a,b

$a, b$ Substructure as element , And others

−

26-9 = 17

$26 - 9 = 17$ Child elements together , in total

$18$ All elements are arranged ;

$18$ All elements are arranged , The result is

18!

$18!$ ;

4. The first step multiply The second step plan ( Step by step calculation principle The law of addition ) :

Number of solutions in the first step multiply Number of schemes in the second step ;

(

)

N = 2\ P(24, 7) \ 18!

$N = 2 P (24, 7) 18!$

Two 、 Set arrangement 、 Example of circle arrangement

$10$ A boy ,

$5$ A girl , Stand in a row , If there are no girls nearby , How many ways ? If you stand in a circle , How many ways ?

Need to use Classification and counting principle ( The principle of addition ) , Step by step counting principle ( Multiplication principle ) ;

Category count ( The principle of addition ) : Yes
Step by step counting principle ( Multiplication principle ) : Yes $\times 4 \times 1 = 82×4×1=8 A plan ;$

$10$ A boy ,

$5$ A girl , Stand in a row , If there are no girls nearby , How many ways :

Step by step processing is required : Put the boys away first , Then insert the girl into the space ;

① First step : Put the boys away first , schoolboy

$10$ individual , After standing there

$11$ Lattice ;

$10$ The placement of boys , Orderly selection of elements without repetition , This is a set arrangement problem , The arrangement scheme has

(

)

P(10,10) = 10!

$P (10, 10) = 10!$ A plan ;

② The second step : Then insert the girl into the space ,

$5$ Girls can only put here

$11$ In a grid ;

$11$ Put

$5$ A girl , Orderly selection of elements without repetition , This is the arrangement of sets , The arrangement scheme has

(

)

P(11, 5)

$P (11, 5)$

③ Step by step counting principle ( Multiplication principle ) : take Number of solutions in the first step And Number of schemes in the second step Multiply , The number of schemes is :

(

)

(

)

P(10,10) \ P(11, 5)

$P (10, 10) P (11, 5)$

$10$ A boy ,

$5$ A girl , stand in a ring , If there are no girls nearby , How many ways :

Step by step processing is required : Put the boys away first , Then insert the girl into the space ;

① First step : First put the boys in a circle , schoolboy

$10$ individual , Because it's in a circle , So after standing up, there is only

$10$ Lattice ;

$10$ The placement of boys , Orderly selection of elements without repetition , This is the arrangement of set circles , You need to use the circle arrangement formula , The arrangement scheme has

(

)

\cfrac{P(10,10)}{10}

$\frac{P ( 1 0 , 1 0 )}{1 0}$ A plan ;

Reference resources : 【 Combinatorial mathematics 】 Permutation and combination ( Arrange and combine content summary | Select the question | Set arrangement | Set combination ) Four 、 Ring arrangement

n
n
$n$ Meta set
S
S
$S$ , from
S
S
$S$ Collection Orderly , No repetition selection
r
r
$r$ Elements ,
S
S
$S$ A collection of
r
−
r-
$r -$ Ring arrangement number
=
P
(
n
,
r
)
r
= \dfrac{P(n,r)}{r}
$= \frac{P ( n , r )}{r}$
r
r
$r$ Different linear permutations , Equivalent to the same ring arrangement ;
A ring arrangement , Cut from any position , Can constitute a
r
r
$r$ Different linear arrangements ;

② The second step : Then insert the girl into the space ,

$5$ Girls can only put here

$10$ In a grid ;

$10$ Put

$5$ A girl , Orderly selection of elements without repetition , This is the arrangement of sets , The arrangement scheme has

(

)

P(10, 5)

$P (10, 5)$

③ Step by step counting principle ( Multiplication principle ) : take Number of solutions in the first step And Number of schemes in the second step Multiply , The number of schemes is :

(

)

(

)

\cfrac{P(10,10)}{10} \ P(10, 5)

$\frac{P ( 1 0 , 1 0 )}{1 0} P (10, 5)$