Ta thấy rằng con số các viết sách với tập đều lớn hơn số nên mua, cho nên vì vậy bài toán chỉ quay trở về việc đếm là tất cả bao nhiêu cuốn sách viết tập cơ mà tổng số là 5 cái, trong các số ấy mỗi cái có hoặc ko có.
Bạn đang xem: Bài toán chia kẹo
Có ba đối tượng người dùng là viết, sách và tập, tạ kí hiệu là $A = V, S, T $. Một món quà gồm 5 cái, do đó quà có thể là $X = V, V, V, S, T $, tất cả 3 cây viết với 1 sách, 1 tập, hoặc là tập $Y = V, V, S, T, T $, ta thấy các đối tượng người sử dụng $V, T$ là lập lại. Khi đó ta nói tổ hợp $X, Y$ là tổng hợp lặp.
Để khái niệm rõ rộng ta có định nghĩa sau:
Định nghĩa. đến tập $A = a_1, a_2, cdots, a_k $. Một ánh xạ trường đoản cú $p: A mapsto mathbbN $, khi ấy $P$ được gọi là một trong những multiset của A.
Ví dụ 1. cho $A = a, b, c $. Ánh xạ $p: A mapsto mathbbN$ như sau: $p(a) = 2, p(b) = 1, p(c) = 1$. Khi ấy ta hoàn toàn có thể kí hiệu $p$ là $(aabc)$, tốt $(baac)$,.., kế bên đến thứ tự của các bộ phận $a, b, c$.
Đặt $n = p(a_1) + p(a_2)+cdots +p(a_k)$, bài toán đặt ra là có bao nhiêu ánh xạ $p: A mapsto mathbbN$ mà lại $n = p(a_1) + p(a_2)+cdots +p(a_k)$.
Tiếp theo lấy ví dụ như trên, giả dụ $ p(a) + p(b) + p(c) = 2$ thì có những multiset sau: $(ab), (ac), (bc), (aa), (bb), (cc)$, 6 multiset.
Tính chất. Cho tập $A = a_1, a_2, cdots, a_k $, số ánh xạ $p: A mapsto mathbbN$ thỏa $p(a_1) + cdots + p(a_k) = n$ là $C^n_n+k-1$
Mỗi ánh xạ $p$ ta cho tương xứng với một dãy nhị phân độ lâu năm $n+k-1$, trong số đó $p(a_1)$ chữ số đầu là 0, tiếp theo sau là số 1, rồi $p(a_2)$ chữ số $0$,…cuối cùng là $p(a_k)$ chữ số $0$. Ví dụ cỗ $VVSTT$ ứng với dãy $0010100$.
Rõ ràng đấy là tương ứng 1 – 1, vì thế số ánh xạ $p$ thông qua số dãy nhị phân, vì vậy ta chỉ việc đếm số hàng nhị phân.
Ta thấy dãy tất cả $n+k-1$ chữ số trong các số đó có $k-1$ chữ số $1$, vì thế số dãy nhị phân chỉ là số bí quyết chọn vị trí đến $k-1$ chữ số $1$ yêu cầu số hàng nhị phân là $C^k-1_n+k-1$.
Do kia số ánh xạ $p$ là $C^k-1_n+k-1 $
Trở lại việc trên, ta thấy số món quà có 5 cái là một tổ hợp lặp chập 5 của sách, viết, tập, cho nên số món quà rất có thể là $C^2_5+2-1 = C^2_6 = 15$.
(Chú ý trong việc trên, bảo đảm số mỗi một số loại sản phẩm có rất nhiều hơn 5 cái).
Bài toán 1. (Chia kẹo Euler). mang lại $n$ viên kẹo kiểu như nhau đem chia cho $k$ người, hỏi tất cả bao rất nhiều cách chia.
Trước không còn phát cho mỗi người một viên, thì còn $n-k$ viên kẹo, tiếp tục áp dụng bài toán trên cùng với $n-k$. Lúc đó số giải pháp chia là
$C^k-1_n-1$
Ta rất có thể giải bài toán trên mà không cần thực hiện bài toán 1 bằng cách xây dựng hàng nhị phân thỏa: $a_1$ chữ số đầu là 0, tiếp theo là số 1, tiếp là $a_2$ chữ số 0, …., sau cuối là $a_k$ chữ số 0. Dãy này còn có $k-1$ chữ tiên phong hàng đầu đứng giữa $n$ chữ số 0 và không tồn tại hai chữ số $1$ nào đứng kề nhau. Lúc ấy số dãy nhị phân là: $C^k-1_n-1$.
Phần sau đó ta cùng tò mò và giải một trong những bài toán rất có thể đưa về bài toán tổ hợp lặp hay việc chia kẹo Euler. Chúng ta chờ nhé.
Bài toán 1 và 2 hoàn toàn có thể phát biểu bên dưới dạng sau.
Bài toán 3. mang lại phương trình $x_1 + x_2 + cdots + x_k = n$ trong những số ấy $k, n$ là những số nguyên dương.
a. Search số nghiệm tự nhiên và thoải mái của phương trình.
b. Tra cứu số nghiệm nguyên dương của phương trình.
Xem thêm: 5 Bộ Lạc Wakanda Là Gì? Wakanda Đã Mất Đi Một Vị Vua Ý Nghĩa Của
Như bài toán trên ta đang biết, số nghiệm tự nhiên của phương trình là $C^k-1_n+k-1$.