Các kết hợp có thể có. Kết hợp

Hãy xem xét vấn đề đếm số lượng mẫu từ một tập hợp đã cho trong điều kiện tổng quát. Hãy để có một số bộ N, bao gồm N các yếu tố. Bất kỳ tập hợp con nào của m các yếu tố có thể được xem xét mà không tính đến thứ tự của chúng, và cùng với nó, tức là khi thay đổi thứ tự, hãy chuyển sang thứ khác m- lấy mẫu.

Chúng tôi xây dựng các định nghĩa sau:

Vị trí không lặp lại

Bằng cách đặt mà không lặp lạiN các yếu tố củam Nchứa đựngmcác yếu tố khác nhau.

Nó theo định nghĩa rằng hai cách sắp xếp khác nhau, cả về phần tử và thứ tự của chúng, ngay cả khi các phần tử giống nhau.

Định lý 3. Số lượng vị trí không có sự lặp lại bằng với sản phẩm m yếu tố, lớn nhất trong số đó là số N . Viết ra:

Hoán vị không lặp lại

Hoán vị từN các phần tử được gọi là các tổ hợp khác nhau của tập hợpN.

Từ định nghĩa này, hai hoán vị chỉ khác nhau về thứ tự của các phần tử và có thể được coi là một trường hợp sắp xếp đặc biệt.

Định lý 4. Số lượng các hoán vị khác nhau mà không lặp lại được tính bằng công thức

Kết hợp không lặp lại

Một sự kết hợp không lặp lạiN các yếu tố củam bất kỳ tập hợp con không có thứ tự nào của một tập hợp được gọi làNchứa đựngm các yếu tố khác nhau.

Nó theo định nghĩa rằng hai tổ hợp chỉ khác nhau về phần tử, thứ tự không quan trọng.

Định lý 5. Số lượng kết hợp không có lặp lại được tính bằng một trong các công thức sau:

ví dụ 1. Có 5 cái ghế trong phòng. Bạn có thể đặt bằng bao nhiêu cách

a) 7 người; b) 5 người; c) 3 người?

Dung dịch: a) Trước hết cần chọn 5 người trong số 7 người ngồi vào ghế. Nó có thể được thực hiện
đường. Với mỗi lựa chọn trong số năm cụ thể, người ta có thể tạo ra
hoán vị ở các vị trí. Theo định lý nhân, số phương thức hạ cánh mong muốn là bằng nhau.

Bình luận: Vấn đề có thể được giải quyết chỉ bằng cách sử dụng định lý tích, lập luận như sau: có 7 lựa chọn để đáp xuống chiếc ghế thứ nhất, 6 lựa chọn cho chiếc ghế thứ 2, 5 lựa chọn cho chiếc ghế thứ 3, 4 cho chiếc ghế thứ 4 và 5-3. Khi đó số cách xếp 7 người vào 5 ghế bằng. Các giải pháp nhất quán theo cả hai cách, vì

b) Giải pháp rõ ràng -

Trong) - số lượng ghế đã được lựa chọn.

- số vị trí của ba người trên ba chiếc ghế đã chọn.

Tổng số lựa chọn là.

Không khó để kiểm tra các công thức
;

;

Số lượng tất cả các tập con của tập hợp bao gồm N các yếu tố.

Các vị trí có sự lặp lại

Vị trí với sự lặp lại từN các yếu tố củam là bất kỳ tập hợp con có thứ tự nào của một tập hợpN, bao gồmm các phần tử để bất kỳ phần tử nào cũng có thể được đưa vào tập hợp con này từ 1 đếnmlần, hoặc không ở tất cả.

Số lượng vị trí có sự lặp lại được biểu thị và được tính theo công thức, là hệ quả của định lý nhân:

Ví dụ 2. Cho một bộ ba chữ cái N = (a, b, c) được cho. Hãy gọi một từ bất kỳ tập hợp các chữ cái có trong tập hợp này. Hãy tìm số từ có độ dài 2 có thể được tạo thành từ các chữ cái này:
.

Bình luận: Rõ ràng, sự sắp xếp với sự lặp lại cũng có thể được xem xét để
.

Ví dụ 3. Yêu cầu từ các chữ cái (a, b) để tạo ra tất cả các từ có thể có độ dài 3. Có bao nhiêu cách thực hiện điều này?

Câu trả lời:

Tổ hợp là một nhánh của toán học nghiên cứu các câu hỏi về bao nhiêu tổ hợp khác nhau, tùy thuộc vào các điều kiện nhất định, có thể được tạo ra từ các đối tượng nhất định. Những điều cơ bản về tổ hợp là rất quan trọng để ước tính xác suất của các sự kiện ngẫu nhiên, bởi vì chính chúng làm cho nó có thể tính toán số lượng cơ bản có thể có của các kịch bản khác nhau cho sự phát triển của các sự kiện.

Công thức tổ hợp cơ bản

Cho có k nhóm phần tử và nhóm thứ i gồm n phần tử i. Hãy chọn một phần tử từ mỗi nhóm. Khi đó tổng số N cách có thể thực hiện lựa chọn như vậy được xác định theo quan hệ N = n 1 * n 2 * n 3 * ... * n k.

ví dụ 1 Hãy để chúng tôi giải thích quy tắc này bằng một ví dụ đơn giản. Cho có hai nhóm phần tử, nhóm thứ nhất gồm n 1 phần tử và nhóm thứ hai gồm n 2 phần tử. Có thể tạo ra bao nhiêu cặp nguyên tố khác nhau từ hai nhóm này để mỗi cặp chứa một nguyên tố trong mỗi nhóm? Giả sử chúng ta lấy phần tử đầu tiên từ nhóm đầu tiên và không thay đổi nó, đi qua tất cả các cặp có thể có, chỉ thay đổi các phần tử từ nhóm thứ hai. Có n 2 cặp như vậy cho phần tử này. Sau đó, chúng tôi lấy phần tử thứ hai từ nhóm đầu tiên và cũng tạo tất cả các cặp có thể có cho nó. Cũng sẽ có n 2 cặp như vậy. Vì chỉ có n 1 phần tử trong nhóm đầu tiên nên sẽ có n 1 * n 2 lựa chọn khả dĩ.

Ví dụ 2 Có thể lập được bao nhiêu số chẵn có ba chữ số từ các chữ số 0, 1, 2, 3, 4, 5, 6 nếu các chữ số đó có thể lặp lại?
Dung dịch: n 1 \ u003d 6 (vì bạn có thể lấy bất kỳ chữ số nào từ 1, 2, 3, 4, 5, 6 làm chữ số đầu tiên), n 2 \ u003d 7 (vì bạn có thể lấy bất kỳ chữ số nào từ 0 làm chữ số thứ hai, 1 , 2, 3, 4, 5, 6), n 3 \ u003d 4 (vì bạn có thể lấy bất kỳ chữ số nào từ 0, 2, 4, 6 làm chữ số thứ ba).
Vì vậy, N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.

Trong trường hợp tất cả các nhóm bao gồm cùng một số phần tử, tức là n 1 = n 2 = ... n k = n chúng ta có thể giả sử rằng mỗi lựa chọn được thực hiện từ cùng một nhóm và phần tử sẽ trở lại nhóm sau lựa chọn. Khi đó số cách chọn bằng n k. Cách chọn này trong tổ hợp được gọi là trả lại mẫu.

Ví dụ 3 Từ các chữ số 1, 5, 6, 7, 8 có thể lập được bao nhiêu số có bốn chữ số khác nhau?
Dung dịch. Mỗi chữ số của số có bốn chữ số đều có năm khả năng xảy ra nên N = 5 * 5 * 5 * 5 = 5 4 = 625.

Xét một tập hợp gồm n phần tử. Tập hợp này trong tổ hợp được gọi là dân số chung.

Số lượng vị trí từ n phần tử theo m

Định nghĩa 1. Chỗ ở từ N các yếu tố của m trong tổ hợp được gọi là bất kỳ đặt hàng đặt từ m các yếu tố khác nhau được chọn từ dân số chung trong N các yếu tố.

Ví dụ 4 Các cách sắp xếp khác nhau của ba phần tử (1, 2, 3) hai phần hai sẽ được các bộ (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2). Các vị trí có thể khác nhau cả về các yếu tố và thứ tự của chúng.

Số lượng vị trí trong tổ hợp được ký hiệu là A n m và được tính theo công thức:

Bình luận: n! = 1 * 2 * 3 * ... * n (đọc là: "en giai thừa"), ngoài ra, giả sử rằng 0! = 1.

Ví dụ 5. Có bao nhiêu số có hai chữ số mà chữ số hàng chục và chữ số hàng đơn vị khác nhau và lẻ?
Dung dịch: tại vì có năm chữ số lẻ là 1, 3, 5, 7, 9, thì bài toán này được rút gọn thành việc chọn và đặt hai trong năm chữ số khác nhau ở hai vị trí khác nhau, tức là các số đã cho sẽ là:

Định nghĩa 2. Sự kết hợp từ N các yếu tố của m trong tổ hợp được gọi là bất kỳ bộ không có thứ tự từ m các yếu tố khác nhau được chọn từ dân số chung trong N các yếu tố.

Ví dụ 6. Đối với tập hợp (1, 2, 3), các kết hợp là (1, 2), (1, 3), (2, 3).

Số tổ hợp của n phần tử theo m

Số tổ hợp được ký hiệu là C n m và được tính theo công thức:

Ví dụ 7 Người đọc có thể chọn hai cuốn sách trong số sáu cuốn sách có sẵn bằng bao nhiêu cách?

Dung dịch: Số cách bằng số kết hợp của sáu cuốn sách với hai, tức là bằng:

Hoán vị của n phần tử

Định nghĩa 3. Hoán vị từ N phần tử được gọi là bất kỳ đặt hàng đặt các yếu tố này.

Ví dụ 7a. Tất cả các hoán vị có thể có của một tập hợp gồm ba phần tử (1, 2, 3) là: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , (3, 2, 1), (3, 1, 2).

Số các hoán vị khác nhau của n phần tử được ký hiệu là P n và được tính theo công thức P n = n !.

Ví dụ 8 Có bao nhiêu cách xếp bảy cuốn sách của các tác giả khác nhau thành một hàng trên một giá?

Dung dịch: Bài toán này là về số hoán vị của bảy cuốn sách khác nhau. Có P 7 = 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040 cách sắp xếp sách.

Thảo luận. Chúng tôi thấy rằng số lượng các kết hợp có thể có có thể được tính toán theo các quy tắc khác nhau (hoán vị, kết hợp, vị trí) và kết quả sẽ khác nhau, bởi vì nguyên tắc đếm và bản thân các công thức là khác nhau. Xem xét kỹ các định nghĩa, bạn có thể thấy rằng kết quả phụ thuộc vào một số yếu tố cùng một lúc.

Thứ nhất, từ bao nhiêu phần tử chúng ta có thể kết hợp các tập hợp của chúng (tổng thể lớn của các phần tử là bao nhiêu).

Thứ hai, kết quả phụ thuộc vào kích thước tập hợp phần tử chúng ta cần.

Cuối cùng, điều quan trọng là phải biết liệu thứ tự của các phần tử trong tập hợp có quan trọng đối với chúng ta hay không. Hãy để chúng tôi giải thích yếu tố cuối cùng với ví dụ sau.

Ví dụ 9 Có 20 người trong cuộc họp phụ huynh. Có bao nhiêu lựa chọn khác nhau cho thành phần của ủy ban phụ huynh nếu nó nên bao gồm 5 người?
Dung dịch: Trong ví dụ này, chúng tôi không quan tâm đến thứ tự của các tên trong danh sách ủy ban. Kết quả là, nếu những người giống nhau xuất hiện trong thành phần của nó, thì về mặt ý nghĩa đối với chúng tôi, đây là một lựa chọn tương tự. Do đó, chúng ta có thể sử dụng công thức để tính số sự kết hợp trong số 20 phần tử, 5.

Mọi chuyện sẽ khác nếu ban đầu mỗi thành viên của ủy ban chịu trách nhiệm về một lĩnh vực công việc nhất định. Sau đó, với cùng một biên chế của ủy ban, có thể có 5 người bên trong nó! tùy chọn hoán vị chuyện đó. Số lượng các lựa chọn khác nhau (cả về thành phần và lĩnh vực trách nhiệm) được xác định trong trường hợp này bằng số vị trí trong số 20 phần tử, 5.

Nhiệm vụ tự kiểm tra
1. Từ các chữ số 0, 1, 2, 3, 4, 5, 6 có thể lập được bao nhiêu số chẵn có ba chữ số khác nhau nếu các số đó có thể lặp lại?

2. Có bao nhiêu số có năm chữ số đọc giống nhau từ trái sang phải và từ phải sang trái?

3. Có mười môn học trong lớp và năm bài học một ngày. Bạn có thể lập thời gian biểu cho một ngày bằng bao nhiêu cách?

4. Có bao nhiêu cách chọn 4 đại biểu cho đại hội nếu có 20 người trong nhóm?

5. Có bao nhiêu cách có thể cho tám lá thư khác nhau vào tám phong bì khác nhau nếu mỗi phong bì chỉ có một lá thư?

6. Từ ba nhà toán học và mười nhà kinh tế, cần phải lập một ủy ban bao gồm hai nhà toán học và sáu nhà kinh tế. Điều này có thể được thực hiện bằng bao nhiêu cách?

Cần lưu ý rằng tổ hợp là một phần độc lập của toán học cao hơn (và không phải là một phần của terver) và các sách giáo khoa có trọng lượng đã được viết trong môn học này, nội dung của nó, đôi khi, không dễ hơn đại số trừu tượng. Tuy nhiên, một phần nhỏ kiến ​​thức lý thuyết sẽ là đủ cho chúng ta, và trong bài viết này tôi sẽ cố gắng phân tích những điều cơ bản của chủ đề với các bài toán tổ hợp điển hình dưới dạng dễ tiếp cận. Và nhiều bạn sẽ giúp tôi ;-)

Chúng ta sẽ làm gì? Theo nghĩa hẹp, tổ hợp là phép tính các tổ hợp khác nhau có thể được tạo ra từ một tập hợp nhất định rời rạc các đối tượng. Vật thể được hiểu là bất kỳ vật thể hoặc sinh vật sống biệt lập nào - người, động vật, nấm, thực vật, côn trùng, v.v. Đồng thời, tổ hợp không quan tâm chút nào rằng bộ gồm có một đĩa bột báng, một mỏ hàn và một con ếch đầm lầy. Về cơ bản, điều quan trọng là các đối tượng này có thể đếm được - có ba trong số chúng. (rời rạc) và điều cốt yếu là không cái nào giống nhau.

Với rất nhiều thứ được sắp xếp, bây giờ là về sự kết hợp. Các kiểu kết hợp phổ biến nhất là hoán vị của các đối tượng, sự lựa chọn của chúng từ một tập hợp (kết hợp) và phân phối (sắp xếp). Hãy xem điều này xảy ra như thế nào ngay bây giờ:

Hoán vị, kết hợp và vị trí không lặp lại

Đừng sợ các thuật ngữ khó hiểu, đặc biệt là vì một số trong số chúng thực sự không thành công lắm. Hãy bắt đầu với phần đuôi của tiêu đề - cái gì " không lặp lại”? Điều này có nghĩa là trong phần này, chúng tôi sẽ xem xét các bộ bao gồm nhiều các đối tượng. Ví dụ, ... không, tôi sẽ không cung cấp cháo với mỏ hàn và ếch, món nào ngon hơn thì ngon hơn =) Hãy tưởng tượng rằng một quả táo, một quả lê và một quả chuối hiện lên trên bàn trước mặt bạn (nếu có bất kỳ, tình huống có thể được mô phỏng và thực tế). Chúng tôi xếp các loại trái cây từ trái sang phải theo thứ tự sau:

táo / lê / chuối

Câu hỏi một: Có bao nhiêu cách sắp xếp lại chúng?

Một kết hợp đã được viết ở trên và không có vấn đề gì với phần còn lại:

táo / chuối / lê
lê / táo / chuối
lê / chuối / táo
chuối / táo / lê
chuối / lê / táo

Tổng cộng: 6 kết hợp hoặc 6 hoán vị.

Chà, không khó để liệt kê tất cả các trường hợp có thể xảy ra ở đây, nhưng nếu có nhiều mục hơn thì sao? Đã có bốn loại trái cây khác nhau, số lượng kết hợp sẽ tăng lên đáng kể!

Vui lòng mở tài liệu tham khảo (Sách hướng dẫn dễ in) và trong đoạn số 2, hãy tìm công thức cho số các hoán vị.

Không bị dày vò - 3 đối tượng có thể được sắp xếp lại theo các cách.

Câu hỏi hai: Có bao nhiêu cách chọn a) một quả, b) hai quả, c) ba quả, d) ít nhất một quả?

Tại sao chọn? Vì vậy, họ đã tạo ra cảm giác thèm ăn trong đoạn trước - để ăn! =)

a) Rõ ràng là có thể chọn một loại trái cây theo ba cách - chọn một quả táo, một quả lê, hoặc một quả chuối. Số lượng chính thức dựa trên công thức cho số lượng kết hợp:

Mục từ trong trường hợp này nên được hiểu như sau: "Bạn có thể chọn 1 trong ba loại quả bằng bao nhiêu cách?"

b) Chúng tôi liệt kê tất cả các kết hợp có thể có của hai loại trái cây:

táo và lê;
táo và chuối;
lê và chuối.

Số lượng kết hợp dễ dàng kiểm tra bằng cách sử dụng cùng một công thức:

Mục từ được hiểu tương tự: “Bạn có thể chọn 2 trong 3 loại quả bằng bao nhiêu cách?”.

c) Và cuối cùng, ba loại trái cây có thể được chọn theo một cách duy nhất:

Nhân tiện, công thức cho số lượng kết hợp cũng có ý nghĩa đối với một mẫu trống:
Bằng cách này, bạn không thể chọn một loại trái cây nào - trên thực tế, bạn không cần lấy gì cả.

d) Bạn có thể thực hiện bao nhiêu cách ít nhất một trái cây? Điều kiện “ít nhất một” ngụ ý rằng chúng ta hài lòng với 1 quả (bất kỳ) hoặc 2 quả bất kỳ hoặc cả 3 quả:
cách bạn có thể chọn ít nhất một loại trái cây.

Những độc giả đã nghiên cứu kỹ bài học giới thiệu trên lý thuyết xác suấtđã tìm ra một cái gì đó. Nhưng về ý nghĩa của dấu cộng sau này.

Để trả lời câu hỏi tiếp theo, mình cần 2 người xung phong ... ... À, vì không ai muốn nên mình sẽ gọi lên ban quản trị =)

Câu hỏi ba: Có bao nhiêu cách có thể phân phát một quả cho Dasha và Natasha?

Để phân phối hai trái cây, trước tiên bạn phải chọn chúng. Theo đoạn "be" của câu hỏi trước, điều này có thể được thực hiện theo nhiều cách, tôi sẽ viết lại chúng một lần nữa:

táo và lê;
táo và chuối;
lê và chuối.

Nhưng bây giờ sẽ có số lượng kết hợp nhiều gấp đôi. Ví dụ, hãy xem xét cặp trái cây đầu tiên:
bạn có thể đãi Dasha bằng một quả táo, và Natasha bằng một quả lê;
hoặc ngược lại - Dasha sẽ nhận được quả lê, và Natasha sẽ nhận được quả táo.

Và hoán vị như vậy là có thể xảy ra đối với mọi cặp quả.

Hãy xem xét cùng một nhóm học sinh đã đi khiêu vũ. Có bao nhiêu cách ghép đôi trai gái?

Cách bạn có thể chọn 1 chàng trai trẻ;
cách bạn có thể chọn 1 cô gái.

Vì vậy, một người đàn ông trẻ và một cô gái có thể được chọn: các cách.

Khi 1 đối tượng được chọn từ mỗi tập hợp, thì nguyên tắc đếm kết hợp sau là hợp lệ: " mỗi một đối tượng từ một tập hợp có thể tạo thành một cặp với mọiđối tượng của tập hợp khác.

Tức là, Oleg có thể mời bất kỳ cô gái nào trong số 13 cô gái khiêu vũ, Evgeny - cũng là bất kỳ cô gái nào trong số mười ba người, và những người trẻ khác cũng có lựa chọn tương tự. Tổng số: các cặp có thể.

Cần lưu ý rằng trong ví dụ này, "lịch sử" của sự hình thành cặp không quan trọng; tuy nhiên, nếu tính đến sự chủ động, thì số lượng kết hợp phải tăng gấp đôi, vì mỗi cô gái trong số 13 cô gái cũng có thể mời bất kỳ chàng trai nào khiêu vũ. Tất cả phụ thuộc vào các điều kiện của một nhiệm vụ cụ thể!

Một nguyên tắc tương tự cũng có giá trị đối với các kết hợp phức tạp hơn, ví dụ: có bao nhiêu cách có thể chọn hai thanh niên và hai cô gái tham gia một tiểu phẩm KVN?

liên hiệp Và gợi ý rõ ràng rằng các kết hợp phải được nhân:

Các nhóm nghệ sĩ có thể có.

Nói cách khác, mỗi các cặp trai (45 cặp duy nhất) có thể cạnh tranh với không tí nào một vài cô gái (78 cặp đôi độc nhất vô nhị). Và nếu chúng ta xem xét sự phân bổ vai trò giữa những người tham gia, thì sẽ có nhiều sự kết hợp hơn nữa. ... Rất muốn, nhưng vẫn sẽ không tiếp tục nữa, để khỏi truyền cho các bạn cái ác cảm về cuộc sống sinh viên =).

Quy tắc nhân áp dụng cho nhiều cấp số nhân hơn:

Nhiệm vụ 8

Có bao nhiêu số có ba chữ số mà chia hết cho 5?

Dung dịch: để rõ ràng, chúng tôi biểu thị số này bằng ba dấu hoa thị: ***

TẠI hàng trăm nơi bạn có thể viết bất kỳ số nào (1, 2, 3, 4, 5, 6, 7, 8 hoặc 9). Số 0 là không tốt, vì trong trường hợp này số không còn là ba chữ số.

Nhưng trong hàng chục(“Ở giữa”) bạn có thể chọn bất kỳ chữ số nào trong số 10 chữ số:.

Theo điều kiện, số đó phải chia hết cho 5. Số chia hết cho 5 nếu nó kết thúc bằng 5 hoặc 0. Như vậy, ở chữ số có nghĩa nhỏ nhất, ta thỏa mãn 2 chữ số.

Tổng cộng, có: các số có ba chữ số chia hết cho 5.

Đồng thời, tác phẩm được giải mã như sau: “9 cách bạn có thể chọn một số trong hàng trăm nơi và 10 cách để chọn một số trong hàng chục và 2 cách trong đơn vị chữ số»

Hoặc đơn giản hơn: mỗi từ 9 chữ số đến hàng trăm nơi kết hợp với mỗi 10 chữ số hàng chục và với mỗi gồm hai chữ số đơn vị chữ số».

Câu trả lời: 180

Và bây giờ…

Vâng, tôi gần như quên mất phần bình luận đã hứa cho vấn đề số 5, trong đó Borya, Dima và Volodya có thể được chia mỗi người một lá bài theo những cách khác nhau. Phép nhân ở đây có nghĩa tương tự: theo cách bạn có thể rút ra 3 lá bài từ bộ bài Và trong mỗi mẫu để sắp xếp lại chúng theo cách.

Và bây giờ là vấn đề cho một giải pháp độc lập ... bây giờ tôi sẽ nghĩ ra một cái gì đó thú vị hơn, ... hãy nói về cùng một phiên bản blackjack của Nga:

Nhiệm vụ 9

Có bao nhiêu kết hợp chiến thắng của 2 thẻ trong một trò chơi "điểm"?

Đối với những người chưa biết: thắng kết hợp 10 + ACE (11 điểm) = 21 điểm và, hãy xem xét kết hợp chiến thắng của hai quân át chủ bài.

(thứ tự của các thẻ trong bất kỳ cặp nào không quan trọng)

Lời giải ngắn gọn và đáp án ở cuối bài.

Nhân tiện, không cần thiết phải xem xét một ví dụ nguyên thủy. Blackjack gần như là trò chơi duy nhất có một thuật toán hợp lý về mặt toán học cho phép bạn đánh bại sòng bạc. Những người muốn có thể dễ dàng tìm thấy nhiều thông tin về chiến lược và chiến thuật tối ưu. Đúng thật, những cao thủ như vậy nhanh chóng lọt vào danh sách đen của tất cả các cơ sở =)

Đã đến lúc củng cố tài liệu bao gồm một số nhiệm vụ vững chắc:

Nhiệm vụ 10

Vasya có 4 con mèo ở nhà.

a) Có bao nhiêu cách xếp những con mèo vào các góc phòng?
b) Có bao nhiêu cách cho phép mèo đi lang thang?
c) Vasya có thể nhặt được hai con mèo (con bên trái, con bên phải) bằng bao nhiêu cách?

Chúng tôi quyết định: đầu tiên, một lần nữa cần lưu ý rằng vấn đề là về khác nhauđồ vật (ngay cả khi những con mèo là anh em sinh đôi giống hệt nhau). Đây là một điều kiện rất quan trọng!

a) Sự im lặng của mèo. Việc thực thi này tuân theo tất cả các con mèo cùng một lúc
+ vị trí của chúng là quan trọng, vì vậy có hoán vị ở đây:
những cách bạn có thể cho mèo ngồi ở các góc phòng.

Tôi nhắc lại rằng khi hoán vị, chỉ có số lượng các đối tượng khác nhau và vị trí tương đối của chúng là quan trọng. Tùy thuộc vào tâm trạng của mình, Vasya có thể đặt các con vật thành hình bán nguyệt trên ghế sofa, thành hàng trên bệ cửa sổ, v.v. - sẽ có 24 hoán vị trong mọi trường hợp. Để thuận tiện, những ai muốn có thể tưởng tượng rằng những con mèo có nhiều màu (ví dụ: trắng, đen, đỏ và sọc) và liệt kê tất cả các kết hợp có thể có.

b) Có bao nhiêu cách cho phép mèo đi lang thang?

Người ta cho rằng mèo chỉ đi dạo qua cửa, trong khi câu hỏi ám chỉ sự thờ ơ về số lượng động vật - 1, 2, 3 hoặc cả 4 con mèo có thể đi dạo.

Chúng tôi xem xét tất cả các kết hợp có thể có:

Cách bạn có thể thả mèo đi dạo (bất kỳ cách nào trong bốn cách);
những cách bạn có thể để hai con mèo đi dạo (tự liệt kê các lựa chọn);
cách bạn có thể để ba con mèo đi dạo (một trong bốn con ngồi ở nhà);
cách bạn có thể thả tất cả những con mèo.

Bạn có thể đoán rằng các giá trị thu được phải được tổng hợp:
cách để cho mèo đi dạo.

Đối với những người đam mê, tôi đưa ra một phiên bản phức tạp của vấn đề - khi bất kỳ con mèo nào trong bất kỳ mẫu nào cũng có thể ngẫu nhiên đi ra ngoài, cả qua cửa và qua cửa sổ của tầng 10. Sẽ có nhiều sự kết hợp hơn!

c) Vasya có thể nhặt được hai con mèo bằng bao nhiêu cách?

Tình huống không chỉ liên quan đến việc lựa chọn 2 con vật mà còn cả vị trí của chúng trên tay:
cách bạn có thể nhặt được 2 con mèo.

Giải pháp thứ hai: theo những cách bạn có thể chọn hai con mèo và cách trồng mọi một vài trong tay:

Câu trả lời: a) 24, b) 15, c) 12

Vâng, để thanh minh lương tâm của tôi, một cái gì đó cụ thể hơn về phép nhân các tổ hợp .... Để Vasya có thêm 5 con mèo =) Có bao nhiêu cách để bạn có thể cho 2 con mèo đi dạo và 1 con mèo?

Đó là, với mỗi một vài con mèo có thể được thả mọi con mèo.

Một nút accordion khác cho một giải pháp độc lập:

Nhiệm vụ 11

3 hành khách vào thang máy của tòa nhà 12 tầng. Tất cả mọi người, độc lập với những người khác, có thể thoát ra từ bất kỳ tầng nào (bắt đầu từ tầng 2) với cùng một xác suất. Có bao nhiêu cách:

1) Hành khách có thể xuống cùng một tầng (thoát lệnh không thành vấn đề);
2) hai người có thể xuống trên một tầng và một người thứ ba ở tầng khác;
3) mọi người có thể xuống ở các tầng khác nhau;
4) Hành khách có thể ra khỏi thang máy không?

Và ở đây họ thường hỏi lại, tôi nói rõ: nếu 2 hoặc 3 người cùng đi ra một tầng thì thứ tự xuất cảnh không thành vấn đề. SUY NGHĨ, sử dụng các công thức và quy tắc cho các kết hợp cộng / nhân. Trong trường hợp gặp khó khăn, hành khách sẽ hữu ích khi nêu tên và lý do để họ có thể ra khỏi thang máy bằng những cách kết hợp nào. Không cần phải bực bội nếu điều gì đó không suôn sẻ, chẳng hạn như điểm số 2 là khá quỷ quyệt.

Giải pháp hoàn chỉnh với nhận xét chi tiết ở cuối hướng dẫn.

Đoạn cuối dành cho các tổ hợp cũng xảy ra khá thường xuyên - theo đánh giá chủ quan của mình thì trong khoảng 20 - 30% các bài tổ hợp:

Hoán vị, kết hợp và vị trí có lặp lại

Các kiểu kết hợp được liệt kê được nêu trong đoạn số 5 của tài liệu tham khảo Các công thức cơ bản của tổ hợp, tuy nhiên, một số trong số chúng có thể không rõ ràng lắm khi đọc lần đầu. Trong trường hợp này, trước tiên bạn nên làm quen với các ví dụ thực tế và chỉ sau đó mới hiểu được công thức tổng quát. Đi:

Hoán vị có lặp lại

Trong hoán vị có lặp lại, như trong hoán vị "thông thường", toàn bộ các đối tượng cùng một lúc, nhưng có một điều: trong tập hợp này, một hoặc nhiều phần tử (đối tượng) được lặp lại. Đáp ứng tiêu chuẩn tiếp theo:

Nhiệm vụ 12

Có thể thu được bao nhiêu tổ hợp chữ cái khác nhau bằng cách sắp xếp lại các thẻ có các chữ cái sau: K, O, L, O, K, O, L, L, H, I, K?

Dung dịch: trong trường hợp tất cả các chữ cái khác nhau, thì một công thức nhỏ nên được áp dụng, tuy nhiên, rõ ràng là đối với bộ thẻ được đề xuất, một số thao tác sẽ hoạt động "nhàn rỗi", vì vậy, ví dụ: nếu bạn hoán đổi hai thẻ bất kỳ. thẻ với các chữ cái "K trong bất kỳ từ nào, nó sẽ là từ tương tự. Hơn nữa, về mặt vật lý, các thẻ có thể rất khác nhau: một thẻ có thể là hình tròn với chữ “K” được in sẵn, thẻ còn lại là hình vuông với chữ “K” được vẽ sẵn. Nhưng theo ý nghĩa của vấn đề, ngay cả những thẻ như vậy được coi là giống nhau, vì điều kiện hỏi về các kết hợp chữ cái.

Mọi thứ cực kỳ đơn giản - tổng cộng: 11 thẻ, bao gồm chữ cái:

K - lặp lại 3 lần;
O - lặp lại 3 lần;
L - lặp lại 2 lần;
b - lặp lại 1 lần;
H - lặp lại 1 lần;
Và - lặp lại 1 lần.

Kiểm tra: 3 + 3 + 2 + 1 + 1 + 1 = 11, đó là những gì chúng tôi muốn kiểm tra.

Theo công thức số hoán vị có lặp lại:
các kết hợp chữ cái khác nhau có thể được lấy. Hơn nửa triệu!

Để tính toán nhanh một giá trị giai thừa lớn, thật tiện lợi khi sử dụng hàm Excel tiêu chuẩn: chúng tôi cho điểm trong bất kỳ ô nào = SỰ THẬT (11) và bấm vào đi vào.

Trên thực tế, có thể chấp nhận được việc không viết ra công thức chung và ngoài ra, bỏ qua các thừa số đơn vị:

Nhưng nhận xét sơ bộ về các bức thư được lặp lại là bắt buộc!

Câu trả lời: 554400

Một ví dụ điển hình khác về hoán vị có lặp lại trong bài toán sắp xếp các quân cờ, bạn có thể tham khảo tại kho giải pháp làm sẵn trong pdf tương ứng. Và đối với một giải pháp độc lập, tôi đã nghĩ ra một nhiệm vụ ít mẫu hơn:

Nhiệm vụ 13

Alexey tập thể thao và 4 ngày một tuần - điền kinh, 2 ngày - tập sức mạnh và 1 ngày nghỉ ngơi. Anh ta có thể sắp xếp các lớp học hàng tuần của mình bằng bao nhiêu cách?

Công thức không hoạt động ở đây vì nó tính đến các hoán vị chồng chéo (ví dụ: khi các bài tập sức mạnh vào thứ Tư được hoán đổi với bài tập sức mạnh vào thứ năm). Và một lần nữa - trên thực tế, 2 buổi tập sức mạnh giống nhau có thể rất khác nhau, nhưng trong bối cảnh của nhiệm vụ (về lịch trình), chúng được coi là những yếu tố giống nhau.

Lời giải hai dòng và đáp án cuối bài.

Kết hợp với lặp lại

Đặc điểm nổi bật của kiểu kết hợp này là mẫu được lấy từ nhiều nhóm, mỗi nhóm gồm các đối tượng giống nhau.

Hôm nay mọi người đều làm việc chăm chỉ, vì vậy đã đến lúc làm mới bản thân:

Nhiệm vụ 14

Nhà ăn sinh viên bán xúc xích dưới dạng bột, bánh pho mát và bánh rán. Có bao nhiêu cách mua năm cái bánh?

Dung dịch: ngay lập tức chú ý đến tiêu chí điển hình cho các kết hợp có lặp lại - theo điều kiện, không phải một tập hợp các đối tượng như vậy, nhưng các loại khác nhau các đối tượng; người ta cho rằng có ít nhất năm xúc xích, 5 bánh pho mát và 5 bánh rán được bán. Tất nhiên, bánh ở mỗi nhóm là khác nhau - vì bánh rán hoàn toàn giống hệt nhau chỉ có thể được mô phỏng trên máy tính =) Tuy nhiên, đặc điểm vật lý của bánh không phải là yếu tố cần thiết cho ý nghĩa của vấn đề, và xúc xích / bánh pho mát / bánh rán trong các nhóm của họ được coi là như nhau.

Những gì có thể được trong mẫu? Trước hết, cần lưu ý rằng chắc chắn sẽ có những chiếc bánh giống hệt nhau trong mẫu (vì chúng tôi chọn 5 chiếc và 3 loại được cung cấp để bạn lựa chọn). Các lựa chọn ở đây cho mọi khẩu vị: 5 xúc xích, 5 bánh pho mát, 5 bánh rán, 3 xúc xích + 2 bánh pho mát, 1 xúc xích + 2 + bánh pho mát + 2 bánh donut, v.v.

Như với các kiểu kết hợp "thông thường", thứ tự lựa chọn và vị trí của bánh nướng trong mẫu không quan trọng - họ chỉ chọn 5 miếng và thế là xong.

Chúng tôi sử dụng công thức số lượng kết hợp có lặp lại:
cách bạn có thể mua 5 cái bánh.

Ăn ngon miệng nhé!

Câu trả lời: 21

Có thể rút ra kết luận gì từ nhiều bài toán tổ hợp?

Đôi khi, điều khó khăn nhất là hiểu được tình trạng bệnh.

Một ví dụ tương tự cho giải pháp tự làm:

Nhiệm vụ 15

Ví chứa một số lượng khá lớn tiền xu 1-, 2-, 5- và 10 rúp. Có bao nhiêu cách có thể lấy ba đồng ra khỏi ví?

Vì mục đích tự chủ, hãy trả lời một số câu hỏi đơn giản:

1) Tất cả các đồng xu trong mẫu có thể khác nhau không?
2) Đặt tên cho sự kết hợp "rẻ nhất" và "đắt nhất" của các đồng tiền.

Lời giải và đáp án cuối bài.

Từ kinh nghiệm cá nhân của tôi, tôi có thể nói rằng các kết hợp có lặp lại là khách hiếm nhất trong thực tế, điều này không thể nói về các loại kết hợp sau:

Vị trí lặp lại

Từ một tập hợp bao gồm các phần tử, các phần tử được chọn và thứ tự của các phần tử trong mỗi mẫu là quan trọng. Và mọi thứ sẽ ổn, nhưng một trò đùa khá bất ngờ là chúng ta có thể chọn bất kỳ đối tượng nào của bộ gốc bao nhiêu lần tùy thích. Nói một cách hình tượng, từ "vô số sẽ không giảm."

Khi nào nó xảy ra? Ví dụ điển hình là khóa kết hợp với nhiều đĩa, nhưng do sự phát triển của công nghệ, nên xem xét hậu duệ kỹ thuật số của nó là phù hợp hơn:

Nhiệm vụ 16

Có bao nhiêu mã pin gồm 4 chữ số?

Dung dịch: thực ra để giải bài toán chỉ cần biết quy luật tổ hợp là đủ: có thể chọn chữ số đầu tiên của mã pin theo các cách và cách - chữ số thứ hai của mã pin và theo nhiều cách - một phần ba và càng nhiều - cái thứ tư. Do đó, theo quy tắc nhân các kết hợp, một mã pin có bốn chữ số có thể được tạo thành: theo các cách.

Và bây giờ với công thức. Theo điều kiện, chúng tôi được cung cấp một bộ số, từ đó các số được chọn và đặt theo một thứ tự nhất định, trong khi các con số trong mẫu có thể được lặp lại (tức là bất kỳ chữ số nào của tập hợp ban đầu có thể được sử dụng với số lần tùy ý). Theo công thức cho số lượng vị trí có lặp lại:

Câu trả lời: 10000

Điều đáng chú ý ở đây là ... ... nếu máy ATM "ăn" thẻ sau lần thứ ba không thành công để nhập mã pin, thì cơ hội nhặt được nó ngẫu nhiên là rất hão huyền.

Và ai đã nói rằng không có ý nghĩa thực tế trong tổ hợp? Một nhiệm vụ nhận thức cho tất cả người đọc của trang web:

Bài toán 17

Theo tiêu chuẩn của nhà nước, biển số xe ô tô bao gồm 3 số và 3 chữ cái. Trong trường hợp này, một số có ba số không không được phép và các chữ cái được chọn từ tập hợp A, B, E, K, M, H, O, R, C, T, U, X (chỉ những chữ cái Kirin đó mới được sử dụng, cách viết của nó khớp với các chữ cái Latinh).

Có bao nhiêu biển số xe khác nhau có thể được tạo cho một khu vực?

Không phải vậy, nhân tiện, và rất nhiều. Ở các khu vực rộng lớn, con số này là không đủ, và do đó đối với họ, có một số mã cho dòng chữ RUS.

Lời giải và đáp án cuối bài. Đừng quên sử dụng các quy tắc tổ hợp ;-)… Tôi muốn khoe khoang về việc độc quyền, nhưng hóa ra không phải là độc quyền =) Tôi đã xem Wikipedia - có những phép tính ở đó, tuy nhiên, không có bình luận. Mặc dù vì mục đích giáo dục, nhưng có lẽ, ít người giải quyết nó.

Bài học hấp dẫn của chúng ta đã kết thúc, và cuối cùng tôi muốn nói rằng bạn đã không lãng phí thời gian của mình - vì lý do các công thức tổ hợp tìm thấy một ứng dụng thực tế quan trọng khác: chúng được tìm thấy trong các nhiệm vụ khác nhau trên lý thuyết xác suất,
và trong nhiệm vụ về định nghĩa cổ điển của xác suất- đặc biệt thường xuyên

Cảm ơn tất cả các bạn đã tham gia tích cực và hẹn gặp lại!

Giải pháp và câu trả lời:

Nhiệm vụ 2: Dung dịch: tìm số tất cả các hoán vị có thể có của 4 thẻ:

Khi một thẻ có số 0 ở vị trí đầu tiên, con số sẽ trở thành ba chữ số, vì vậy những kết hợp này nên bị loại trừ. Đặt số 0 ở vị trí thứ nhất thì 3 chữ số còn lại trong các chữ số có nghĩa nhỏ nhất có thể được sắp xếp lại theo các cách.

Ghi chú : tại vì có rất ít thẻ, có thể dễ dàng liệt kê tất cả các tùy chọn như vậy ở đây:
0579
0597
0759
0795
0957
0975

Do đó, từ tập hợp được đề xuất, bạn có thể thực hiện:
24 - 6 = 18 số có bốn chữ số
Câu trả lời : 18

Nhiệm vụ 4: Dung dịch: Có thể chọn 3 thẻ trong 36 cách.
Câu trả lời : 7140

Nhiệm vụ 6: Dung dịch: các cách.
Giải pháp khác : các cách bạn có thể chọn hai người từ nhóm và và
2) Bộ "rẻ nhất" chứa 3 đồng rúp và bộ "đắt" nhất chứa 3 đồng 10 rúp.

Nhiệm vụ 17: Dung dịch: những cách bạn có thể tạo sự kết hợp kỹ thuật số của một biển số xe, trong khi một trong số chúng (000) nên được loại trừ:.
cách bạn có thể tạo tổ hợp chữ cái của một số ô tô.
Theo quy tắc nhân các kết hợp, mọi thứ có thể được tạo thành:
số xe
(mỗi kết hợp kỹ thuật số kết hợp với mỗi kết hợp chữ cái).
Câu trả lời : 1726272

Để dễ dàng hơn trong việc điều hướng tài liệu, tôi sẽ bổ sung nội dung của chủ đề này:

Giới thiệu. Bộ và lựa chọn.

Trong chủ đề này, chúng ta sẽ xem xét các khái niệm cơ bản của tổ hợp: hoán vị, tổ hợp và vị trí. Hãy cùng tìm hiểu bản chất và công thức của chúng để bạn có thể tìm ra số hiệu của chúng.

Để bắt đầu, chúng tôi cần một số thông tin cơ bản. Hãy bắt đầu với một khái niệm toán học cơ bản như một tập hợp. Khái niệm tập hợp đã được mô tả chi tiết trong chuyên đề "Khái niệm tập hợp. Các phương pháp xác định tập hợp".

Một câu chuyện rất ngắn về vô số: hiện an

Tóm lại, một tập hợp là một tập hợp các đối tượng. Tập hợp được viết trong dấu ngoặc nhọn. Thứ tự mà các phần tử được viết không quan trọng; sự lặp lại của các phần tử không được phép. Ví dụ: tập hợp các chữ số của số 11115555999 sẽ là: $ \ (1,5,9 \) $. Bộ chữ cái phụ âm trong từ "hổ con" như sau: $ \ (t, r, r, n, k \) $. Ký hiệu $ 5 \ trong A $ có nghĩa là phần tử 5 thuộc tập hợp $ A = \ (1,5,9 \) $. Số phần tử trong một tập hợp hữu hạn được gọi là sức mạnh của tập hợp này và được ký hiệu là $ | A | $. Ví dụ, với một tập hợp $ A = \ (1,5,9 \) $ chứa 3 phần tử, ta có: $ | A | = 3 $.

Ta xét một số tập hợp hữu hạn khác rỗng $ U $, tổng số của nó bằng $ n $, $ | U | = n $ (nghĩa là tập $ U $ có $ n $ phần tử). Hãy để chúng tôi giới thiệu một khái niệm như vật mẫu(một số tác giả gọi nó là tuple). Theo mẫu có kích thước $ k $ trong số $ n $ phần tử (viết tắt là $ (n, k) $ - lựa chọn), chúng tôi có nghĩa là một tập hợp các phần tử $ (a_1, a_2, \ ldots, a_k) $, trong đó $ a_i \ in U $. Một lựa chọn được cho là có thứ tự nếu thứ tự của các phần tử được chỉ định trong đó. Hai mẫu có thứ tự chỉ khác nhau về thứ tự của các phần tử là khác biệt. Nếu thứ tự của các phần tử của mẫu không có ý nghĩa thì mẫu đó được gọi là không có thứ tự.

Lưu ý rằng định nghĩa lựa chọn không nói gì về việc lặp lại mục. Không giống như các phần tử tập hợp, các phần tử lựa chọn có thể được lặp lại.

Ví dụ, hãy xem xét tập hợp $ U = \ (a, b, c, d, e \) $. Tập hợp $ U $ chứa 5 phần tử, tức là $ | Ư | = 5 $. Một mẫu không có lặp lại có thể là: $ (a, b, c) $. Mẫu này chứa 3 phần tử, tức là kích thước của mẫu này là 3. Nói cách khác, đây là mẫu $ (5,3) $.

Một mẫu có các lần lặp lại có thể là: $ (a, a, a, a, a, c, c, d) $. Nó chứa 8 phần tử, tức là khối lượng của nó là 8. Nói cách khác, đây là một mẫu $ (5,8) $.

Xét thêm hai mẫu $ (5,3) $ -: $ (a, b, b) $ và $ (b, a, b) $. Nếu chúng ta giả sử rằng các mẫu của chúng ta không có thứ tự, thì mẫu $ (a, b, b) $ bằng với mẫu $ (b, a, b) $, tức là $ (a, b, b) = (b, a, b) $. Nếu chúng ta giả sử các mẫu của chúng ta được đặt hàng, thì $ (a, b, b) \ neq (b, a, b) $.

Hãy xem một ví dụ khác, ít trừu tượng hơn một chút :) Giả sử có sáu viên kẹo trong một giỏ, và tất cả chúng đều khác nhau. Nếu viên kẹo đầu tiên được gán là số 1, viên kẹo thứ hai là số 2, v.v. thì tập hợp sau có thể được liên kết với các viên kẹo trong giỏ: $ U = \ (1,2,3,4,5 , 6 \) $. Hãy tưởng tượng rằng chúng ta cho tay vào rổ một cách ngẫu nhiên để lấy ra ba chiếc kẹo. Kẹo kéo ra - đây là mẫu. Vì chúng ta lấy ra 3 cái kẹo từ 6 cái, nên chúng ta nhận được một (6,3) -mẫu. Thứ tự đặt viên kẹo trong lòng bàn tay hoàn toàn không liên quan nên mẫu này không có thứ tự. Vâng, và vì tất cả các loại kẹo đều khác nhau, nên mẫu không có sự lặp lại. Vì vậy, trong tình huống này, chúng ta đang nói về một sự lựa chọn không có thứ tự (6,3) mà không có sự lặp lại.

Bây giờ chúng ta hãy đi từ phía bên kia. Hãy tưởng tượng rằng chúng ta đang ở trong một nhà máy sản xuất kẹo, và nhà máy này sản xuất bốn loại kẹo. Tập hợp $ U $ trong tình huống này như sau: $ U = \ (1,2,3,4 \) $ (mỗi chữ số chịu trách nhiệm về loại kẹo riêng của nó). Bây giờ hãy tưởng tượng rằng tất cả đồ ngọt được đổ vào một máng duy nhất, gần nơi chúng ta đang đứng. Và, thay thế lòng bàn tay, chúng tôi chọn 20 kẹo từ luồng này. Kẹo trong một số ít - đây là mẫu. Thứ tự của những viên kẹo trong tay có đóng một vai trò nào không? Đương nhiên, không, vì vậy mẫu không có thứ tự. Chỉ có 4 loại đồ ngọt và chúng tôi chọn ra 20 loại từ quy trình chung - việc lặp lại các loại là không thể tránh khỏi. Đồng thời, các mẫu có thể rất khác nhau: chúng ta thậm chí có thể có tất cả các loại kẹo cùng loại. Do đó, trong tình huống này, chúng ta đang đối phó với một sự phân tích không theo thứ tự (4.20) với sự lặp lại.

Hãy xem xét thêm một vài ví dụ. Cho 7 chữ cái khác nhau được viết trên các khối lập phương: k, o, n, f, e, t, a. Các chữ cái này tạo thành tập hợp $ U = \ (k, o, n, f, e, t, a \) $. Giả sử chúng ta muốn tạo các "từ" gồm 5 chữ cái từ các hình khối này. Các chữ cái của những từ này (ví dụ: "confé", "tenko", v.v.) tạo thành (7,5) -sự lựa chọn: $ (k, o, n, f, e) $, $ (t, e, n , k, o) $, v.v. Rõ ràng, thứ tự của các chữ cái trong một mẫu như vậy là quan trọng. Ví dụ, các từ "nokft" và "kfton" khác nhau (mặc dù chúng bao gồm các chữ cái giống nhau), vì chúng không có cùng thứ tự các chữ cái. Không có sự lặp lại của các chữ cái trong những “từ” như vậy, bởi vì chỉ có bảy hình khối. Vì vậy, tập hợp các chữ cái của mỗi từ là một mẫu có thứ tự (7,5) không có lặp lại.

Một ví dụ khác: chúng ta tạo tất cả các loại số có tám chữ số từ bốn chữ số 1, 5, 7, 8. Ví dụ, 11111111, 15518877, 88881111, v.v. Tập hợp $ U $ như sau: $ U = \ (1,5,7,8 \) $. Các chữ số của mỗi số tổng hợp tạo thành a (4,8) -mẫu. Thứ tự của các chữ số trong một số rất quan trọng, tức là mẫu được đặt hàng. Lặp lại được phép, vì vậy ở đây chúng tôi đang xử lý một phần (4,8) có thứ tự với các lần lặp lại.

Phân bổ không lặp lại các phần tử $ n $ x $ k $

Phân bổ không lặp lại các phần tử $ n $ theo $ k $ - có thứ tự $ (n, k) $ - lựa chọn không lặp lại.

Vì không thể lặp lại các phần tử trong mẫu đang xét nên chúng ta không thể chọn nhiều phần tử trong mẫu hơn số phần tử có trong tập ban đầu. Do đó, đối với các mẫu như vậy, bất đẳng thức sau là đúng: $ n≥ k $. Số lượng vị trí không có sự lặp lại của $ n $ phần tử x $ k $ được xác định theo công thức sau:

\ begin (phương trình) A_ (n) ^ (k) = \ frac (n{(n-k)!} \end{equation} !}

Dấu "!" Nghĩa là gì?: hiện an

Đang ghi "n!" (đọc là "en factorial") biểu thị tích của tất cả các số từ 1 đến n, tức là

$$ n! = 1 \ cdot2 \ cdot 3 \ cdot \ ldots \ cdot n $$

Theo định nghĩa, người ta giả định rằng $ 0! = 1! = 1 $. Ví dụ, hãy tìm 5 !:

$$ 5! = 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 = 120. $$

Ví dụ 1

Bảng chữ cái bao gồm một tập hợp các ký tự $ E = \ (+, *, 0,1, f \) $. Hãy xác định số từ có ba ký tự như vậy trong bảng chữ cái này không chứa các chữ cái lặp lại.

Theo các từ gồm ba ký tự, chúng tôi có nghĩa là các biểu thức như "+ * 0" hoặc "0f1". Tập hợp $ E $ có năm phần tử, vì vậy các chữ cái của các từ có ba ký tự tạo thành (5,3) -các phần tử. Câu hỏi đầu tiên là: những mẫu này có được đặt hàng hay không? Các từ chỉ khác nhau về thứ tự của các chữ cái được coi là khác nhau, vì vậy thứ tự của các phần tử trong mẫu là rất quan trọng. Vì vậy, mẫu được đặt hàng. Câu hỏi thứ hai: có được phép lặp lại hay không? Câu trả lời cho câu hỏi này được đưa ra bởi điều kiện: các từ không được chứa các chữ cái lặp lại. Tính tổng: các chữ cái của mỗi từ thỏa mãn điều kiện của bài toán tạo thành một mẫu có thứ tự (5,3) không lặp lại. Nói cách khác, các chữ cái của mỗi từ tạo thành một sự sắp xếp không có sự lặp lại của 5 phần tử của 3. Dưới đây là các ví dụ về sự sắp xếp như vậy:

$$ (+, *, f), \; (*, +, f), \; (1, +, 0) $$

Chúng tôi cũng quan tâm đến tổng số vị trí này. Theo công thức (1), số lượng vị trí không có sự lặp lại của 5 phần tử với 3 sẽ như sau:

$$ A_ (5) ^ (3) = \ frac (5{(5-3)!}=\frac{5!}{2!}=60. $$ !}

Những thứ kia. bạn có thể tạo 60 từ có ba ký tự, các chữ cái của chúng sẽ không được lặp lại.

Câu trả lời: 60.

Phân bổ có sự lặp lại của $ n $ phần tử x $ k $

Vị trí có sự lặp lại của $ n $ phần tử trên $ k $ là một lựa chọn có thứ tự $ (n, k) $ - có sự lặp lại.

Số lượng vị trí có sự lặp lại của $ n $ phần tử x $ k $ được xác định theo công thức sau:

\ begin (phương trình) \ bar (A) _ (n) ^ (k) = n ^ k \ end (phương trình)

Ví dụ số 2

Có bao nhiêu số có năm chữ số có thể được tạo thành từ tập hợp các chữ số $ \ (5,7,2 \) $?

Từ bộ số này, bạn có thể tạo các số có năm chữ số 55555, 75222, v.v. Các chữ số của mỗi số như vậy tạo thành a (3,5) -Ví dụ: $ (5,5,5,5,5) $, $ (7,5,2,2,2) $. Chúng ta hãy tự hỏi mình: những mẫu này là gì? Đầu tiên, các chữ số trong số có thể được lặp lại, vì vậy chúng tôi đang xử lý các mẫu có số lần lặp lại. Thứ hai, thứ tự của các con số trong số rất quan trọng. Ví dụ, 27755 và 77255 là các số khác nhau. Do đó, chúng tôi đang đối phó với các lựa chọn có thứ tự (3,5) có sự lặp lại. Tổng số mẫu như vậy (tức là tổng số các số có năm chữ số bắt buộc) có thể được tìm thấy bằng cách sử dụng công thức (2):

$$ \ bar (A) _ (3) ^ (5) = 3 ^ 5 = 243. $$

Do đó, từ các chữ số đã cho có thể lập được 243 số có năm chữ số.

Câu trả lời: 243.

Hoán vị không lặp lại $ n $ phần tử

Một hoán vị không có lặp lại các phần tử $ n $ là một phép chọn $ (n, n) $ có thứ tự không có lặp lại.

Trên thực tế, hoán vị không lặp lại là một trường hợp đặc biệt của sắp xếp không lặp lại, khi kích thước mẫu bằng lũy ​​thừa của tập ban đầu. Số lần hoán vị không lặp lại của $ n $ phần tử được xác định theo công thức sau:

\ begin (phương trình) P_ (n) = n! \ end (phương trình)

Nhân tiện, công thức này rất dễ đạt được nếu chúng ta tính đến $ P_n = A_ (n) ^ (n) $. Sau đó, chúng tôi nhận được:

$$ P_n = A_ (n) ^ (n) = \ frac (n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$ !}

Ví dụ # 3

Tủ đông chứa năm phần kem từ các công ty khác nhau. Trong bao nhiêu cách bạn có thể chọn thứ tự mà chúng được ăn?

Để số 1 tương ứng với kem đầu tiên, số 2 tương ứng với thứ hai, v.v. Chúng ta sẽ nhận được một tập hợp $ U = \ (1,2,3,4,5 \) $ sẽ đại diện cho nội dung của ngăn đá. Thứ tự ăn có thể là $ (2,1,3,5,4) $ hoặc $ (5,4,3,1,2) $. Mỗi tập hợp như vậy là một (5,5) -sample. Nó sẽ có trật tự và không có sự lặp lại. Nói cách khác, mỗi mẫu như vậy là một hoán vị của 5 phần tử của tập hợp ban đầu. Theo công thức (3), tổng số các hoán vị này là:

$$ P_5 = 5! = 120. $$

Do đó, có 120 suất đặt ăn.

Câu trả lời: 120.

Hoán vị có lặp lại

Một hoán vị có lặp lại là một lựa chọn có thứ tự $ (n, k) $ - với các lần lặp lại trong đó phần tử $ a_1 $ được lặp lại $ k_1 $ lần, $ a_2 $ được lặp lại $ k_2 $ lần, v.v., cho đến phần tử cuối cùng $ a_r $, được lặp lại $ k_r $ lần. Hơn nữa, $ k_1 + k_2 + \ ldots + k_r = k $.

Tổng số các hoán vị có lặp lại được cho bởi:

\ begin (phương trình) P_ (k) (k_1, k_2, \ ldots, k_r) = \ frac (k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation} !}

Ví dụ # 4

Các từ được hình thành trên cơ sở bảng chữ cái $ U = \ (a, b, d \) $. Có bao nhiêu từ khác nhau gồm bảy ký tự nếu trong các từ này phải lặp lại chữ "a" 2 lần; chữ "b" - 1 lần, và chữ "d" - 4 lần?

Dưới đây là ví dụ về các từ tìm kiếm: "aabdddd", "daddabd", v.v. Các chữ cái của mỗi từ tạo thành a (3,7) -mẫu có lặp lại: $ (a, a, b, d, d, d, d) $, $ (d, a, d, d, a, b, d ) $ và v.v. Mỗi lựa chọn như vậy bao gồm hai phần tử "a", một phần tử "b" và bốn phần tử "d". Nói cách khác, $ k_1 = 2 $, $ k_2 = 1 $, $ k_3 = 4 $. Tất nhiên, tổng số lần lặp lại của tất cả các ký tự bằng với kích thước mẫu, tức là $ k = k_1 + k_2 + k_3 = 7 $. Thay các dữ liệu này vào công thức (4), chúng ta sẽ có:

$$ P_7 (2,1,4) = \ frac (7{2!\cdot 1!\cdot 4!}=105. $$ !}

Do đó, tổng số từ được tìm kiếm là 105.

Câu trả lời: 105.

Các kết hợp không lặp lại của $ n $ phần tử với $ k $

Một tổ hợp không có sự lặp lại của $ n $ phần tử với $ k $ là một lựa chọn $ (n, k) $ - không có thứ tự không có sự lặp lại.

Tổng số kết hợp không có sự lặp lại của $ n $ phần tử với $ k $ được xác định theo công thức:

\ begin (phương trình) C_ (n) ^ (k) = \ frac (n{(n-k)!\cdot k!} \end{equation} !}

Ví dụ số 5

Rổ đựng các thẻ trên đó viết các số nguyên từ 1 đến 10. Lấy 4 thẻ ra khỏi giỏ và tổng các số ghi trên chúng. Có thể rút ra bao nhiêu bộ thẻ khác nhau từ rổ?

Vì vậy, trong bài toán này, tập hợp ban đầu như sau: $ U = \ (1,2,3,4,5,6,7,8,9,10 \) $. Từ tập hợp này, chúng tôi chọn bốn phần tử (tức là bốn thẻ từ rổ). Số của các phần tử được kéo ra tạo thành một (10,4) -mẫu. Không được phép lặp lại trong mẫu này, vì số lượng của tất cả các thẻ là khác nhau. Câu hỏi đặt ra là: thứ tự các thẻ được chọn có quan trọng hay không? Ví dụ, các mẫu $ (1,2,7,10) $ và $ (10,2,1,7) $ bằng nhau hay không bằng nhau? Ở đây bạn cần chuyển sang điều kiện của vấn đề. Các thẻ được lấy ra để sau đó tìm tổng các phần tử. Và điều này có nghĩa là thứ tự của các thẻ không quan trọng, vì số tiền sẽ không thay đổi từ việc thay đổi vị trí của các điều khoản. Ví dụ: mẫu $ (1,2,7,10) $ và mẫu $ (10,2,1,7) $ sẽ khớp với cùng một số $ 1 + 2 + 7 + 10 = 10 + 2 + 1 + 7 = 20 $. Kết luận: nó dựa trên điều kiện của vấn đề mà chúng ta đang xử lý với các mẫu không có thứ tự. Những thứ kia. chúng ta cần tìm tổng số ví dụ (10,4) không có thứ tự mà không có lặp lại. Nói cách khác, chúng ta cần tìm số kết hợp của 10 phần tử bằng 4. Chúng ta sử dụng công thức (5) cho điều này:

$$ C_ (10) ^ (4) = \ frac (10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$ !}

Do đó, tổng số bộ cần thiết là 210.

Câu trả lời: 210.

Các kết hợp có sự lặp lại của $ n $ phần tử với $ k $

Một tổ hợp có sự lặp lại của $ n $ phần tử trên $ k $ là một lựa chọn $ (n, k) $ - không có thứ tự với các lần lặp lại.

Tổng số kết hợp có sự lặp lại của $ n $ phần tử trên $ k $ được xác định theo công thức:

\ begin (phương trình) \ bar (C) _ (n) ^ (k) = \ frac ((n + k-1){(n-1)!\cdot k!} \end{equation} !}

Ví dụ # 6

Hãy tưởng tượng rằng chúng ta đang ở trong một nhà máy sản xuất kẹo - ngay bên cạnh băng chuyền có bốn loại kẹo di chuyển. Chúng tôi đặt tay vào dòng suối này và kéo ra hai mươi trong số chúng. Có thể có bao nhiêu "sự kết hợp kẹo" khác nhau trong một số ít?

Nếu chúng ta giả sử rằng số 1 tương ứng với sắp xếp đầu tiên, số 2 tương ứng với sắp xếp thứ hai, v.v., thì tập hợp ban đầu trong bài toán của chúng ta như sau: $ U = \ (1,2,3,4 \ ) $. Từ tập hợp này, chúng tôi chọn 20 phần tử (tức là 20 viên kẹo giống nhau từ băng tải). Một số ít đồ ngọt tạo thành (4,20) -mẫu. Đương nhiên, sẽ có sự lặp lại của các giống. Câu hỏi đặt ra là thứ tự của các yếu tố trong sự lựa chọn có đóng một vai trò nào đó hay không? Từ các điều kiện của bài toán mà thứ tự của các phần tử không quan trọng. Không có gì khác biệt đối với chúng tôi cho dù một số ít chứa 15 viên kẹo mút đầu tiên, sau đó là 4 viên sô-cô-la, hay 4 viên sô-cô-la đầu tiên và chỉ sau đó là 15 viên kẹo mút. Vì vậy, chúng tôi đang xử lý một mẫu không có thứ tự (4.20) với các lần lặp lại. Để tìm tổng số mẫu này, chúng tôi sử dụng công thức (6):

$$ \ bar (C) _ (4) ^ (20) = \ frac ((4 + 20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$ !}

Do đó, tổng số kết hợp mong muốn là 1771.

KẾT HỢP

Tổ hợp là một nhánh của toán học nghiên cứu các vấn đề về lựa chọn và sắp xếp các phần tử từ một số tập hợp cơ bản theo các quy tắc nhất định. Các công thức và nguyên tắc của tổ hợp được sử dụng trong lý thuyết xác suất để tính xác suất của các sự kiện ngẫu nhiên và do đó, để thu được quy luật phân phối của các biến ngẫu nhiên. Điều này giúp cho việc nghiên cứu các quy luật của các hiện tượng ngẫu nhiên hàng loạt có ý nghĩa rất quan trọng, điều này rất quan trọng để hiểu đúng về các quy luật thống kê thể hiện trong tự nhiên và công nghệ.

Quy tắc cộng và nhân trong tổ hợp

Quy tắc tính tổng. Nếu hai hành động A và B loại trừ lẫn nhau và hành động A có thể được thực hiện theo m cách và B theo n cách, thì bất kỳ một trong những hành động này (hoặc A hoặc B) đều có thể được thực hiện theo n + m cách.

ví dụ 1

Có 16 nam và 10 nữ trong lớp. Một người phục vụ có thể được chỉ định theo bao nhiêu cách?

Dung dịch

Bạn có thể cử một chàng trai hoặc một cô gái làm nhiệm vụ, tức là bất kỳ ai trong số 16 chàng trai hoặc bất kỳ cô gái nào trong số 10 cô gái đều có thể làm nhiệm vụ.

Theo quy tắc tổng, chúng tôi nhận được rằng một sĩ quan trực ca có thể được chỉ định 16 + 10 = 26 cách.

Quy tắc nhân. Để nó được yêu cầu thực hiện tuần tự k hành động. Nếu hành động đầu tiên có thể được thực hiện trong n 1 cách, hành động thứ hai trong n 2 cách, hành động thứ ba trong n 3 cách, v.v. cho đến hành động thứ k có thể được thực hiện theo n k cách, thì tất cả k hành động cùng có thể được đã thực hiện:

các cách.

Ví dụ 2

Có 16 nam và 10 nữ trong lớp. Có bao nhiêu cách có thể chỉ định hai tiếp viên?

Dung dịch

Người làm nhiệm vụ đầu tiên có thể là trai hoặc gái. Tại vì lớp có 16 nam và 10 nữ thì cử cán bộ trực ban thứ nhất theo 16 + 10 = 26 cách.

Sau khi chúng tôi đã chọn sĩ quan trực ban đầu tiên, chúng tôi có thể chọn người thứ hai trong số 25 người còn lại, tức là 25 cách.

Theo định lý nhân, có thể chọn hai tiếp viên trong 26 * 25 = 650 cách.

Kết hợp không lặp lại. Kết hợp với lặp lại

Bài toán cổ điển của tổ hợp là bài toán về số lượng các tổ hợp không lặp lại, nội dung của nó có thể được diễn đạt bằng câu hỏi: bao nhiêu cách có thể chọn M từ n mặt hàng khác nhau?

Ví dụ 3

Bạn phải chọn 4 trong số 10 cuốn sách khác nhau có sẵn để làm quà tặng. Điều này có thể được thực hiện bằng bao nhiêu cách?

Dung dịch

Chúng ta cần chọn 4 trong số 10 cuốn sách, và thứ tự lựa chọn không quan trọng. Do đó, bạn cần tìm số lượng các kết hợp của 10 phần tử với 4:

.

Xét bài toán về số lượng các tổ hợp có lặp lại: có r đối tượng giống hệt nhau thuộc n loại khác nhau; bao nhiêu cách có thể chọn m () trong số này (n * r) mặt hàng?

.

Ví dụ 4

Cửa hàng bánh ngọt có bán 4 loại bánh: napoleons, eclairs, shortbread và phồng. Có bao nhiêu cách mua được 7 cái bánh?

Dung dịch

Tại vì Trong số 7 cái bánh có thể có những cái bánh giống nhau thì số cách mua được 7 cái bánh được xác định bằng số cách tổ hợp có lặp lại từ 7 đến 4 cái.

.

Vị trí không lặp lại. Vị trí lặp lại

Bài toán cổ điển của tổ hợp là bài toán về số lượng các vị trí không lặp lại, nội dung của chúng có thể được thể hiện bằng câu hỏi: bao nhiêu cách có thể chọn và nơi trên tôi khác vị trí M từ n khác mặt hàng?

Ví dụ 5

Một số tờ báo có 12 trang. Cần phải đặt bốn bức ảnh trên các trang của tờ báo này. Điều này có thể được thực hiện bằng bao nhiêu cách nếu không trang nào của tờ báo được chứa nhiều hơn một bức ảnh?

Dung dịch.

Trong bài toán này, chúng ta không chỉ chọn ảnh mà đặt trên một số trang nhất định của tờ báo, và mỗi trang báo không được quá một ảnh. Do đó, bài toán được rút gọn thành bài toán cổ điển là xác định số lượng vị trí không có lặp lại từ 12 phần tử theo 4 phần tử:

Như vậy, 4 bức ảnh trên 12 trang có thể được sắp xếp theo 11880 cách.

Ngoài ra, nhiệm vụ cổ điển của tổ hợp là vấn đề về số lượng các vị trí có lặp lại, nội dung của chúng có thể được thể hiện bằng câu hỏi: bao nhiêu cách có thể bạnbquân đội và nơi trên tôi khác vị trí M từ n mặt hàngVớiredi cái mà có như nhau?

Ví dụ 6

Cậu bé có những con tem với các số 1, 3 và 7 từ bộ cho trò chơi trên bàn cờ. Cậu quyết định sử dụng những con tem này để dán các số có năm chữ số vào tất cả các cuốn sách - để biên soạn một danh mục. Cậu bé có thể lập được bao nhiêu số có năm chữ số khác nhau?

Hoán vị không lặp lại. Hoán vị có lặp lại

Bài toán cổ điển của tổ hợp là bài toán về số các hoán vị không lặp lại, nội dung của nó có thể được diễn đạt bằng câu hỏi: bao nhiêu cách có thể nơi N nhiều mặt hàng trên n khác vị trí?

Ví dụ 7

Có thể tạo ra bao nhiêu "từ" có bốn chữ cái từ các chữ cái của từ "hôn nhân"?

Dung dịch

Tập hợp chung là 4 chữ cái của từ "hôn nhân" (b, p, a, k). Số lượng "từ" được xác định bởi các hoán vị của 4 chữ cái này, tức là

Đối với trường hợp trong số n phần tử được chọn có giống nhau (phép chọn có trả về), bài toán về số hoán vị có lặp lại có thể được biểu diễn bằng câu hỏi: Có bao nhiêu cách có thể sắp xếp lại n đối tượng ở n vị trí khác nhau nếu trong số n đối tượng có k loại khác nhau (k< n), т. е. есть одинаковые предметы.

Ví dụ 8

Có bao nhiêu tổ hợp chữ cái khác nhau có thể được tạo ra từ các chữ cái của từ "Mississippi"?

Dung dịch

Có 1 chữ cái "m", 4 chữ cái "i", 3 chữ cái "c" và 1 chữ cái "p", tổng cộng là 9 chữ cái. Do đó, số hoán vị có lặp lại là

TÓM TẮT CƠ SỞ VỀ PHẦN "KẾT HỢP"