[combinatorics] basic counting principle (addition principle | multiplication principle)

1. The principle of addition

( 1 ) The principle of addition ( Can't stack Events can only be used The principle of addition | Apply to Select by category )

The principle of addition :

• 1. Description of addition rule : event $A$
• 1. The law of addition is extended : set up event $A_1,A_2,...,A_n$

  A

  1

  A_{1}

  A1​ or

  A

  2

  A_{2}

  A2​ or … or

  A

  n

  A_{n}

  An​ " The way it came into being yes

  p

  1

  +

  p

  2

  +

  .

  .

  .

  +

  p

  n

  p_{1} + p_{2} + ... + p_{n}

  p1​+p2​+...+pn​ Kind of ;

  p1​,p2​,...,pn​ Kind of The way of production , if among whatever Two event The way it came into being all No overlap , be " event

• 2. Be careful : there event

  A

  1

  ,

  A

  2

  ,

  .

  .

  .

  ,

  A

  n

  A_{1} , A_{2} , ... , A_{n}

  A1​,A2​,...,An​ Must be Cannot overlap , namely Only a event happen , If there are more than one event At the same time , It must be Use Multiplication principle ;

• 3. Application problems : Select by category ;

---

( 2 ) product rule ( Are independent of each other Of event Ability to use product rule | Apply to Step by step selection )

Multiplication principle :

• 1. Multiplication rule description : event A Yes m Kind of The way of production , event B Yes n Kind of The way of production , be " event A And B " Yes mn There are two ways to produce ;
• 1. Multiplication rule generalization : set up event $A_1,A_2,...,A_n$

  A

  1

  A_{1}

  A1​ or

  A

  2

  A_{2}

  A2​ or … or

  A

  n

  A_{n}

  An​ " The way it came into being yes

  p

  1

  p

  2

  .

  .

  .

  p

  n

  p_{1} p_{2} ... p_{n}

  p1​p2​...pn​ Kind of ;

  p1​,p2​,...,pn​ Kind of The way of production , if among whatever Two event The way it came into being all Are independent of each other , be " event

• 2. Be careful : there event

  A

  1

  ,

  A

  2

  ,

  .

  .

  .

  ,

  A

  n

  A_{1} , A_{2} , ... , A_{n}

  A1​,A2​,...,An​ Must be Are independent of each other Of ;

• 3. Application problems : Select step by step ;

---

2. Problem solving

( 1 ) exercises 1 ( The principle of addition )

subject :

The car market Yes truck 15 car , Van 8 car , Sedan 20 car ;
Buy only one car from the market , How many ways to buy ?

answer :

① It's used here The principle of addition , If only buy A car , Three kinds of cars You can only buy one , Three events It cannot overlap ;

② Buy a truck Yes 15 Ways of planting , Buy a van Yes 8 Ways of planting , Buy a car Yes 20 Kind of , Only one of the three methods can be selected , The three cannot overlap ( At the same time ) , So use the principle of addition Calculate ;

③ The result is : 15 + 8 + 20 = 43 ;

---

( 2 ) exercises 2 ( The principle of addition Multiplication principle Comprehensive use )

set up

A

,

B

,

C

A , B , C

A,B,C yes 3 Cities ,
from

A

A

A To

B

B

B Yes 3 Strip road , from

B

B

B To

C

C

C Yes 2 Strip road , from

A

A

A To

C

C

C Yes

4

4

4 Strip road ,
ask from

A

A

A To

C

C

C How many different ways ?

Explain :

The principle of addition :
① Directly from

A

A

A To

C

C

C And ② from

A

A

A Come first

B

B

B Until then

C

C

C yes Cannot overlap , programme ① And programme ② need Use the principle of family law ,

Multiplication principle :
programme ② Internal use required Multiplication principle namely

A

A

A To

B

B

B Yes 3 Kind of choice ,

B

B

B To

C

C

C Yes 2 A choice , These two choices are independent of each other , Step by step choice ,

3

∗

2

=

6

3 * 2 = 6

3∗2=6 Kind of ;

Final

N

=

3

×

2

+

4

=

10

N = 3 \times 2 + 4 = 10

N=3×2+4=10 ;

---

( 3 ) exercises 3 ( Multiplication principle )

subject :

from

1000

1000

1000 To

9999

9999

9999 Of Integers in :

① contain 5 How many are there ;
② How many Hundred bit and Ten digits Are all Odd number Of even numbers ;
③ Each digit Are different Of Odd number How many ;

answer :

( 1 ) contain 5 Number of numbers The number of :

① set up Numbers aggregate

{

0

,

1

,

2

,

3

,

4

,

5

,

6

,

7

,

8

,

9

}

\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}

{ 0,1,2,3,4,5,6,7,8,9}

② Ask directly contain

5

5

5 Number of numbers , More trouble : It can be divided into

1

1

1 position contain

5

5

5 Number of numbers , At this time, it is divided into bits ten Hundred bit Thousand bit Four situations ,

2

2

2 position or

3

3

3 position contain

5

5

5 More complicated ;

③ here Sure Change your mind , seek Not included 5 The number of :

• 1> Thousand bit : thousands You can't take $0$

  5 , Only value

  8 In this case ;

• 2> Hundred bit : Hundreds of digits You can't take

  5

  5

  9

  9

  5 , Yes

  9 Kind of The situation of value taking ;

• 3> ten : Hundreds of digits You can't take

  5

  5

  9

  9

  5 , Yes

  9 Kind of The situation of value taking ;

• 4> bits : Hundreds of digits You can't take

  5

  5

  9

  9

  5 , Yes

  9 Kind of The situation of value taking ;

According to the principle of multiplication : Not included

5

5

5 The number of digits of is

8

×

9

×

9

×

9

=

5832

8 \times 9\times 9\times 9 = 5832

8×9×9×9=5832
contain 5 The number of :

9000

−

5832

=

3168

9000 - 5832 = 3168

9000−5832=3168 ;

( 2 ) Hundred bit and Ten digits Are all Odd number Of even numbers :

analysis Four place Count Number of value schemes :

• 1> Number of single digit value schemes : Consider even numbers : If even numbers , that Single digit Only value $\{0,2,4,6,8\}$

  5 In this case ;

• 2> Ten digits and Hundreds of digits Value Number of schemes : Ten digits Hundreds of digits All are Odd number , that Its Value $\{1,3,5,7,9\}$

  5 Kind of plan ;

• 3> thousands Value Number of schemes :$\{1,2,3,4,5,6,7,8,9\}$

  9 Kind of plan ;

according to Multiplication principle : Hundred bit and ten Are all Odd number Of even numbers Yes

9

×

5

×

5

×

5

=

1125

9 \times 5 \times 5 \times 5 = 1125

9×5×5×5=1125 individual ;

( 3 ) Each digit Are different Of Odd number Number :

Bit by bit analysis :

• 1> analysis Single digit Value : Single digit If there are no restrictions , Yes $10$

  5

  5

  5 Medium scheme , Only from

  {

  1

  ,

  3

  ,

  5

  ,

  7

  ,

  9

  }

  \{1,3,5,7,9\}

  { 1,3,5,7,9} The value of ;

  { 0,1,2,3,4,5,6,7,8,9} , requirement yes Odd number , therefore Single digit Only

• 2> analysis Thousand bit The value of : thousands Without restrictions Yes $9$

  { 1,2,3,4,5,6,7,8,9} , If required And Different single digits , So there are

  8 Kind of plan ;

• 3> analysis Hundred bit Number value : Hundreds of digits If there are no restrictions , Yes $10$

  { 0,1,2,3,4,5,6,7,8,9} , Thousand bit And bits Their respective Take it One digit , Then I can only

  8 Kind of Number of schemes ;

• 4> analysis ten Number value : Ten digits If there are no restrictions , Yes $10$

  { 0,1,2,3,4,5,6,7,8,9} , Thousand bit , bits And Hundred bit Their respective Take it One digit , Then I can only

  7 Kind of Number of schemes ;

According to the principle of multiplication :

1000

1000

1000 To

9999

9999

9999 In the integer of , Each digit all Different Odd number Yes

5

×

8

×

7

×

7

=

2240

5 \times 8 \times 7 \times 7 = 2240

5×8×7×7=2240 individual ;

The sequence of each analysis is very particular , Generally speaking, we should analyze first The conditions are strict choice , Based on the analysis of A more relaxed choice ;

About one-to-one correspondence Explanation :
If nature

A

A

A Of Count More difficult , nature

B

B

B It's easier to count , nature

A

A

A and nature

B

B

B There is a one-to-one correspondence , So for nature

A

A

A Count of , Can be converted to Yes nature

B

B

B Count of ;
It's used here One-to-one correspondence , Such as Above , Count contain

5

5

5 Number of integers , If front counting is difficult , It can be reversed Calculation It doesn't contain

5

5

5 Number of integers , This makes it easier to count ,

1000

1000

1000 To

9999

9999

9999 Altogether

9000

9000

9000 Number ,

9000

−

No

contain

5

Of

whole

Count

individual

Count

9000 - Not included 5 Number of integers

9000− No contain 5 Of whole Count individual Count And contain

5

5

5 Number of integers It's one-to-one ;

Common one-to-one correspondence :
① Select the question
② Nonnegative integer solutions of indefinite equations
③ Non descending path problem
④ Positive integer splitting problem
⑤ The problem of putting the ball

---