Có bao nhiêu danh sách gồm 5 có thể được chọn từ nhóm 30 ban đầu

Đầu tiên chúng ta chuyển sang đếm. Mặc dù điều này nghe có vẻ đơn giản, có lẽ quá đơn giản để nghiên cứu, nhưng nó không phải là. Khi chúng ta nói về đếm, đó là cách viết tắt để xác định kích thước của một tập hợp, hoặc thường xuyên hơn, kích thước của nhiều tập hợp, tất cả đều có điểm chung, nhưng các kích thước khác nhau tùy thuộc vào một hoặc nhiều tham số. Ví dụ. có bao nhiêu kết quả có thể xảy ra khi tung một con súc sắc? . chúng ta nói "kết quả" nghĩa là gì? Giả sử chúng ta tung hai con xúc xắc, giả sử một con xúc xắc màu đỏ và một con xúc xắc màu xanh lá cây. Kết quả "hai đỏ, ba xanh" có khác với "ba đỏ, hai xanh" không? . Nếu không, có 21. Chúng tôi thậm chí có thể chỉ quan tâm đến tổng số có thể, trong trường hợp đó có 11 kết quả

Ngay cả cách giải thích đầu tiên khá đơn giản cũng dựa trên một số kiến ​​thức về đếm; . Về kích thước tập hợp, giả sử chúng ta biết rằng tập hợp $A$ có kích thước $m$ và tập hợp $B$ có kích thước $n$. Kích thước của $A$ và $B$ cộng lại là bao nhiêu, tức là kích thước của $A\cup B$? . Một vấn đề đơn giản nhưng điển hình của loại này. Nếu chúng ta tung hai con xúc xắc, có bao nhiêu cách để được 7 hoặc 11? . Mặc dù nguyên tắc này đơn giản, nhưng rất dễ quên yêu cầu rằng hai tập hợp phải rời nhau và do đó sử dụng nó khi hoàn cảnh khác. Nguyên tắc này thường được gọi là nguyên tắc bổ sung

Nguyên tắc này có thể được khái quát. nếu các bộ $A_1$ đến $A_n$ rời nhau theo cặp và có kích thước $m_1,\ldots m_n$, thì kích thước của $A_1\cup\cdots\cup A_n=\sum_{i=1}^n m_i$. Điều này có thể được chứng minh bằng một lập luận quy nạp đơn giản

Tại sao khi gieo hai con xúc xắc ta lại biết được 36 kết quả mà không liệt kê hết? . Đối với mỗi 6 kết quả của con súc sắc đầu tiên, con súc sắc thứ hai có thể có bất kỳ kết quả nào trong số 6 kết quả, vì vậy tổng số là $6+6+6+6+6+6=36$, hoặc ngắn gọn hơn, $6\cdot6=36$. Lưu ý rằng chúng tôi đang thực sự sử dụng nguyên tắc bổ sung ở đây. đặt $A_1$ là tất cả các cặp $(1,x)$, đặt $A_2$ là tất cả các cặp $(2,x)$, v.v. Điều này có phần tinh tế hơn so với lần đầu tiên. Trong ví dụ đơn giản này, kết quả của quân súc sắc thứ hai không liên quan gì đến kết quả của quân súc sắc thứ nhất. Đây là một ví dụ phức tạp hơn một chút. Có bao nhiêu cách tung hai con súc sắc sao cho hai con súc sắc không bằng nhau? . Ở đây, đối với mỗi giá trị có thể có trên khuôn số một, có năm giá trị có thể có cho khuôn số hai, nhưng chúng là năm giá trị khác nhau cho mỗi giá trị trên khuôn số một. Tuy nhiên, vì tất cả đều giống nhau nên kết quả là $5+5+5+5+5+5=30$ hoặc $6\cdot 5=30$. Nói chung, khi đó, nếu có $m$ khả năng xảy ra cho một biến cố và $n$ cho biến cố thứ hai, thì số kết quả có thể xảy ra cho cả hai biến cố cộng lại là $m\cdot n$. Điều này thường được gọi là nguyên tắc nhân

Nói chung, nếu $n$ sự kiện có $m_i$ kết quả có thể xảy ra, với $i=1,\ldots,n$, trong đó mỗi $m_i$ không bị ảnh hưởng bởi kết quả của các sự kiện khác, thì tổng số kết quả có thể xảy ra là $ . Điều này cũng có thể được chứng minh bằng quy nạp

ví dụ 1. 2. 1 Có bao nhiêu kết quả có thể xảy ra khi tung ba con súc sắc, nếu không có hai con nào giống nhau? . Đối với mỗi kết quả trong số 30 kết quả này, có 4 kết quả có thể xảy ra cho con súc sắc thứ ba, vì vậy tổng số kết quả là $30\cdot 4=6\cdot 5\cdot 4=120$. (Lưu ý rằng chúng tôi coi xúc xắc là có thể phân biệt được, nghĩa là một lượt tung 6, 4, 1 khác với 4, 6, 1, vì xúc xắc thứ nhất và thứ hai khác nhau trong hai lượt tung, mặc dù các số là một . ) $\square$

ví dụ 1. 2. 2 Giả sử các khối được đánh số từ 1 đến $n$ nằm trong một cái thùng; . Có bao nhiêu kết quả có thể xảy ra?

Điều này về cơ bản giống như ví dụ trước. có $k$ "điểm" được lấp đầy bởi các khối. Bất kỳ khối $n$ nào cũng có thể xuất hiện đầu tiên trong dòng; . Do đó, số lượng kết quả là $n(n-1)(n-2)\cdots(n-k+1)$, theo nguyên tắc nhân. Trong ví dụ trước, "điểm'' đầu tiên là xúc xắc số một, vị trí thứ hai là xúc xắc số hai, vị trí thứ ba là xúc xắc số ba và $6\cdot5\cdot4=6(6-1)(6-2)$ . $\square$

Đây là một loại vấn đề khá chung chung

định nghĩa 1. 2. 3 Số hoán vị của $n$ thứ được lấy $k$ tại một thời điểm là $$P(n,k)=n(n-1)(n-2)\cdots(n-k+1)={n. \ hơn (n-k). }. $$ $\square$

Một hoán vị của một số đối tượng là một thứ tự tuyến tính cụ thể của các đối tượng; . số cách chọn và sắp xếp $k$ trong số $n$ đồ vật. Một trường hợp đặc biệt hữu ích là $k=n$, trong đó chúng ta chỉ đơn giản là đếm số cách sắp xếp tất cả các đối tượng $n$. Đây là $n(n-1)\cdots(n-n+1)=n. $. Lưu ý rằng dạng thứ hai của $P(n,k)$ từ định nghĩa cho $${n. \ hơn (n-n). }={n. \ trên 0. }. $$ Điều này chỉ đúng nếu $0. =1$, vì vậy chúng tôi áp dụng quy ước tiêu chuẩn rằng điều này là đúng, nghĩa là chúng tôi xác định $0. $ thành $1$

Giả sử chúng ta chỉ muốn đếm số cách chọn $k$ mục trong số $n$, nghĩa là chúng ta không quan tâm đến thứ tự. Ví dụ , chúng tôi đã đếm số lần gieo của ba viên xúc xắc với các số khác nhau hiển thị. Xúc xắc có thể phân biệt được, hoặc theo một thứ tự cụ thể. con súc sắc thứ nhất, con thứ hai và con thứ ba. Bây giờ chúng tôi muốn đếm đơn giản có bao nhiêu tổ hợp số, với 6, 4, 1 hiện được tính là tổ hợp giống như 4, 6, 1

ví dụ 1. 2. 4 Giả sử chúng ta liệt kê tất cả 120 khả năng trong ví dụ. Danh sách sẽ chứa nhiều kết quả mà bây giờ chúng tôi muốn tính là một kết quả duy nhất; . Bao nhiêu lần một kết quả duy nhất sẽ xuất hiện trong danh sách? . có $3. $ đơn đặt hàng trong đó 1, 4, 6 có thể xuất hiện và tất cả 6 trong số này sẽ có trong danh sách. Trên thực tế, mọi kết quả sẽ xuất hiện trong danh sách 6 lần, vì mọi kết quả có thể xuất hiện trong $3. $ đơn đặt hàng. Do đó, danh sách này quá lớn với hệ số 6; . $\square$

Nói chung, theo lý luận tương tự, nếu chúng ta có $n$ đối tượng, số cách chọn $k$ trong số chúng là $P(n,k)/k. $, vì mỗi bộ sưu tập các đối tượng $k$ sẽ được tính $k. $ nhân $P(n,k)$

định nghĩa 1. 2. 5 Số tập con kích thước $k$ của một tập kích thước $n$ (còn được gọi là $n$-set) là $$C(n,k)={P(n,k)\over k. }={n. \over k. (n-k). }={n\chọn k}. $$ Ký hiệu $C(n,k)$ hiếm khi được sử dụng; . $\square$

ví dụ 1. 2. 6 Xét $n=0,1,2,3$. Thật dễ dàng để liệt kê các tập hợp con của một $n$-set nhỏ; . Một $0$-set, cụ thể là tập rỗng, có một tập con, tập rỗng; . $\emptyset$, $\{a_1\}$, $\{a_2\}$, $\{a_3\}$, $\{a_1,a_2\}$, $\{a_1,a_3\}$, $ . Từ những danh sách này, thật dễ dàng để tính toán $n\choose k$. $$\displaylines{\cr \matrix{ &\rlap{\lower 3pt\hbox{$\Rule{65pt}{0pt}{0. 5pt}$}}\cr &0\cr n&1\cr &2\cr &3\cr }\left\vert \matrix{ 0&\lower 3. 5pt\hbox{}\rlap{\smash{\raise 1. 5em \hbox{$k$}}}1&2&3\cr 1\cr 1&1\cr 1&2&1\cr 1&3&3&1\cr }\right. \cr}$$ $\square$

Bạn có thể nhận ra những con số này. đây là điểm bắt đầu của Tam giác Pascal. Mỗi mục trong tam giác Pascal được tạo bằng cách thêm hai mục từ hàng trước đó. cái ở ngay phía trên, và cái ở trên và bên trái. Điều này cho thấy rằng ${n\choose k}={n-1\choose k-1}+{n-1\choose k}$, và thực tế điều này đúng. Để giải quyết vấn đề này một cách gọn gàng, chúng tôi áp dụng quy ước ${n\choose k}=0$ khi $k< 0$ hoặc $k>n$

Định lý 1. 2. 7 $\ds{n\choose k}={n-1\choose k-1}+{n-1\choose k}$

Bằng chứng. Một $n$-set điển hình là $A=\{a_1,\ldots,a_n\}$. Chúng tôi xem xét hai loại tập hợp con. những cái có chứa $a_n$ và những cái không. Nếu $k$-tập hợp con của $A$ không chứa $a_n$, thì đó là $k$-tập hợp con của $\{a_1,…,a_{n-1}\}$ và có $n . Nếu nó chứa $a_n$, thì nó bao gồm các phần tử $a_n$ và $k-1$ của $\{a_1,…,a_{n-1}\}$; . Do đó, tổng số $k$-tập hợp con của $A$ là ${n-1\choose k-1}+{n-1\choose k}$

Lưu ý rằng khi $k=0$, ${n-1\choose k-1}={n-1\choose -1}=0$ và khi $k=n$, ${n-1\choose k . Những giá trị này là những giá trị biên trong Tam giác Pascal. $\qed$

Nhiều bài toán đếm dựa vào kiểu lập luận mà chúng ta đã thấy. Dưới đây là một vài biến thể về chủ đề

ví dụ 1. 2. 8 Sáu người sẽ ngồi quanh bàn tròn;

Không rõ chính xác những gì chúng ta muốn tính ở đây. Ví dụ: nếu có một "chỗ ngồi đặc biệt", việc ai ngồi vào ghế đó có thể quan trọng. Nếu điều này không quan trọng, chúng ta chỉ quan tâm đến vị trí tương đối của mỗi người. Sau đó, việc một người nào đó ở bên trái hay bên phải của người khác có thể hoặc không quan trọng. Vì vậy, câu hỏi này có thể được giải thích theo (ít nhất) ba cách. Hãy trả lời tất cả

Đầu tiên, nếu những chiếc ghế thực sự có người ngồi là quan trọng, thì điều này hoàn toàn giống với việc xếp sáu người thành một hàng. 6 lựa chọn cho ghế số một, 5 cho ghế số hai, v.v., với tổng số tiền là 6 đô la. $. Nếu ghế không quan trọng, thì $6. $ đếm cùng một cách sắp xếp quá nhiều lần, một lần cho mỗi người có thể ngồi ở ghế một. Vì vậy, tổng số tiền trong trường hợp này là $6. /6=5. $. Một cách tiếp cận khác cho điều này. vì chỗ ngồi thực tế không quan trọng, chỉ cần đặt một trong sáu người vào ghế. Sau đó, chúng tôi cần sắp xếp 5 người còn lại thành một hàng, có thể thực hiện trong 5 đô la. $ cách. Cuối cùng, giả sử tất cả những gì chúng ta quan tâm là ai ở bên cạnh ai, không cần biết phải trái. Sau đó, câu trả lời trước đó đếm mỗi lần sắp xếp hai lần, một lần cho thứ tự ngược chiều kim đồng hồ và một lần theo chiều kim đồng hồ. Vậy tổng cộng là $5. /2=P(5,3)$. $\square$

Chúng ta đã hai lần chứng kiến ​​một nguyên tắc chung đang hoạt động. nếu chúng ta có thể đếm vượt quá tập hợp mong muốn theo cách mà mọi mục được đếm cùng một số lần, thì chúng ta có thể nhận được số lượng mong muốn chỉ bằng cách chia cho thừa số chung. Đây sẽ tiếp tục là một ý tưởng hữu ích. Một biến thể của chủ đề này là đếm thừa rồi trừ đi số lượng đếm thừa.

ví dụ 1. 2. 9 Có bao nhiêu cách sắp xếp sáu người sao cho một cặp người nào đó không đứng cạnh nhau?

Biểu thị những người $A$ và $B$. Tổng số đơn đặt hàng là $6. $, nhưng điều này tính những đơn đặt hàng có $A$ và $B$ cạnh nhau. Có bao nhiêu trong số này? . $. Mỗi đơn đặt hàng này tương ứng với hai đơn đặt hàng khác nhau, trong đó $A$ và $B$ liền kề nhau, tùy thuộc vào việc $A$ hay $B$ đứng trước. Vì vậy, $6. số lượng $ quá cao $2\cdot5. $ và số lượng chúng tôi tìm kiếm là $6. -2\cchấm 5. =4\cdot5. $. $\square$

bài tập 1. 2

Ví dụ 1. 2. 1 $2\cdot3^4\cdot7^3\cdot11^2\cdot47^5$ có bao nhiêu yếu tố tích cực?

Ví dụ 1. 2. 2 Một ván bài xì phé bao gồm năm quân bài từ bộ bài tiêu chuẩn 52 lá với bốn quân bài và mười ba giá trị trong mỗi quân bài; . Có bao nhiêu ván bài bao gồm 2 quân bài có cùng giá trị và 3 quân bài có giá trị khác (một nhà đầy)?

Ví dụ 1. 2. 3 Sáu nam và sáu nữ ngồi quanh một bàn, nam và nữ luân phiên nhau. Ghế không quan trọng, chỉ quan trọng ai ngồi cạnh ai, trái phải khác nhau. Có bao nhiêu cách sắp xếp chỗ ngồi?

Ví dụ 1. 2. 4 Tám người ngồi chung quanh một cái bàn; . Hai người X và Y không được ngồi cạnh nhau. Có bao nhiêu cách sắp xếp chỗ ngồi?

Ví dụ 1. 2. 5. Trong cờ vua, một quân xe tấn công bất kỳ quân nào ở cùng hàng hoặc cùng cột với quân đó, miễn là không có quân nào khác ở giữa chúng. Có bao nhiêu cách xếp tám quân xe không giống nhau lên một bàn cờ sao cho không có quân nào tấn công lẫn nhau?

Ví dụ 1. 2. 6 Giả sử chúng ta muốn đặt 8 quân Xe không tấn công trên bàn cờ. Có bao nhiêu cách chúng ta có thể làm điều này nếu 16 ô vuông 'tây bắc' nhất phải trống?

Ví dụ 1. 2. 7 Chuỗi dấu ngoặc đơn "hợp pháp'' là chuỗi trong đó các dấu ngoặc đơn có thể khớp đúng cách, như $()(())$. Không khó để thấy rằng điều này hoàn toàn có thể xảy ra khi số lượng dấu ngoặc trái và phải là như nhau, và mỗi đoạn ban đầu của chuỗi có ít nhất số dấu ngoặc trái bằng số dấu ngoặc phải. Ví dụ: $())\ldots$ không thể được mở rộng thành một chuỗi hợp lệ. Chứng minh rằng số dãy hợp lệ có độ dài $2n$ là $C_n={2n\choose n}-{2n\choose n+1}$. Các số $C_n$ được gọi là các số Catalan

Có bao nhiêu cách chọn một nhóm 5 người từ 30 người?

Có bao nhiêu cách bạn có thể chọn 3 sinh viên từ một nhóm 5 người?

Có bao nhiêu cách chọn 5 người từ một nhóm 15 người?

Hỏi có bao nhiêu cách chọn ra một hội đồng gồm 5 người từ 9 người?