การนับและการหารลงตัว

[BLACK-Dragon]

1.จงหาจำนวนของจำนวน 9 หลักที่สร้างจาก $\left\{\,0,1,2,...,8,9\right\} $ โดยแต่ละหลักไม่ซ้ำกัน และจำนวนนั้นหารด้วย $11111$ ลงตัว

[lnพwsะบุ๑sสุ๑xล่o]

ให้ 9 หลักเป็น x8x7x6x5x4x3x2x1x0 , $x_i<10$

$x8(10^8)+x7(10^7)+x6(10^6)+x5(10^5)+x4(10^4)+x3(10^3)+x2(10^2)+x1(10)+x0$
$\equiv x4(10^4)+(x8+x3)10^3+(x7+x2)10^2+(x6+x1)10+(x5+x0)$

หารด้วย 11111 ลงตัวแสดงว่า
x4=x8+x3=x7+x2=x6+x1=x5+x0

แต่ $x_i$ ไม่ซ้ำ แสดงว่าไม่มี $ x_i $ ที่เป็น 0

ใช้ stars&bars แก้
5 เขียนเป็นผลบวกจำนวนต่างกัน(ที่ไม่ใช่ 0)ได้ 4
ในทำนองเดียวกัน
6 ได้ 4
7 ได้ 6
8 ได้ 6
9 ได้ 8
(พิจารณาถึง 9 เนื่องจาก $x_4<=9$)
รวมได้ 28 จำนวน

[gnap]

ข้อความเดิมเขียนโดยคุณ lnพwsะบุ๑sสุ๑xล่o

ให้ 9 หลักเป็น x8x7x6x5x4x3x2x1x0 , $x_i<10$

$x8(10^8)+x7(10^7)+x6(10^6)+x5(10^5)+x4(10^4)+x3(10^3)+x2(10^2)+x1(10)+x0$
$\equiv x4(10^4)+(x8+x3)10^3+(x7+x2)10^2+(x6+x1)10+(x5+x0)$

หารด้วย 11111 ลงตัวแสดงว่า
x4=x8+x3=x7+x2=x6+x1=x5+x0

แต่ $x_i$ ไม่ซ้ำ แสดงว่าไม่มี $ x_i $ ที่เป็น 0

ใช้ stars&bars แก้
5 เขียนเป็นผลบวกจำนวนต่างกัน(ที่ไม่ใช่ 0)ได้ 4
ในทำนองเดียวกัน
6 ได้ 4
7 ได้ 6
8 ได้ 6
9 ได้ 8
(พิจารณาถึง 9 เนื่องจาก $x_4<=9$)
รวมได้ 28 จำนวน

stars&bars คืออะไรหรอครับ?

[lnพwsะบุ๑sสุ๑xล่o]

วิธีช่วยแก้ปัญหาทางคอมบินาทอริก วิธีหนึ่งครับ ลองหาศึกษาจากหนังสือหรือเว็บไซด์ดูครับ

[gnap]

อ่อครับๆๆๆ

[Sirius]

http://en.wikipedia.org/wiki/Stars_a...combinatorics)

บทความ wiki เกี่ยวกับ star&bar ครับ