|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
โจทย์เกี่ยวกับ Bag
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? ช่วยอธิบายวิธีคิดหน่อยนะครับ |
#2
|
||||
|
||||
เข้าใจถึงที่มาของทฤษฎีนี้รึยังครับ โจทย์ดูค่อนข้างจะพลิกแพลง ไม่ได้ใช้ทฤษฎีตรงๆ
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 ลองดูครับ] |
#3
|
||||
|
||||
ผมยังไม่เข้าใจ concept ของbag เลยครับ
คือถ้าเงื่อนไข มันไม่ใช่ 0 ให้เปลี่ยนเป็น 0 หรอครับ ขอแสดงวิธีทำอย่างละเอียดในข้อ 3 หน่อยนะครับ ขอบคุณครับ |
#4
|
||||
|
||||
ทฤษฎีนี้เกี่ยวกับการเลือกของมา 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}$ |
|
|