ปล่อย $b_{n}$ แสดงถึงจำนวนองค์ประกอบของ $n$ เป็น $k$ชิ้นส่วนโดยที่แต่ละส่วนเป็นหนึ่งหรือสอง ค้นหาซีรีส์ที่สร้างขึ้นสำหรับ $b_{n}$
ฉันติดอยู่กับปัญหา Combinatorics นี้ -
ปล่อย $n$ เป็นจำนวนเต็มบวกและปล่อยให้ $b_{n}$ แสดงถึงจำนวนองค์ประกอบของ $n$ เป็น $k$ชิ้นส่วนโดยที่แต่ละส่วนเป็นหนึ่งหรือสอง ตัวอย่างเช่น,$(1, 2, 1, 2, 1)$ และ $(2, 2, 1, 1, 1)$ เป็นสององค์ประกอบของ $n = 7$ เป็น $k = 5$ ชิ้นส่วน
ประการแรกเราต้องหาซีรี่ส์ที่สร้างขึ้นสำหรับ $b_{n}$
ประการที่สองพิสูจน์ว่า $b_{n} = {k \choose n-k}$ สำหรับ $k\le n \le2k$ และ $b_{n} = 0$ มิฉะนั้น.
คำตอบ
เพื่อคำนวณอนุกรมการสร้าง -
ให้ {1,2}$^{𝑘}$ เป็นชุดขององค์ประกอบที่มีส่วน k ซึ่งแต่ละส่วนเป็น 1 หรือ 2
จากนั้นใช้ "Product Lemma" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
พิสูจน์ -
องค์ประกอบของ n ที่มีส่วน k จะมี $i$ ส่วนเท่ากับ 2 สำหรับบางส่วน $0\le i\le k$. โปรดสังเกตว่าจำนวนชิ้นส่วนเท่ากับ 1 คือ$k-i$และ $n = (k-i) + 2i$, การให้ $i = n-k$. มี$k$ ตำแหน่งสำหรับ $n-k$ ส่วนที่เท่ากับ 2 ดังนั้นจึงมีองค์ประกอบทั้งหมด {k \ choose nk} ของ $n$ เป็น $k$ แต่ละส่วน $1$ หรือ $2$. โปรดทราบว่า$0\le i\le k$ หมายถึง $k\le n\le 2k$และจำนวนองค์ประกอบจะเป็นศูนย์
มีข้อพิสูจน์ที่ดีสำหรับคำถามที่สอง:
จำนวนองค์ประกอบของ $n$ เป็น $k$ แต่ละส่วนเท่ากับ $1$ หรือ $2$ เท่ากับจำนวนองค์ประกอบของ $n-k$ เป็น $k$ แต่ละส่วนเท่ากับ $0$ หรือ $1$. ต้องมีอย่างชัดเจน$n-k$ $1$ในองค์ประกอบดังกล่าวและมี $\binom k{n-k}$ วิธีการจัดเรียงเหล่านั้น $1$ในหมู่ $k$ ชิ้นส่วน
(1) มันคือ $(x+x^2)^k=x^k(1+x)^k$
(2) ค่าสัมประสิทธิ์ของ $x^n$ อยู่ใน $x^k(1+x)^k$ เหมือนกับ $x^{n-k}$ ใน $(1+x)^k$. ดังนั้นโดยทฤษฎีบททวินามจึงเป็น${k\choose n-k}$