โจทย์เกี่ยวกับ Bag

[gnopy]

Theorem:
The number of unordered lists of length r taken
from a set of size n, with repetitions allowed, is
C(r + n ? 1, r)


1.Let A and B be finite sets of size m and n,
respectively. How many different functions
from A to B are there?

2.How many positive integer solutions are
there to x + y + z = 21?

3.How many nonnegative integer solutions
are there to the equation w + x + y + z = 10
if w ≥ 3 and x ≥ 1?

4. How many ways can we roll a sum of 17 on
six distinguishable dice?

5.How many bit strings of length n with no
two consecutive 0's are there?

6.How many ways to choose an n-digit PIN
containing an even number of 0 digits?


ช่วยอธิบายวิธีคิดหน่อยนะครับ

[Onasdi]

เข้าใจถึงที่มาของทฤษฎีนี้รึยังครับ โจทย์ดูค่อนข้างจะพลิกแพลง ไม่ได้ใช้ทฤษฎีตรงๆ
1. คิดว่ามันไม่ต้องใช้ทฤษฎีนี้นะครับ
2. จำนวนคำตอบที่ต้องการ = จำนวนคำตอบของ a + b + c = 18 โดยที่ $a,b,c\ge 0$ ซึ่ง = $\dbinom{3+18-1}{3}$
[มอง a=x-1,...]
3. คล้ายข้อ 2 ให้ตัวแปรใหม่ a=w-3,b=x-1,c=y,d=z เพื่อที่จะได้ $a,b,c,d\ge 0$
4. ต้องการจำนวนคำตอบของ $x_1+\dots +x_6=17$ โดยที่ $1\le x_k\le 6$
ขั้นแรก ให้ $y_k=x_k-1$ ได้ $y_1+\dots +y_6=11$ โดยที่ $0\le y_k\le 5$
จากนั้น เราก็หา จำนวนคำตอบของ $y_1+\dots +y_6=11$ โดยที่ $0\le y_k$ ทุก $k$
ลบออกด้วย จำนวนคำตอบของ $y_1+\dots +y_6=11$ โดยที่มี $k$ ซึ่ง $6\le y_k$
[ก้อนหลังหาโดย inclusion-exclusion principle ลองดูครับ]

[gnopy]

ผมยังไม่เข้าใจ concept ของbag เลยครับ
คือถ้าเงื่อนไข มันไม่ใช่ 0 ให้เปลี่ยนเป็น 0 หรอครับ

ขอแสดงวิธีทำอย่างละเอียดในข้อ 3 หน่อยนะครับ

ขอบคุณครับ

[Onasdi]

ทฤษฎีนี้เกี่ยวกับการเลือกของมา r ชิ้น จากของ n ชนิดซึ่งแต่ละชนิดมีจำนวนไม่จำกัด
เช่น ต้องการซื้ออาหาร 4 กล่อง โดยมีอาหารให้เลือก 2 ชนิดคือข้าวต้มกับข้าวผัด
ซึ่งทำได้ทั้งหมด 5 วิธีคือ 4-0 3-1 2-2 1-3 0-4
ซึ่งเทียบเท่ากับคำตอบของ $x_1+x_2=5$ โดยที่ $x_i\ge 0$

ทฤษฎีนี้บอกว่า จำนวนการเลือกของมา r ชิ้น จากของ n ชนิดซึ่งแต่ละชนิดมีจำนวนไม่จำกัด = $\dbinom{r+n-1}{r}$
นั่นคือ จำนวนคำตอบของ $x_1+x_2+\dots+x_n=r$ โดยที่ $x_i\ge 0$ = $\dbinom{r+n-1}{r}$