Công thức tính số tổ hợp lặp

[minhcanh2095]

Cho tập $A$ gồm $n$ phần tử. Chứng minh công thức tính số tổ hợp lặp chập $k$ của $n$ phần tử thuộc $A$ là $C_{n + k - 1}^k$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TrauBo]

Nguyên văn bởi minhcanh2095

Cho tập $A$ gồm $n$ phần tử. Chứng minh công thức tính số tổ hợp lặp chập $k$ của $n$ phần tử thuộc $A$ là $C_{n + k - 1}^k$

Khi $k<n$ thì số tổ hợp k chập n là $C_n^k$.
Khi $k>n$ thì theo định nghĩa số cần tìm là số cách chọn $k$ phần tử từ tập gồm $n$ phần tử là $A=\{a_1,a_2,...,a_n\}$.
Như vậy sẽ có ít nhất 1 số được chọn nhiều lần. Gọi $x_i$ là số lần phần tử $a_i$ được chọn thì ta có $$x_1+x_2+...+x_n=k$$
Theo bài toán chia kẹo Euler thì số nghiệm của PT trên là $C_{n + k - 1}^k$.

TrauBo nghĩ thế

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]