Combinatorics and Linear Programming
 

ไปเจอโจทย์คอมบิข้อนึงอ่ะครับ แบบงงๆ

แนวของโจทย์ประมาณว่า ให้จำนวนเต็มบวก n มาหนึ่งตัว แล้วจงเขียนให้รูปของผลบวกของเลขจำนวนเต็มบวกสามจำนวน แล้วเอาเลขสามจำนวนนั้นมาเรียงกัน

สมมุติ n เป็น 9

ิถ้าใช้ star(s) and bar(s) ก้อจะได้ C 8,2 ( รึเปล่า ?? :D )
แต่ถ้าเอามาเขียนเป็นสมการจะได้ประมาณ

a+b+c = 9
a , b , c เป็นจำนวนเต็มบวก

จากเรื่องกำหนดการเชิงเส้น ซึ่งถ้านำมา plot เป็นกราฟ ( สามมิติ รึเปล่า ?? ) แล้วนำจำนวนจุดที่เป็นจำนวนเต็มซึ่งสอดคล้องตามเงื่อนไข ที่ถูกรูปคร่อม จะได้เท่ากับ C 8,2 ...

จึงมีำคำถามจะเรียนถามว่า
(1) จริงๆแล้วคอมบินาทอริกเป็นกรรมวิธีหาคำตอบจำนวนเต็มที่สอดคล้องกับสมการใช่หรือไม่

(2) ถ้าไม่ใช้คอมบินาทอริกช่วย จะหาคำตอบของสมการข้างต้น ที่เป็นจำนวนเต็ม ได้อย่างไร

(3) จะเขียนคำถามเกี่ยวกับการเีรียงสับเปลี่ยนทั่วๆไปให้อยู่ใน รูปของสมการได้ิอย่างไร เช่น มีคน 7 คน ให้นำเรียงแถวกันได้กี่แบบเป็นต้น

ขอบคุณล่วงหน้าสำหรับคำตอบครับ ^^

ขอแสดงความเห็นนะครับ (ไม่ใช่คำตอบ)
(1) คอมบินาทอริกไม่ใช่กรรมวิธีหาคำตอบจำนวนเต็มที่สอดคล้องกับสมการ อาจจะสามารถหาได้แค่ว่ามีกี่คำตอบ ส่วนคำตอบคืออะไรนั้นคงยากครับ
(2) ดังนั้นเรานักจะใช้เรื่องของทฤษฎีจำนวน เช่น Diophatine หรือพวก Congruence มาช่วยครับ
(3) ไม่มีวิธีแน่ชัดเท่าที่ทราบ อย่างไรก็ตามบางปัญหาเราสามารถเขียนออกมาได้แต่ก็เป็นการแปลงปัญหาเรื่องที่เป็นโจทย์ออกมาในรูปแบบสัญลักษณ์เท่านั้น ไม่ได้ช่วยมากนัก (ความเห็นผมนะครับ) เช่นจะแบ่งคน 9 คนออกเป็น 3 กลุ่ม ก็จะได้สมการดังข้างต้น

Star and Bars 8C2 ถูกแล้วครับ. ส่วนที่ถาม 1 ถึง 3 เหมือนกับคุณ Sos_Math ครับ.

ไหนๆ ก็พูดถึง Linear Programming แล้ว ผมขอคำแนะนำนิดนึงครับ
คือ ผมไปเข้าค่ายคอมโอฯ มา แล้ว อาจารย์ที่ค่ายก็สอนเรื่อง Linear Programming คือแก้สมการหาค่าที่เหมาะที่สุดธรรมดาๆแหละครับ
แต่ตัวแปรในสมการมีได้เป็นจำนวนมาก และเยอะจนไม่สามารถคิดในกระดาษได้ ต้องเขียนเป็นโปรแกรมช่วย
การแก้ปัญหาโดยเขียนโปรแกรมที่อาจารย์เค้าสอน ต้องใช้ Matrix ช่วย ถ้าเป็นคอมพิวเตอร์ก็จะเป็น Array 2 มิติ ซึ่งผมเรียนแล้วไม่ค่อยรู้เรื่อง
ผมควรจะหาข้อมูลเพิ่มเติมเรื่องนี้ได้จากที่ไหนครับ ถ้าเป็นไปได้ อยากให้มีตัวอย่างการเขียนโปรแกรมด้วยครับ ถ้าเป็นภาษา C ก็ดี
ป.ล. ถ้ามีเน้อหาเกี่ยวกับ Non-Linear Programming ก็ขอด้วยครับ เพราะอาจารย์เค้าบอกว่าจะสอนในค่าย 2

ถ้าเป็น linear programming ก็ต้องนึกถึงการแก้ระบบสมการหาจุดตัด แต่ในที่นี้ที่บอกว่า มีตัวแปรเยอะมากต้องใช้ Matrix ช่วยแก้ระบบสมการ
1.ถ้าสนใจวิธีการหาคำตอบโดยใช้ Matrix ศึกษาได้จาก หนังสือวิชา Linear Algebra ทั่วไป
2.ถ้าสนใจการเขียนโปรแกรม ก็แนะนำหนังสือ การเขียนโปรแกรมทั่วๆไปครับ
ส่วน Non-Linear Programming น่าจะมีในหนังสือ Calculus for business เพราะมักใช้ในปัญหาเกี่ยวกับเศรฐศาสตร์ มากกว่า ลองหาๆดูครับ

ขอบคุณครับ :) จะพยายามศึกษาดู แต่สงสัยจะยาก ผมยังไม่ได้เรียน Calculus เลย :( (อยู่ม.3)