PERMUTATIONS

​Ngo Van Minh - UMC

​Permutations

Hoán vị​

​

​1. Qui tắc cộng.  (Rule of sum/Additional rule/Princilpe)

• Ta có 2 (hoặc nhiều) công việc (Jobs) độc lập (tách rời nhau).

Có m cách (ways) để làm Job1. Có n cách để làm Job2.

Khi đó ta có: (m+n)  cách (ways) để thực hiện Job1 hoặc Job2.

​

​2. Qui tắc nhân. (Rule of product/Multiplication rule/principle)

• Ta có 2 (hoặc nhiều) công việc (Jobs) độc lập (tách rời nhau).

Có m cách (ways) để làm Job1. Có n cách để làm Job2.

Khi đó ta có: (mxn) cách (ways) để thực hiện cả hai công việc (Job1

và Job2).

​Factorial of natural number n (Giai thừa của số tự nhiên n) is denoted as:

• 0! = 1.

• n! = 1 x 2 x 3 x ... x n.

• Giai thừa của n là số cách xếp n người vào n cái ghế trên một hàng.

​1! = 1.

2! = 1 × 2 = 2

3! = 1 ×2 × 3 = 6

4! = 1 × 2 × 3 × 4 = 24

5! = 1 × 2 × 3 × 4 × 5 = 120

6! = 1 × 2 × 3 × 4 × 5 × 6 = 720

7! = ​1 × 2 × 3 × 4 × 5 × 6 × 7 = 5040

n! = (n-1)! × ​N.

Why 0! = 1 ???

​

5! =

​

4! =

​

3! = 0! =​

​

2! =

​

1! =

​

​

​

Multiple Choice

$$\frac{10!}{8!}\ =\$$  

• 80

• 9

• 10

• 90

Multiple Choice

$$4!=...$$  

• $$4+3+2+1$$  

• $$1x2x3x4$$  

• $$4+5+6$$  

• $$4$$  

Multiple Choice

$$Tính\ giá\ trị:\ \frac{6!}{5!}=$$  

• $$6$$  

• $$30$$  

• $$\frac{1}{5}$$  

• $$\frac{1}{6}$$  

Multiple Choice

$$Tính\ giá\ trị:\ \ 4!+5!=$$  

• 120

• 122

• 144

• 135

Multiple Choice

$$Tính\ giá\ trị\ \ \ \ 7!-5!=$$  

• 4,520

• 4,620

• 4,820

• 4,920

Multiple Choice

$$\frac{100!}{101!}\ =\$$  

• 101

• 1/100

• 100

• 1/101

Multiple Choice

$$\frac{100!\ x\ 100!}{101!\ x\ 99!}\ =\$$  

• 101/99

• 1

• 100

• 100/101

Multiple Choice

$$A\ =\frac{1!}{3!}+\frac{2!}{4!}+\frac{3!}{5!}+...+\frac{98!}{100!}\ =\$$  

• 99/100

• 1

• 49/100

• 1/2

Permutation: is the number of ways we can arrange k people of the group of n people in a row of k chairs (k ≤ n), such that no person hold more than one chair. We denote it as: P(n,k)

​

Hoán vị (hoán đổi vị trí) là số cách xếp k người từ nhóm n người vào k chiếc ghế trên một hàng (k ≤ n). Ta ký hiệu là: P(n,k).​

​

Ví dụ 1: Có bao nhiêu cách xếp 1 người từ nhóm 5 người vào 1 cái ghế?

P(5,1) = 5​

​

​

Ví dụ 2: Có bao nhiêu cách xếp 2 người từ nhóm 5 người vào 2 cái ghế?

P(5,2)=5x4=20

​

​

​

Ví dụ 3: Có bao nhiêu cách xếp 3 người từ nhóm 5 người vào 3 cái ghế?

P(5,3)=5x4x3=60

​

​

Ví dụ 4: Có bao nhiêu cách xếp 4 người từ nhóm 5 người vào 4 cái ghế?

​P(5,4)=5x4x3x4=240

​

​

​

Ví dụ 5: Có bao nhiêu cách xếp 5 người từ nhóm 5 người vào 5 cái ghế?

P(5,5)=5x4x3x2x1=120 Hoặc theo giai thừa ta có:

P(5,5)=5!=120

​

​

Multiple Choice

$$P\left(7,2\right)\ =\$$  

• 5

• 7

• 42

• 210

Multiple Choice

How many ways can a club select a president, vice president, and a secretary from a group of 6 people?

Có bao nhiêu cách để một câu lạc bộ chọn được chủ tịch, phó chủ tịch và thư ký từ một nhóm 6 người?

• 30

• 120

• 720

• 240

Multiple Choice

How many ways ways can you arrange the letters and digit in the word UMC4?

Có bao nhiêu cách bạn có thể sắp xếp các chữ cái và chữ số trong từ UMC4?

• 12

• 4

• 24

• 15

Multiple Choice

$$Số\ thứ\ 10\ của\ dãy\ sau:\ \ \ \ 20,19,18,17,...$$  

• 9

• 10

• 11

• 12

Multiple Choice

$$Số\ thứ\ k\ của\ dãy\ số\ sau\ (k\le n):\ \ n,n-1,n-2,n-3,...$$  

• $$n-k-1$$  

• $$n-k$$  

• $$n-k+1$$  

• $$n-k+2$$  

Multiple Choice

$$7!\ =\ \frac{10!}{10x9x8}$$  

• True

• False

Multiple Choice

$$20x19x18x17x16\ =\ \frac{20!}{15!}$$  

• True

• False

Multiple Choice

$$Với\ k\le n,\ Ta\ có:\ \ \ nx\left(n-1\right)x\left(n-2\right)x...\left(n-k+1\right)=\frac{n!}{\left(n-k\right)!}$$  

• True

• False

Tổng quát: Hoán vị (hoán đổi vị trí) là số cách xếp k người từ nhóm n người vào k chiếc ghế trên một hàng (n ≥ k). Ta ký hiệu là: P(n,k).

​

P(n,k)=?

​

​

Để xếp người vào k ghế, ta có k công việc cần phải làm:

Công việc 1: Xếp người vào ghế thứ 1: Có n cách làm.

Công việc 2: Xếp người vào ghế thứ 2: Có (n-1) cách làm. (Vì đã có 1 người ngồi ở ghế 1)

Công việc 3: Xếp người vào ghế thứ 3: Có (n-2) cách làm. (Vì đã có 2 người được xếp chỗ)

…

Công việc k: Xếp người vào ghế thứ k: Có: n-(k-1) = (n-k+1) cách làm. (vì đã có k-1 người được xếp chỗ)

Theo quy tắc nhân, số cách xếp người vào k ghế là:

P(n,k)=n.(n-1).(n-2)….(n-k+1) = n.(n-1).(n-2)….(n-k+1).(n-k).(n-k-1)…2.1/[(n-k).(n-k-1)…..2.1] = n!/(n-k)

​

​

Multiple Choice

$$P\left(n,k\right)=\frac{n!}{\left(n-k\right)!}$$  

• True

• False

Multiple Choice

$$Câu\ trả\ lời\ nào\ sai?\ P\left(8,3\right)=$$  

• $$\frac{8!}{5!}$$  

• $$8x7x6$$  

• 363

• 336

Bài 1. Có bao nhiêu số có 4 chữ số khác nhau mà chứa toàn chữ số lẻ. Viết công thức P(n,k)

​

​

​

​

​Bài 2. Có bao nhiêu số có 4 chữ số khác nhau, khác 0, và chia hết cho 5. Viết công thức có P.

Bài 3. Có bao nhiêu số có các chữ số khác nhau và khác 0?

​

​

​

​

​

​I. Permution without repetition: Hoán vị  không có sự lặp lại là hoán vị mà các vị trí khác nhau (các cái ghế) có các phần tử khác nhau (con người hoặc các con số).

 

Ví dụ: Số cách xếp 6 người vào 6 cái ghế trên 1 hàng: P(6,6)=6x5x4x3x2x1=6!= 720.

 

Vậy ta có thể hiểu được giai thừa của n số chính là số cách sắp xếp n người vào n cái ghế.

 

Ví dụ 2: Có bao nhiêu số có 4 chữ số khác nhau và toàn là các chữ số lẻ: P(5,4)=5x4x3x2=120 hay viết bằng công thức: P(5,4)=5!/(5-4)!=5!/1!=120.

II. Permution with repetition:

​Hoán vị được phép có lặp lại, tức là khi ta sắp xếp các phần tử thì một số vị trí có thể có những phần tử giống hệt nhau.

Ví dụ: Khi ta đặt pass của Iphone6 có 6 chữ số, thì tại các vị trí các chữ số có thể giống nhau được, khi đó số các viết vào mỗi vị trí sẽ là 10 và số cách đặt pass sẽ là:

10x10x10x10x10x10 = 1,000,000

 

Hoặc quay lại ví dụ trên, câu hỏi là có bao nhiêu số có 4 chữ số bao gồm toàn các chữ số lẻ, kết quả sẽ là: 5x5x5x5 = 625, vì các chữ số ở các vị trí khác nhau có thể giống nhau (được lặp lại).​

III. Permution with restrictions: Hoán vị có điều kiện ràng buộc (chướng ngại vật).

​When additional restrictions are imposed, the situation is transformed into a problem about permutations with restrictions.

Ví dụ:

Với bài toán có bao nhiêu số có 4 chữ số khác nhau ta có thế sắp xếp các chữ số từ trái qua phải là 9x9x8x7=5436.

Nhưng nếu ta thêm một điều kiện ràng buộc là số đó là số lẻ, tức là có bao nhiêu số lẻ có 4 chữ số khác nhau, khi đó ta ưu tiên xử lý ràng buộc trước:

Viết hàng đơn vị: có 5 cách. Sau khi xử lý xong ràng buộc ta lại quay lại làm bình thường, tức là:

Viết hàng nghìn: 8, viết hàng trăm 7, viết hàng chục 6: 5x8x7x6=1680.

IV. Circular Permutations: Hoán vị vòng tròn.

​The number of ways to arrange n distinct objects along a circle is P_n=(n-1)!.

The number is (n-1)! instead of the usual factorial n! since all cyclic permutations of objects are equivalent because the circle can be rotated..

For example, of the 3!=6 permutations of three objects, the (3-1)!=2 distinct circular permutations are {1,2,3} and {1,3,2}.

Similarly, of the 4!=24 permutations of four objects, the (4-1)!=6 distinct circular permutations are {1,2,3,4}, {1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}, and {1,4,3,2}.

Permutations:

4!/4 = 3! = 6​

4 people

Permutations:

4! = 24​

5 people

​

​

5! = 120

6 people​

​

7! = 5040

8 people​

​

Multiple Choice

There are 6 books of Math, Physics, Chemistry, Biology, English, and France are arranged on 1 row of bookshelf. How many ways are there to arrange the Math book on the left side of the Biology book?

• $$240$$  

• $$360$$  

• $$120$$  

• $$720$$   

Multiple Choice

How many 8 digit numbers are there, such that they are divisible by 9 and all of the digits are distinct?

• $$4x8!$$   

• $$5x8!$$   

• $$36x7!$$   

• $$9!$$    

Multiple Choice

How many arrangements are there ofthe letters of BANANA

such that no two N's appear in adjacent positions? 

• $$40$$  

• $$60$$  

• $$80$$  

• $$30$$  

Multiple Choice

How many ways can the letters of the word BOTTLES be arranged such that both of the vowels are at the end? 

Note: The vowels in the word BOTTLES are O and E.

• $$40$$  

• $$60$$  

• $$80$$  

• $$120$$   

Multiple Choice

Among 5 students in a group, exactly two of them are wearing red hat. How many ways are there to seat all 5 students in a row such that the two red hat students are not sitting adjacent to each other?

• $$48$$  

• $$60$$  

• $$72$$  

• $$120$$   

Multiple Choice

In how many ways can 3 people can be seated around a round table?

• $$6$$  

• $$2$$  

• $$3$$  

• $$1$$   

Multiple Choice

3 boys and 2 girls are about to be seated at a rotatable round table. If the 2 girls want to sit next to each other, find the number of ways seating these boys and girls.

• $$24$$  

• $$60$$  

• $$12$$  

• $$72$$   

Fill in the Blanks

Multiple Choice

The dartboard above is made up of three concentric circles with radii 1, 3, and 5. Assuming that a dart thrown will land randomly on the dartboard, what is the probability that it lands in the green region?

• 30%

• 36%

• 40%

• 60%

Multiple Choice

The dartboard above is made up of three concentric circles with radii 1, 3, and 5. Assuming that a dart thrown will land randomly on the dartboard, what is the probability that it lands in the green region?

• 30%

• 36%

• 40%

• 60%

Bài 1. Có bao nhiêu cách sắp xếp các chữ trong các từ sau đây?

1) VN

2) VNN

3) ELEVEN

4) BANANA

​

​

​

​

Bài 2. Có bao nhiêu số có 3 chữ số khác nhau và không chứa chữ số 3.

​

​

​

​

Bài 3. Có bao nhiêu số có 3 chữ số trong đó có ít nhất một trong các chữ số 0 và 1.

Bài 4. Có bao nhiêu đường đi ngắn nhất từ A đến B theo hình vẽ?

​

​

​

​

Bài 5. Có bao nhiêu đường đi ngắn nhất từ A đến B theo hình vẽ?

​

​

​

​

Homework:

1. Calculate: A = 1!/4! + 2!/​5! + 3!/6! + ... + 17!/20!

​

​

​