Chủ đề này có 4 trả lời

[hoaadc08]

Có bao nhiêu cách chia 20 cái bánh khác nhau cho 5 đứa trẻ sao cho mỗi đứa có ít nhất một cái bánh .

[dottoantap]

Có bao nhiêu cách chia 20 cái bánh khác nhau cho 5 đứa trẻ sao cho mỗi đứa có ít nhất một cái bánh .

Sử dụng công thức tính số Stirling loại 2.

CT tính số Stirling loại 2: Số cách bỏ n cái bánh khác nhau vào k hộp giống nhau sao cho không hộp nào rỗng là:

$S\left ( n,k \right )=\frac{1}{k!}\sum_{j=0}^{k}\left ( -1 \right )^{j}C_{k}^{j}\left ( k-j \right )^{n}$

Do đó số cách chia n=20 cái bánh khác nhau cho k=5 đứa trẻ sao cho mỗi trẻ có ít nhất 1 cái bánh là:

$S\left ( 20,5 \right )=\frac{5!}{5!}\sum_{j=0}^{5}\left ( -1 \right )^{j}C_{5}^{j}\left ( 5-j \right )^{20}=5^{20}-5.4^{20}+10.3^{20}-10.2^{20}+5=89904730860000\text{ cách}$

==========

hoặc dùng nguyên lý bù trừ rồi tính từ từ...

Gọi $S$ là tập các cách chia $n$ cái bánh khác nhau cho $k$ đứa trẻ mà không có ràng buộc nào (tức là có trẻ không được chia bánh)$\Rightarrow\left | S \right |=k^{n}$

Gọi $A_{i}$ là tập các cách chia bánh mà đứa trẻ $i$ không được chia bánh thì:

$\left | A_{i} \right |=C_{k}^{1}\left ( k-1 \right )^{n}$

$\left | A_{i}\cap A_{j} \right |=C_{k}^{2}\left ( k-2 \right )^{n}$

................................

Như vậy, để các trẻ đều có bánh thì số cách chia bánh $N$ thỏa yêu cầu là:

$N=\left | \overline{A_{1}}\cap\overline{A_{2}}\cap...\cap\overline{A_{k}} \right |=\left | \overline{A_{1}\cup A_{2}\cup ...\cup A_{k}} \right |=\left | S \right |-\left | A_{1}\cup A_{2}\cup ...\cup A_{k} \right |$

$\Rightarrow N=k^{n}-C_{k}^{1}\left ( k-1 \right )^{n}+C_{k}^{2}\left ( k-2 \right )^{n}+...+\left ( -1 \right )^{k}C_{k}^{k}\left ( k-k \right )^{n}=\sum_{j=0}^{k}\left ( -1 \right )^{j}C_{k}^{j}\left ( k-j \right )^{n}$     $(*)$

Thế $n=20$ và  $k=5$ vào $(*)$ ta có đáp án.

 

Bài viết đã được chỉnh sửa nội dung bởi dottoantap: 09-10-2018 - 12:17

[dottoantap]

Sử dụng công thức tính số Stirling loại 2.

CT tính số Stirling loại 2: Số cách bỏ n cái bánh khác nhau vào k hộp giống nhau sao cho không hộp nào rỗng là:

$S\left ( n,k \right )=\frac{1}{k!}\sum_{j=0}^{k}\left ( -1 \right )^{j}C_{k}^{j}\left ( k-j \right )^{n}$

Do đó số cách chia n=20 cái bánh khác nhau cho k=5 đứa trẻ sao cho mỗi trẻ có ít nhất 1 cái bánh là:

$S\left ( 20,5 \right )=\frac{5!}{5!}\sum_{j=0}^{5}\left ( -1 \right )^{j}C_{5}^{j}\left ( 5-j \right )^{20}=5^{20}-5.4^{20}+10.3^{20}-10.2^{20}+5=89904730860000\text{ cách}$

==========

hoặc dùng nguyên lý bù trừ rồi tính từ từ...

Gọi $S$ là tập các cách chia $n$ cái bánh khác nhau cho $k$ đứa trẻ mà không có ràng buộc nào (tức là có trẻ không được chia bánh)$\Rightarrow\left | S \right |=k^{n}$

Gọi $A_{i}$ là tập các cách chia bánh mà đứa trẻ $i$ không được chia bánh thì:

$\left | A_{i} \right |=C_{k}^{1}\left ( k-1 \right )^{n}$

$\left | A_{i}\cap A_{j} \right |=C_{k}^{2}\left ( k-2 \right )^{n}$

................................

Như vậy, để các trẻ đều có bánh thì số cách chia bánh $N$ thỏa yêu cầu là:

$N=\left | \overline{A_{1}}\cap\overline{A_{2}}\cap...\cap\overline{A_{k}} \right |=\left | \overline{A_{1}\cup A_{2}\cup ...\cup A_{k}} \right |=\left | S \right |-\left | A_{1}\cup A_{2}\cup ...\cup A_{k} \right |$

$\Rightarrow N=k^{n}-C_{k}^{1}\left ( k-1 \right )^{n}+C_{k}^{2}\left ( k-2 \right )^{n}+...+\left ( -1 \right )^{k}C_{k}^{k}\left ( k-k \right )^{n}=\sum_{j=0}^{k}\left ( -1 \right )^{j}C_{k}^{j}\left ( k-j \right )^{n}$     $(*)$

Thế $n=20$ và  $k=5$ vào $(*)$ ta có đáp án.

...hoặc dùng hàm sinh:

Hàm sinh cho số cách chia bánh mỗi trẻ là $\left ( x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+... \right )$ theo qui tắc xoắn ta có:

$G(x)=\left ( x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+... \right )^{5}=\left ( e^{x}-1 \right )^{5}$

Khai triển chuỗi :

$...+3474971465400\frac{x^{18}}{18!}+17710714165200\frac{x^{19}}{19!}+89904730860000\frac{x^{20}}{20!}+454951508208120\frac{x^{21}}{21!}+...$

Hệ số của $x^{20}$ trong khai triển là số cách chia bánh thỏa yc và bằng $89904730860000$ cách.

[hoaadc08]

Sử dụng công thức tính số Stirling loại 2.
CT tính số Stirling loại 2: Số cách bỏ n cái bánh khác nhau vào k hộp giống nhau sao cho không hộp nào rỗng là:
$S\left ( n,k \right )=\frac{1}{k!}\sum_{j=0}^{k}\left ( -1 \right )^{j}C_{k}^{j}\left ( k-j \right )^{n}$
Do đó số cách chia n=20 cái bánh khác nhau cho k=5 đứa trẻ sao cho mỗi trẻ có ít nhất 1 cái bánh là:
$S\left ( 20,5 \right )=\frac{5!}{5!}\sum_{j=0}^{5}\left ( -1 \right )^{j}C_{5}^{j}\left ( 5-j \right )^{20}=5^{20}-5.4^{20}+10.3^{20}-10.2^{20}+5=89904730860000\text{ cách}$
==========
hoặc dùng nguyên lý bù trừ rồi tính từ từ...
Gọi $S$ là tập các cách chia $n$ cái bánh khác nhau cho $k$ đứa trẻ mà không có ràng buộc nào (tức là có trẻ không được chia bánh)$\Rightarrow\left | S \right |=k^{n}$
Gọi $A_{i}$ là tập các cách chia bánh mà đứa trẻ $i$ không được chia bánh thì:
$\left | A_{i} \right |=C_{k}^{1}\left ( k-1 \right )^{n}$
$\left | A_{i}\cap A_{j} \right |=C_{k}^{2}\left ( k-2 \right )^{n}$
................................
Như vậy, để các trẻ đều có bánh thì số cách chia bánh $N$ thỏa yêu cầu là:
$N=\left | \overline{A_{1}}\cap\overline{A_{2}}\cap...\cap\overline{A_{k}} \right |=\left | \overline{A_{1}\cup A_{2}\cup ...\cup A_{k}} \right |=\left | S \right |-\left | A_{1}\cup A_{2}\cup ...\cup A_{k} \right |$
$\Rightarrow N=k^{n}-C_{k}^{1}\left ( k-1 \right )^{n}+C_{k}^{2}\left ( k-2 \right )^{n}+...+\left ( -1 \right )^{k}C_{k}^{k}\left ( k-k \right )^{n}=\sum_{j=0}^{k}\left ( -1 \right )^{j}C_{k}^{j}\left ( k-j \right )^{n}$     $(*)$
Thế $n=20$ và  $k=5$ vào $(*)$ ta có đáp án.

CÓ CÁCH GIẢI NÀO PHỔ THÔNG KHÔNG BẠN ?

[dottoantap]

CÓ CÁCH GIẢI NÀO PHỔ THÔNG KHÔNG BẠN ?

Rất tiếc là cho đến hiện giờ mình chưa nghĩ ra cách giải " phổ thông " hơn ! Theo mình, trong các cách đã trình bày thì cách giải dùng nguyên lý bù trừ có vẻ gần gũi hơn...