1 Giải tích tổ hợp

Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp. Chủ đề này đã được nghiên cứu từ thế kỷ 17, khi những câu hỏi về tổ hợp được nêu ra trong những công trình nghiên cứu các trò chơi may rủi. Liệt kê, đếm các đối tượng có những tính chất nào đó là một phần quan trọng của lý thuyết tổ hợp. Chúng ta cần phải đếm các đối tượng để giải nhiều bài toán khác nhau. Các kỹ thuật đếm được dùng rất nhiều trong tin học đặc biệt là trong phân tích thuật toán và lý thuyết xác suất.

1.1 Cơ sở phép đếm

1.1.1 Những nguyên lý đếm cơ bản

Quy tắc cộng

Giả sử có \(k\) công việc \(T_{1},T_{2},...,T_{k}\). Các việc này có thể làm tương ứng bằng \(n_{1},n_{2},...,n_{k}\) cách và giả sử không có hai việc nào có thể làm đồng thời. Khi đó số cách làm một trong \(k\) việc đó là \(n_{1}+n_{2}+...+n_{k}\).

Một sinh viên có thể chọn bài thực hành máy tính từ một trong ba danh sách tương ứng có 23, 15 và 19 bài. Vì vậy, theo quy tắc cộng có \(23+15+19=57\) cách chọn bài thực hành.

Giá trị của biến \(m\) bằng bao nhiêu sau khi đoạn chương trình Python sau được thực hiện?

m = 0
for i1 in range(n1):
    m += 1
for i2 in range(n2):
    m += 1 
...
for ik in range(nk):
    m += 1

Proof. Lời giải. Giá trị khởi tạo của \(m\) bằng 0. Khối lệnh này gồm \(k\) vòng lặp khác nhau. Sau mỗi bước lặp của từng vòng lặp giá trị của \(k\) được tăng lên một đơn vị. Gọi \(T_{i}\) là việc thi hành vòng lặp thứ \(i\). Có thể làm \(T_{i}\) bằng \(n_{i}\) cách vì vòng lặp thứ \(i\) có \(n_{i}\) bước lặp. Do các vòng lặp không thể thực hiện đồng thời nên theo quy tắc cộng, giá trị cuối cùng của \(m\) bằng số cách thực hiện một trong số các nhiệm vụ \(T_{i}\), tức là \(m=n_{1}+n_{2}+...+n_{k}\). ◻

Ngôn ngữ tập hợp

Nếu \(A_{1},A_{2},...,A_{k}\) là các tập hợp đôi một rời nhau, khi đó số phần tử của hợp các tập hợp này bằng tổng số các phần tử của các tập thành phần. Giả sử \(T_{i}\) là việc chọn một phần tử từ tập \(A_{i}\) với \(i=1,2,...,k\). Có \(|A_{i}\)| cách làm và không có hai việc nào có thể được làm cùng một lúc. Số cách chọn một phần tử của hợp các tập hợp này, một mặt bằng số phần tử của nó, mặt khác theo quy tắc cộng nó bằng \(|A_{1}|+|A_{2}|+...+|A_{k}|\). Do đó ta có: \(|A_{1}\cup A_{2}\cup...\cup A_{k}|=|A_{1}|+|A_{2}|+...+|A_{k}|\).

Quy tắc nhân

Giả sử một nhiệm vụ nào đó được tách ra thành \(k\) việc \(T_{1},T_{2},...,T_{k}\). Nếu việc \(T_{i}\) có thể làm bằng \(n_{i}\) cách sau khi các việc \(T_{1},T_{2},...T_{i-1}\) đã được làm, khi đó có \(n_{1}.n_{2}...n_{k}\) cách thi hành nhiệm vụ đã cho.

Người ta có thể ghi nhãn cho những chiếc ghế trong một giảng đường bằng một chữ cái và một số nguyên dương không vượt quá 100. Bằng cách như vậy, nhiều nhất có bao nhiêu chiếc ghế có thể được ghi nhãn khác nhau?

Proof. Lời giải. Thủ tục ghi nhãn cho một chiếc ghế gồm hai việc, gán một trong 26 chữ cái và sau đó gán một trong 100 số nguyên dương. Quy tắc nhân chỉ ra rằng có \(26.100=2600\) cách khác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán nhãn cho 2600 chiếc ghế. ◻

Có bao nhiêu chuỗi nhị phân có độ dài \(n\).

Proof. Lời giải. Mỗi bit trong \(n\) bit của chuỗi nhị phân có thể chọn bằng hai cách vì mỗi bit hoặc bằng 0 hoặc bằng 1. Bởi vậy theo quy tắc nhân có tổng cộng \(2^{n}\) chuỗi nhị phân khác nhau có độ dài bằng \(n\). ◻

Có thể tạo được bao nhiêu ánh xạ từ tập \(A\) có \(m\) phần tử vào tập \(B\) có \(n\) phần tử?

Proof. Lời giải. Theo định nghĩa, một ánh xạ xác định trên \(A\) có giá trị trên \(B\) là một phép tương ứng mỗi phần tử của \(A\) với một phần tử nào đó của \(B\). Rõ ràng sau khi đã chọn được ảnh của \(i-1\) phần tử đầu, để chọn ảnh của phần tử thứ \(i\) của \(A\) ta có \(n\) cách. Vì vậy theo quy tắc nhân, ta có \(n.n...n=n^{m}\) ánh xạ xác định trên \(A\) nhận giá trị trên \(B\). ◻

Có bao nhiêu đơn ánh xác định trên tập \(A\) có \(m\) phần tử và nhận giá trị trên tập \(B\) có \(n\) phần tử?

Proof. Lời giải. Nếu \(m>n\) thì với mọi ánh xạ, ít nhất có hai phần tử của \(A\) có cùng một ảnh, điều đó có nghĩa là không có đơn ánh từ \(A\) đến \(B\). Bây giờ giả sử \(m\leq n\) và gọi các phần tử của \(A\) là \(a_{1},a_{2},...,a_{m}\). Rõ ràng có \(n\) cách chọn ảnh cho phần tử \(a_{1}\). Vì ánh xạ là đơn ánh nên ảnh của phần tử \(a_{2}\) phải khác ảnh của \(a_{1}\) nên chỉ có \(n-1\) cách chọn ảnh cho phần tử \(a_{2}\). Nói chung, để chọn ảnh của \(a_{k}\) ta có \(n-k+1\) cách. Theo quy tắc nhân, ta có \[n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}\] đơn ánh từ tập A đến tập B. ◻

Giá trị của biến \(m\) bằng bao nhiêu sau khi đoạn chương trình Python sau được thực hiện?

m = 0 
for i1 in range(n1):
    for i2 in range(n2):
        ...
            for ik in range(nk):
                m += 1

Proof. Lời giải. Giá trị khởi tạo của \(m\) bằng 0. Ta có k vòng lặp được lồng nhau. Gọi \(T_{i}\) là việc thi hành vòng lặp thứ \(i\). Khi đó số lần đi qua vòng lặp bằng số cách làm các việc \(T_{1},T_{2},...,T_{k}\). Số cách thực hiện việc \(T_{j}\) là \(n_{j}\) với \((j=1,2,...,k)\), vì vòng lặp thứ \(j\) được duyệt với mỗi giá trị nguyên \(i_{j}\) nằm giữa 1 và \(n_{j}\). Theo quy tắc nhân vòng lặp lồng nhau này được duyệt qua \(n_{1}.n_{2}...n_{k}\) lần. Vì vậy giá trị cuối cùng của \(m\) là \(n_{1}.n_{2}...n_{k}\). ◻

Ngôn ngữ tập hợp

Nếu \(A_{1},A_{2},...,A_{k}\) là các tập hữu hạn, khi đó số phần tử của tích Descartes của các tập này bằng tích của số các phần tử của mọi tập thành phần. Ta biết rằng việc chọn một phần tử của tích Descartes \(A_{1}\times A_{2}\times...\times A_{k}\) được tiến hành bằng cách chọn lần lượt một phần tử của \(A_{1}\), một phần tử của \(A_{2}\),..., một phần tử của \(A_{k}\). Theo quy tắc nhân ta có: \(|A_{1}\times A_{2}\times...\times A_{k}|=|A_{1}|.|A_{2}|...|A_{k}|\).

1.1.2 Nguyên lý bù trừ

Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc.

Ngôn ngữ tập hợp.

Cho \(A_{1},A_{2}\) là hai tập hữu hạn, khi đó \[|A_{1}\cup A_{2}|=|A_{1}|+|A_{2}|-|A_{1}\cap A_{2}|\]
Từ đó với ba tập hợp hữu hạn \(A_{1},A_{2},A_{3}\), ta có: \[|A_{1}\cup A_{2}\cup A_{3}|=|A_{1}|+|A_{2}|+|A_{3}|-|A_{1}\cap A_{2}|-|A_{2}\cap A_{3}|-|A_{3}\cap A_{1}|+|A_{1}\cap A_{2}\cap A_{3}|\]
Bằng quy nạp, với \(k\) tập hữu hạn \(A_{1},A_{2},...,A_{k}\) ta có: \[|A_{1}\cup A_{2}\cup...\cup A_{k}|=N_{1}-N_{2}+N_{3}-...+(-1)^{k-1}N_{k}\] trong đó \(N_{m}(m=1,...,k)\) là tổng phần tử của tất cả các giao \(m\) tập lấy từ \(k\) tập đã cho, nghĩa là \[N_{m}=\sum_{1\leq i_{1}<i_{2}<...<i_{m}\leq k}A_{i_{1}}\cap A_{i_{2}}\cap...\cap A_{i_{m}}\]
Bây giờ ta đồng nhất tập \(A_{m}(1\le m\leq k)\) với tính chất \(A_{m}\) cho trên tập vũ trụ hữu hạn \(U\) nào đó và đếm xem có bao nhiêu phần tử của U sao cho không thỏa mãn bất kỳ một tính chất \(Am\) nào. Gọi \(\bar{N}\) là số cần đếm, \(N\) là số phần tử của \(U\). Ta có: \[N=N-|A_{1}\cup A_{2}\cup...\cup A_{k}|=N-N_{1}+N_{2}-N_{3}+...+(-1)^{k}N_{k}\] trong đó \(N_{m}\) là tổng các phần tử của \(U\) thỏa mãn \(m\) tính chất lấy từ \(k\) tính chất đã cho. Công thức này được gọi là nguyên lý bù trừ. Nó cho phép tính \(\bar{N}\) qua các \(N_{m}\).

Có \(n\) lá thư và \(n\) phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì. Hỏi xác suất để xảy ra không một lá thư nào đúng địa chỉ.

Proof. Lời giải. Mỗi phong bì có \(n\) cách bỏ thư vào, nên có tất cả \(n!\) cách bỏ thư. Vấn đề còn lại là đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ. Gọi \(U\) là tập hợp các cách bỏ thư và \(A_{m}\) là tính chất lá thư thứ m bỏ đúng địa chỉ. Khi đó theo công thức về nguyên lý bù trừ ta có: \[\bar{N}=n!-N_{1}+N_{2}-...+(-1)^{n}N_{n}\] trong đó \(N_{m}(1\le m\leq n)\) là số tất cả các cách bỏ thư sao cho có \(m\) lá thư đúng địa chỉ. Nhận xét rằng, \(N_{m}\) là tổng theo mọi cách lấy \(m\) lá thư từ \(n\) lá, với mỗi cách lấy \(m\) lá thư, có \((n-m)!\) cách bỏ để m lá thư này đúng địa chỉ, ta nhận được: \[N_{m}=\binom{n}{m}(n-m)!=\frac{n!}{m!}\] và \[\bar{N}=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-...+(-1)^{n}\frac{1}{n!}\right)\] Từ đó xác suất cần tìm là \[P=1-\frac{1}{1!}+\frac{1}{2!}-...+(-1)^{n}\frac{1}{n!}\to\frac{1}{e}\] khi \(n\) khá lớn. ◻

\(n\)	2	3	4	5	6	7	8	9	10	11
\(\bar{N}\)	1	2	9	44	265	1854	14833	133496	1334961	14684570

1.2 Nguyên lý Dirichlet

1.2.1 Giới thiệu

Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim. Nguyên lý này dĩ nhiên là có thể áp dụng cho các đối tượng không phải là chim bồ câu và chuồng chim.

Nếu có \(k+1\) (hoặc nhiều hơn) đồ vật được đặt vào trong \(k\) hộp thì tồn tại một hộp có ít nhất hai đồ vật.

Proof. Proof. Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó tổng số vật được chứa trong các hộp nhiều nhất là bằng \(k\). Điều này trái giả thiết là có ít nhất \(k+1\) vật. ◻

Nguyên lý này thường được gọi là nguyên lý Dirichlet, mang tên nhà toán học người Đức ở thế kỷ 19. Ông thường xuyên sử dụng nguyên lý này trong công việc của mình.

Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có ngày sinh nhật giống nhau.

Proof. Lời giải. Bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau. ◻

Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất có bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau?

Proof. Lời giải. Theo nguyên lý Dirichlet, số học sinh cần tìm là 102, vì ta có 101 kết quả điểm thi khác nhau ◻

Trong số những người có mặt trên trái đất, phải tìm được hai người có hàm răng giống nhau.

Proof. Lời giải. Nếu xem mỗi hàm răng gồm 32 cái như là một chuỗi nhị phân có chiều dài 32, trong đó răng còn ứng với bit 1 và răng mất ứng với bit 0, thì có tất cả \(2^{32}=4294967296\) hàm răng khác nhau. Trong khi đó số người trên hành tinh này là vượt quá 7 tỉ, nên theo nguyên lý Dirichlet ta có điều cần tìm. ◻

1.2.2 Nguyên lý Dirichlet tổng quát

Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất \(\left\lceil \frac{N}{k}\right\rceil\) đồ vật.

Proof. Proof. Giả sử mọi hộp đều chứa ít hơn \(\left\lceil \frac{N}{k}\right\rceil\) vật. Khi đó tổng số đồ vật là \(\leq k\left(\left\lceil \frac{N}{k}\right\rceil -1\right)<k.\frac{N}{k}=N\). Điều này mâu thuẩn với giả thiết là có \(N\) đồ vật cần xếp. ◻

Xét một số ví dụ đơn giản sau

Trong 100 người, có ít nhất 9 người sinh cùng một tháng. Xếp những người sinh cùng tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirichlet, tồn tại một nhóm có ít nhất \(\left\lceil \frac{100}{12}\right\rceil\)= 9 người.
Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là 6 người cùng nhận học bổng như nhau. Gọi \(N\) là số sinh viên, khi đó \(\left\lceil \frac{N}{5}\right\rceil =6\) khi và chỉ khi \(5<\frac{N}{5}\leq6\) hay \(25<N\leq30\). Vậy số \(N\) cần tìm là 26.
Số mã vùng cần thiết nhỏ nhất phải là bao nhiêu để đảm bảo 25 triệu máy điện thoại trong nước có số điện thoại khác nhau, mỗi số có 9 chữ số (giả sử số điện thoại có dạng 0XX - 8XXXXX với X nhận các giá trị từ 0 đến 9). Có \(10^{7}=10.000.000\) số điện thoại khác nhau có dạng 0XX - 8XXXXX. Vì vậy theo nguyên lý Dirichlet tổng quát, trong số 25 triệu máy điện thoại ít nhất có \(\left\lceil \frac{25.000.000}{10.000.000}\right\rceil =3\) có cùng một số. Để đảm bảo mỗi máy có một số cần có ít nhất 3 mã vùng.

1.2.3 Một số ứng dụng của nguyên lý Dirichlet

Trong nhiều ứng dụng thú vị của nguyên lý Dirichlet, khái niệm đồ vật và hộp cần phải được lựa chọn một cách khôn khéo. Trong phần nay có vài thí dụ như vậy.

Trong một phòng họp có \(n\) người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau. Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến \(n-1\).

Proof. Lời giải. Rõ ràng trong phòng không thể đồng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen là \(n-1\) (tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân \(n\) người ra thành \(n-1\) nhóm. Vậy theo nguyên lý Dirichlet tồn tại một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có số người quen là như nhau. ◻

Trong một tháng gồm 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trận nhưng chơi không quá 45 trận. Chứng minh rằng tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận.

Proof. Lời giải. Gọi \(a_{j}\) là số trận mà đội đã chơi từ ngày đầu tháng đến hết ngày \(j\). Khi đó \[1\leq a_{1}<a_{2}<...<a_{30}<45\] \[15\leq a_{1}+14<a_{2}+14<...<a_{30}+14<59\] Sáu mươi số nguyên \(a_{1},a_{2},...,a_{30},a_{1}+14,a_{2}+14,...,a_{30}+14\) nằm giữa 1 và 59. Do đó theo nguyên lý Dirichlet có ít nhất 2 trong 60 số này bằng nhau. Vì vậy tồn tại \(i\) và \(j\) sao cho \(a_{i}=a_{j}+14(j<i)\). Điều này có nghĩa là từ ngày \(j+1\) đến hết ngày \(i\) đội đã chơi đúng 14 trận. ◻

Chứng tỏ rằng trong \(n+1\) số nguyên dương không vượt quá \(2n\), tồn tại ít nhất một số chia hết cho số khác.

Proof. Lời giải. Ta viết mỗi số nguyên \(a_{1},a_{2},...,a_{n+1}\) dưới dạng \(a_{j}=2^{k_{j}}q_{j}\) trong đó \(k_{j}\) là số nguyên không âm còn \(q_{j}\) là số dương lẻ nhỏ hơn \(2n\). Vì chỉ có \(n\) số nguyên dương lẻ nhỏ hơn \(2n\) nên theo nguyên lý Dirichlet tồn tại \(i\) và \(j\) sao cho \(q_{i}=q_{j}=q\). Khi đó \(a_{i}=2^{k_{i}}q\) và \(a_{j}=2^{k_{j}}q\). Vì vậy, nếu \(k_{i}\leq k_{j}\) thì \(a_{j}\) chia hết cho \(a_{i}\) còn trong trường hợp ngược lại ta có \(a_{i}\) chia hết cho \(a_{j}\). ◻

Thí dụ cuối cùng trình bày cách áp dụng nguyên lý Dirichlet vào lý thuyết tổ hợp mà vẫn quen gọi là lý thuyết Ramsey, tên của nhà toán học người Anh. Nói chung, lý thuyết Ramsey giải quyết những bài toán phân chia các tập con của một tập các phần tử.

Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau.

Proof. Lời giải. Gọi \(A\) là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của \(A\) hoặc có ít nhất ba người là kẻ thù của \(A\), điều này suy ra từ nguyên lý Dirichlet tổng quát, vì \(\left\lceil \frac{5}{2}\right\rceil =3\). Trong trường hợp đầu ta gọi \(B,C,D\) là bạn của \(A\). nếu trong ba người này có hai người là bạn thì họ cùng với \(A\) lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người \(B,C,D\) không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau. Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ thù của \(A\). ◻

1.3 Chỉnh hợp và tổ hợp

1.3.1 Chỉnh hợp có lặp

Một cách sắp xếp có thứ tự \(k\) phần tử có thể lặp lại của một tập \(n\) phần tử được gọi là một chỉnh hợp lặp chập \(k\) từ tập \(n\) phần tử. Nếu \(A\) là tập gồm \(n\) phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập \(A_{n}^{k}\). Ngoài ra, mỗi chỉnh hợp lặp chập \(k\) từ tập \(n\) phần tử là một hàm từ tập \(k\) phần tử vào tập \(n\) phần tử. Vì vậy số chỉnh hợp lặp chập \(k\) từ tập \(n\) phần tử là \(n^{k}\).

1.3.2 Tổ hợp có lặp

Một tổ hợp lặp chập \(k\) của một tập hợp là một cách chọn không có thứ tự \(k\) phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểu này là một dãy không kể thứ tự gồm \(k\) thành phần lấy từ tập \(n\) phần tử. Do đó có thể là \(k>n\).

Số tổ hợp lặp chập \(k\) từ tập \(n\) phần tử bằng \(\binom{k}{n+k-1}\).

Proof. Proof. Mỗi tổ hợp lặp chập \(k\) từ tập \(n\) phần tử có thể biểu diễn bằng một dãy \(n\) ô và \(k\) ngôi sao. Ô thứ \(i\) chứa thêm một ngôi sao mỗi lần khi phần tử thứ \(i\) của tập xuất hiện trong tổ hợp. Chẳng hạn, tổ hợp lặp chập 6 của 4 phần tử được biểu thị bằng một dãy gồm 4 ô.

`* *`	`*`		`* * *`

Hình trên mô tả tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử thứ hai, không có phần tử thứ 3 và 3 phần tử thứ tư của tập hợp. Mỗi dãy \(n\) ô và \(k\) ngôi sao ứng với một chuỗi nhị phân độ dài \(n+k-1\) với \(k\) số 1. Do đó số các dãy \(n\) ô và \(k\) ngôi sao chính là số tổ hợp chập \(k\) từ tập \(n+k-1\) phần tử. Đó là điều cần chứng minh. ◻

Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két đựng tiền gồm những tờ 1000đ, 2000đ, 5000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ.

Proof. Lời giải. Giả sử thứ tự mà các tờ tiền được chọn là không quan trọng, các tờ tiền cùng loại là không phân biệt và mỗi loại có ít nhất 5 tờ. Vì ta không kể tới thứ tự chọn tờ tiền và vì ta chọn đúng 5 lần, mỗi lần lấy một từ 1 trong 7 loại tiền nên mỗi cách chọn 5 tờ giấy bạc này chính là một tổ hợp lặp chập 5 từ 7 phần tử. Do đó số cần tìm là \(\binom{5}{5+7-1}=462\). ◻

Phương trình \(x_{1}+x_{2}+x_{3}=15\) có bao nhiêu nghiệm nguyên không âm?

Proof. Lời giải. Chúng ta nhận thấy mỗi nghiệm của phương trình ứng với một cách chọn 15 phần tử từ một tập có 3 loại, sao cho có \(x_{1}\) phần tử loại 1, \(x_{2}\) phần tử loại 2 và \(x_{3}\) phần tử loại 3 được chọn. Vì vậy số nghiệm bằng số tổ hợp lặp chập 15 từ tập có 3 phần tử và bằng \(\binom{15}{15+3-1}=136\). ◻

1.3.3 Hoán vị của tập hợp có các phần tử giống nhau

Trong bài toán đếm, một số phần tử có thể giống nhau. Khi đó cần phải cẩn thận, tránh đếm chúng hơn một lần. Ta xét thí dụ sau.

Có thể nhận được bao nhiêu chuỗi khác nhau bằng cách sắp xếp lại các chữ cái của từ SUCCESS?

Proof. Lời giải. Vì một số chữ cái của từ SUCCESS là như nhau nên câu trả lời không phải là số hoán vị của 7 chữ cái được. Từ này chứa 3 chữ S, 2 chữ C, 1 chữ U và 1 chữ E. Để xác định số chuỗi khác nhau có thể tạo ra được ta nhận thấy có \(\binom{3}{7}\) cách chọn 3 chỗ cho 3 chữ S, còn lại 4 chỗ trống. Có \(\binom{2}{4}\) cách chọn 2 chỗ cho 2 chữ C, còn lại 2 chỗ trống. Có thể đặt chữ U bằng \(\binom{1}{2}\) cách và \(\binom{1}{1}\) cách đặt chữ E vào chuỗi. Theo nguyên lý nhân, số các chuỗi khác nhau có thể tạo được là: \[\binom{3}{7}\binom{2}{4}\binom{1}{2}\binom{1}{1}=\frac{7!4!2!1!}{3!4!2!2!1!1!1!0!}=\frac{7!}{3!2!1!1!}=420.\] ◻

Số hoán vị của \(n\) phần tử trong đó có \(n_{1}\) phần tử như nhau thuộc loại 1, \(n_{2}\) phần tử như nhau thuộc loại 2,..., và \(n_{k}\) phần tử như nhau thuộc loại \(k\), là \[\frac{n!}{n_{1}!n_{2}!\ldots n_{k}!}\]

Proof. Proof. Để xác định số hoán vị trước tiên chúng ta nhận thấy có \(\binom{n_{1}}{n}\) cách giữ \(n_{1}\) chỗ cho \(n_{1}\) phần tử loại 1, còn lại \(n-n_{1}\) chỗ trống. Sau đó có \(\binom{n_{2}}{n-n_{1}}\) cách đặt \(n_{2}\) phần tử loại 2 vào hoán vị, còn lại \(n-n_{1}-n_{2}\) chỗ trống. Tiếp tục đặt các phần tử loại 3, loại 4,..., loại \(k-1\) vào chỗ trống trong hoán vị. Cuối cùng có \(\binom{n_{k}}{n-n_{1}-n_{2}-...-n_{k-1}}\) cách đặt \(n_{k}\) phần tử loại \(k\) vào hoán vị. Theo quy tắc nhân tất cả các hoán vị là

\[\binom{n_{1}}{n}\binom{n_{2}}{n-n_{1}}...\binom{n_{k}}{n-n_{1}-...-n_{k-1}}=\frac{n!}{n_{1}!n_{2}!\ldots n_{k}!}\] ◻

1.3.4 Sự phân bố các đồ vật vào trong hộp

Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân?

Proof. Lời giải. Người đầu tiên có thể nhận được 5 quân bài bằng \(\binom{5}{32}\) cách. Người thứ hai có thể được chia 5 quân bài bằng \(\binom{5}{47}\) cách, vì chỉ còn 47 quân bài. Người thứ ba có thể nhận được 5 quân bài bằng \(\binom{5}{42}\) cách. Cuối cùng, người thứ tư nhận được 5 quân bài bằng \(\binom{5}{37}\) cách. Vì vậy, theo nguyên lý nhân tổng cộng có \[\binom{5}{52}\binom{5}{47}\binom{5}{42}\binom{5}{37}=\frac{52!}{5!5!5!5!32!}\] cách chia cho 4 người mỗi người một xấp 5 quân bài. ◻

Thí dụ trên là một bài toán điển hình về việc phân bố các đồ vật khác nhau vào các hộp khác nhau. Các đồ vật là 52 quân bài, còn 4 hộp là 4 người chơi và số còn lại để trên bàn. Số cách sắp xếp các đồ vật vào trong hộp được cho bởi mệnh đề sau

Số cách phân chia \(n\) đồ vật khác nhau vào trong \(k\) hộp khác nhau sao cho có \(n_{i}\) vật được đặt vào trong hộp thứ \(i\), với \(i=1,2,...,k\) là \[\frac{n!}{n_{1}!n_{2}!\ldots n_{k}!(n-n_{1}-n_{2}-\ldots-n_{k})!}\]

1.4 Sinh các hoán vị và tổ hợp

1.4.1 Sinh các hoán vị

Có nhiều thuật toán đã được phát triển để sinh ra \(n!\) hoán vị của tập \(\left\{ 1,2,...,n\right\}\). Ta sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê các hoán vị của tập \(\left\{ 1,2,...,n\right\}\) theo thứ tự từ điển.

Khi đó, hoán vị \(a_{1}a_{2}...a_{n}\) được gọi là đi trước hoán vị \(b_{1}b_{2}...b_{n}\) nếu tồn tại \(k(1\leq k\leq n),a_{1}=b_{1},a_{2}=b_{2},...,a_{k-1}=b_{k-1}\) và \(a_{k}<b_{k}\).

Thuật toán sinh các hoán vị của tập \(\left\{ 1,2,...,n\right\}\) dựa trên thủ tục xây dựng hoán vị kế tiếp, theo thứ tự từ điển, từ hoán vị cho trước \(a_{1}a_{2}...a_{n}\).

Đầu tiên nếu \(a_{n-1}<a_{n}\) thì rõ ràng đổi chỗ \(a_{n-1}\) và \(a_{n}\) cho nhau thì sẽ nhận được hoán vị mới đi liền sau hoán vị đã cho. Nếu tồn tại các số nguyên \(a_{j}\) và \(a_{j+1}\) sao cho \(a_{j}<a_{j+1}\) và \(a_{j+1}>a_{j+2}>...>a_{n}\), tức là tìm cặp số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số đầu nhỏ hơn số sau. Sau đó, để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn \(a_{j}\) của tập \(a_{j+1},a_{j+2},...,a_{n}\), rồi liệt kê theo thứ tự tăng dần của các số còn lại của \(a_{j},a_{j+1},a_{j+2},...,a_{n}\) vào các vị trí \(j+1,...,n\). Dễ thấy không có hoán vị nào đi sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra.

Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 4736521.

Proof. Lời giải. Cặp số nguyên đầu tiên tính từ phải qua trái có số trước nhỏ hơn số sau là a 3 = 3 và a 4 = 6. Số nhỏ nhất trong các số bên phải của số 3 mà lại lớn hơn 3 là số 5. Đặt số 5 vào vị trí thứ 3. Sau đó đặt các số 3, 6, 1, 2 theo thứ tự tăng dần vào bốn vị trí còn lại. Hoán vị liền sau hoán vị đã cho là 4751236. ◻

Mã python phát sinh hoán vị liền sau:

def DoiCho(a, i, j):
    a[i], a[j] = a[j], a[i]

def HoanViLienSau(a):
    n = len(a)
    j = n - 2
    while a[j] > a[j+1]:
        j -= 1
    k = n - 1
    while a[j] > a[k]:
        k -= 1
    DoiCho(a, j, k)
    r = n - 1
    l = j + 1
    while l < r:
        DoiCho(a, l, r)
        l += 1
        r -= 1      

a = [4, 7, 3, 6, 5, 2, 1]
HoanViLienSau(a)
print(a)

kết quả chạy sẽ in ra màn hình

[4, 7, 5, 1, 2, 3, 6]

1.4.2 Sinh các tổ hợp

Làm thế nào để tạo ra tất cả các tổ hợp các phần tử của một tập hữu hạn? Vì tổ hợp chính là một tập con, nên ta có thể dùng phép tương ứng 1-1 giữa các tập con của \(\left\{ a_{1},a_{2},...,a_{n}\right\}\) và chuỗi nhị phân độ dài \(n\). Ta thấy một chuỗi nhị phân độ dài \(n\) cũng là khai triển nhị phân của một số nguyên nằm giữa 0 và \(2^{n}-1\). Khi đó \(2^{n}\) chuỗi nhị phân có thể liệt kê theo thứ tự tăng dần của số nguyên trong biểu diễn nhị phân của chúng. Chúng ta sẽ bắt đầu từ chuỗi nhị phân nhỏ nhất 00...00 (\(n\) số 0). Mỗi bước để tìm chuỗi liền sau ta tìm vị trí đầu tiên tính từ phải qua trái mà ở đó là số 0, sau đó thay tất cả số 1 ở bên phải số này bằng 0 và đặt số 1 vào chính vị trí này.

Mã python để phát sinh chuỗi nhị phân liền sau:

def ChuoiNhiPhanLienSau(b):
    i = 0
    while b[i] == 1:
        b[i] = 0 
        i += 1
    b[i] = 1

b = [0, 1, 1, 0, 0]
ChuoiNhiPhanLienSau(b)
print(b)

kết quả chạy sẽ in ra màn hình

[1, 1, 1, 0, 0]

Tiếp theo chúng ta sẽ trình bày thuật toán tạo các tổ hợp chập \(k\) từ \(n\) phần tử \(\left\{ 1,2,...,n\right\}\). Mỗi tổ hợp chập \(k\) có thể biểu diễn bằng một chuỗi tăng. Khi đó có thể liệt kê các tổ hợp theo thứ tự từ điển. Có thể xây dựng tổ hợp liền sau tổ hợp \(a_{1}a_{2}...a_{k}\) bằng cách sau. Trước hết, tìm phần tử đầu tiên \(a_{i}\) trong dãy đã cho kể từ phải qua trái sao cho \(a_{i}\neq n-k+i\). Sau đó thay \(a_{i}\) bằng \(a_{i+1}\) và \(a_{j}\) bằng \(a_{i}+j-i+1\) với \(j=i+1,i+2,...,k\).

Tìm tổ hợp chập 4 từ tập {1, 2, 3, 4, 5, 6} đi liền sau tổ hợp {1, 2, 5, 6}.

Proof. Lời giải. Ta thấy từ phải qua trái \(a_{2}=2\) là số hạng đầu tiên của tổ hợp đã cho thỏa mãn điều kiện \(a_{i}\neq6-4+i\). Để nhận được tổ hợp tiếp sau ta tăng \(a_{i}\) lên một đơn vị, tức \(a_{2}=3\), sau đó đặt \(a_{3}=3+1=4\) và \(a_{4}=3+2=5\). Vậy tổ hợp liền sau tổ hợp đã cho là {1, 3, 4, 5}. ◻

Thủ tục này được cài đặt bằng mã python như sau:

def ToHopLienSau(a, n, k):
    i = k - 1
    while a[i] == n - k + i + 1:
        i -= 1
    a[i] = a[i] + 1
    for j in range(i + 1, k):
        a[j] = a[i] + j - i

a = [1, 2, 5, 6]
ToHopLienSau(a, 6, 4)
print(a)

kết quả chạy sẽ in ra màn hình

[1, 3, 4, 5]

Chương này đã trình bày những vấn đề cơ bản nhất của lý thuyết tổ hợp, bao gồm:

Việc sử dụng hai nguyên lý đếm căn bản là nguyên lý cộng và nguyên lý nhân để giải quyết những bài toán cơ bản
Vận dụng các công thức liên quan đến chỉnh hợp và tổ hợp để đếm trong các trường hợp phức tạp hơn
Áp dụng nguyên lý Dirichlet để giải quyết những bài toán liên quan đến vấn đề tồn tại

1.5 ✏️ Bài tập

Tập hợp

Cho dãy tập hợp \(A_{1},A_{2},...,A_{n},...\). Chứng minh rằng luôn luôn tồn tại dãy tập hợp \(B_{1},B_{2},...,B_{n},...\), sao cho:

Các \(B_{i}\) từng đôi một rời nhau;
\(\cup_{i=1}^{\infty}A_{i}=\cup_{k=1}^{\infty}B_{k}.\)

Chứng minh rằng các hệ thức sau đây tương đương nếu \(A\) và \(B\) là tập hợp con của \(\Omega\):

\(A\cup B=\Omega,A\subset B,B\subset A.\)

Khẳng định cho rằng nếu \(A,B,C\) là tập hợp con của tập hợp \(\Omega\) sao cho \(A\subset B\cup C\) và \(B\subset A\cup C\), thì \(B=\emptyset\), có đúng không?

Chứng minh rằng nếu \(A,B,C\) là các tập hợp con của tập hợp \(\Omega\), sao cho \(A\cap B\subset C\) và \(A\cup C\subset B\), thì \(A\cap C=\emptyset\)

Tìm biểu thức đơn giản của các biểu thức sau:

\((A\cup B)(A\cup C)\)
\((A\cup B)(A\cup\overline{B})\)
\((A\cup B)(\overline{A}\cup B)(A\cup\overline{B})\)
\((A\cup B)(\overline{A}\cup B)(\overline{A}\cup\overline{B})\)
\((A\cup B)(B\cup C)\)

Hệ thức nào trong các hệ thức sau đây đúng

\(A\cup B\cup C=A\cup(B\setminus AB)\cup(C\setminus AC)\)
\(A\cup B=(A\setminus AB)\cup B\)
\((A\cup B)\setminus A=B\)
\((A\cup B)\setminus C=A\cup(B\setminus C)\)
\(ABC=AB(C\cup B)\)
\(AB\cup BC\cup CA\supset ABC\)
\((AB\cup BC\cup CA)\subset(A\cup B\cup C)\)
\(ABC\subset A\cup B\)
\(A\cup BC=AC\cup BC\)
\(A\cup BC=C\setminus(C(A\cup B))\)

Chứng minh rằng:

\(\overline{\overline{A}\cup\overline{B}}\cup\overline{\overline{A}\cup B}=A\)
\((A\cup B)\overline{AB}=A\overline{B}\cup B\overline{A}\)

Chứng minh

Nếu \(A\cup B=AB\) thì \(A=B\)
\(A\cup BC\supset(A\cup B)C\)
Nếu \(A_{1}\subset A,B_{1}\subset B\) và \(A\cap B=\emptyset\) thì \(A_{1}\cap B_{1}=\emptyset\)

Giải tích tổ hợp

Một lô hàng có 50 sản phẩm.

Có bao nhiêu cách chọn ngẫu nhiên cùng lúc 5 sản phẩm để kiểm tra?
Có bao nhiêu cách chọn ngẫu nhiên lần lượt 5 sản phẩm?

Trong một hệ thống điện thoại nội bộ 3 số

có bao nhiêu máy có các chữ số khác nhau?
Có bao nhiêu máy có số 9 ở cuối còn các chữ số còn lại đều khác nhau?

Một lớp học có 40 học sinh gồm 20 nam và 20 nữ. Có bao nhiêu cách chia để trong mỗi nửa lớp có 10 nam sinh và 10 nữ sinh?

Nếu một người có 6 đôi vớ khác nhau và 4 đôi giày khác nhau. Có bao nhiêu cách kết hợp giữa vớ và giày?

Năm người A, B, C, D, E sẽ phát biểu trong một hội nghị. Có bao nhiêu cách sắp xếp để:

Người B phát biểu sau A.
Người A phát biểu xong thì đến lượt B.

Có 6 học sinh được sắp xếp ngồi vào 6 chỗ đã ghi số thứ tự trên một bàn dài. Tìm số cách xếp

6 học sinh vào bàn.
6 học sinh này vào bàn sao cho 2 học sinh A, B ngồi cạnh nhau.
6 học sinh này ngồi vào bàn sao cho 2 học sinh A, B không ngồi cạnh nhau.

Một lớp có 40 học sinh. Giáo viên chủ nhiệm muốn chọn ra một ban cán sự lớp: 1 lớp trưởng, 1 lớp phó, 1 thủ quỹ. Hỏi giáo viên chủ nhiệm có bao nhiêu cách chọn ban cán sự lớp?

Một hộp có 8 bi đỏ, 6 bi trắng, 4 bi vàng. Người ta chọn ra 6 bi từ hộp đó. Hỏi có bao nhiêu cách chọn nếu:

Không yêu cầu gì thêm.
Phải có 2 bi đỏ, 2 bi trắng, 2 bi vàng.
Có đúng 2 bi vàng.

Một đồn cảnh sát khu vực có 9 người. Trong ngày cần cử 3 người làm nhiệm vụ ở địa điểm A, 2 người ở địa điểm B còn 4 người trực tại đồn. Hỏi có bao nhiêu cách phân công?

Một tổ sản xuất có 12 người, trong đó có 4 nữ, cần chia thành 4 nhóm đều nhau. Hãy tìm số cách phân chia sao cho mỗi nhóm có 1 nữ?

Xếp 12 hành khách lên 4 toa tàu. Tìm số cách sắp xếp:

Mỗi toa có 3 hành khách.
Một toa có 6 hành khách, một toa có 4 hành khách, 2 toa còn lại mỗi toa có 1 hành khách.

Có bao nhiêu chuỗi 8 bit đối xứng?

Có 6 sách tin học, 4 sách toán học, 3 sách vật lý

Có bao nhiêu nhiêu cách sắp xếp chúng lên giá sách?
Có bao nhiêu cách sắp xếp chúng lên giá sách sao cho tất cả các sách cùng nhóm thì được xếp kề nhau?
Có bao nhiêu cách sắp xếp để 2 sách toán không kề nhau?

Một tổ chức gồm 7 nam và 8 nữ

Có bao nhiêu cách chọn một hội đồng gồm 5 người?
Có bao nhiêu cách chọn hội đồng gồm 2 nam và 3 nữ?
Có bao nhiêu cách chọn hội đồng gồm 4 người và phải có ít nhất 1 nữ?
Có bao nhiêu cách chọn hội đồng gồm 5 người và phải có cả nam và nữ?

Trong tổng số 2504 sinh viên của một khoa công nghệ thông tin, có 1876 theo học môn ngôn ngữ lập trình Pascal, 999 học môn ngôn ngữ Fortran và 345 học ngôn ngữ C. Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C, 290 học cả Pascal và C. Nếu 189 sinh viên học cả 3 môn Pascal, Fortran và C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong 3 môn ngôn ngữ lập trình kể trên.

Một cuộc họp gồm 12 người tham dự để bàn về 3 vấn đề. Có 8 người phát biểu về vấn đề I, 5 người phát biểu về vấn đề II và 7 người phát biểu về vấn đề III. Ngoài ra, có đúng 1 người không phát biểu vấn đề nào. Hỏi nhiều lắm là có bao nhiêu người phát biểu cả 3 vấn đề.

Chỉ ra rằng có ít nhất 4 người trong số 25 triệu người có cùng tên họ viết tắt bằng 3 chữ cái sinh cùng ngày trong năm (không nhất thiết trong cùng một năm).

Một tay đô vật tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta có ít nhất một trận đấu, nhưng toàn bộ anh ta có không quá 125 trận. Chứng tỏ rằng có những giờ liên tiếp anh ta đã đấu đúng 24 trận.

Cho \(n\) là số nguyên dương bất kỳ. Chứng minh rằng luôn lấy ra được từ \(n\) số đã cho một số số hạng thích hợp sao cho tổng của chúng chia hết cho \(n\).

Trong một cuộc lấy ý kiến về 7 vấn đề, người được hỏi ghi vào một phiếu trả lời sẵn bằng cách để nguyên hoặc phủ định các câu trả lời tương ứng với 7 vấn đề đã nêu. Chứng minh rằng với 1153 người được hỏi luôn tìm được 10 người trả lời giống hệt nhau.

Có 17 nhà bác học viết thư cho nhau trao đổi 3 vấn đề. Chứng minh rằng luôn tìm được 3 người cùng trao đổi một vấn đề.

Trong kỳ thi kết thúc học phần toán học rời rạc có 10 câu hỏi. Có bao nhiêu cách gán điểm cho các câu hỏi nếu tổng số điểm bằng 100 và mỗi câu ít nhất được 5 điểm.

Phương trình \(x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=21\) có bao nhiêu nghiệm nguyên không âm?

Có bao nhiêu số nguyên trong tập \(\{1,2,...,100000\}\) có tổng chữ số là 16

Có bao nhiêu chuỗi khác nhau có thể lập được từ các chữ cái trong từ MISSISSIPI, yêu cầu phải dùng tất cả các chữ?

Một giáo sư cất bộ sưu tập gồm 40 số báo toán học vào 4 chiếc ngăn tủ, mỗi ngăn đựng 10 số. Có bao nhiêu cách có thể cất các tờ báo vào các ngăn nếu:

Mỗi ngăn được đánh số sao cho có thể phân biệt được;
Các ngăn là giống hệt nhau?

Có thể nối năm máy tính với nhau sao cho có chính xác hai máy tính được nối trực tiếp đến cùng số máy? Hãy giải thích lý do.

Một bàn cờ kích thước \(3\times7\) gồm 21 ô hình vuông, mỗi hình vuông được tô màu đen hoặc màu trắng. Chứng minh rằng bàn cờ chứa một hình chữ nhật không tầm thường (có kích thước \(1\times k\) hoặc \(k\times1\)) sao cho 4 hình vuông ở bốn góc hoặc tất cả tô màu đen hoặc tất cả tô màu trắn.

Tìm hệ thức truy hồi cho số mất thứ tự \(\bar{N}\).

Tìm hệ thức truy hồi cho số các chuỗi nhị phân chứa chuỗi 01.

Tìm hệ thức truy hồi cho số cách đi lên \(n\) bậc thang nếu một người có thể bước một, hai hoặc ba bậc một lần.

Tìm hệ thức truy hồi mà \(R_{n}\) thoả mãn, trong đó \(R_{n}\) là số miền của mặt phẳng bị phân chia bởi \(n\) đường thẳng nếu không có hai đường nào song song và không có 3 đường nào cùng đi qua một điểm. Tính \(R_{n}\) bằng phương pháp lặp.

Tìm nghiệm của hệ thức truy hồi \(a_{n}=2a_{n-1}+5a_{n-2}-6a_{n-3}\) với \(a_{0}=7,a_{1}=-4,a_{2}=8\).

Giả sử \(m,n,r\) là các số nguyên dương. Chứng minh rằng

\[C_{m}^{0}C_{n-m}^{r}+C_{m}^{1}C_{n-m}^{r-1}+...C_{m}^{r}C_{n-m}^{0}+=C_{n}^{r}\]

Chứng minh rằng

\(C_{n}^{1}+2C_{n}^{2}+...+nC_{n}^{n}=n2^{n-1}\)
\(2.1.C_{n}^{2}+3.2C_{n}^{3}+...+n.(n-1).C_{n}^{n}=n(n-1)2^{n-2}\)

Cho m\(,n,r\) là các số nguyên dương. Chứng minh rằng

\(\sum_{k=0}^{m}C_{n-k}^{r}=C_{n+1}^{r+1}-C_{n-m}^{r+1}\)
\(\sum_{k=0}^{m}(-1)^{k}C_{n}^{k}=(-1)^{m}C_{n-1}^{m}\)

Chứng minh rằng \[\left(C_{n}^{0}\right)^{2}+\left(C_{n}^{1}\right)^{2}+...+\left(C_{n}^{n}\right)^{2}=C_{2n}^{n}\]

Chứng minh rằng \[\sum_{k=0}^{n}\dfrac{2n!}{k!^{2}(n-k)!^{2}}=\left(C_{2n}^{n}\right)^{2}\]

Viết chương trình in ra tất cả các hoán vị của \(n\) số tự nhiên \(\{1,2,...,n\}\)

Viết chương trình in ra tất cả các chỉnh hợp \(k\) của \(n\) số tự nhiên \(\{1,2,...,n\}\)

Viết chương trình in ra tất cả các tổ hợp \(k\) của \(n\) số tự nhiên \(\{1,2,...,n\}\)