บทความนี้จะเน้นที่หัวข้อพิเศษของคณิตศาสตร์ที่เรียกว่า combinatorics สูตร กฎ ตัวอย่างการแก้ปัญหา - ทั้งหมดนี้คุณจะพบได้ที่นี่โดยการอ่านบทความให้จบ
แล้วส่วนนี้คืออะไร? Combinatorics เกี่ยวข้องกับปัญหาการนับวัตถุใดๆ แต่ในกรณีนี้ สิ่งของนั้นไม่ใช่ลูกพลัม ลูกแพร์ หรือแอปเปิ้ล แต่เป็นอย่างอื่น Combinatorics ช่วยให้เราค้นหาความน่าจะเป็นของเหตุการณ์ ตัวอย่างเช่น เมื่อเล่นไพ่ ความน่าจะเป็นที่คู่ต่อสู้มีไพ่กล้าหาญเป็นเท่าใด หรือตัวอย่าง - ความน่าจะเป็นที่คุณจะได้สีขาวจากถุง 20 ลูกเป็นเท่าไหร่? สำหรับงานประเภทนี้ อย่างน้อยเราต้องรู้พื้นฐานของคณิตศาสตร์หมวดนี้
การกำหนดค่าผสม
เมื่อพิจารณาถึงประเด็นของแนวคิดพื้นฐานและสูตรของ combinatorics แล้ว เราไม่สามารถสนใจการกำหนดค่าแบบผสมผสานได้ พวกเขาใช้ไม่เพียง แต่สำหรับการกำหนด แต่ยังสำหรับการแก้ปัญหาต่างๆ ตัวอย่างของโมเดลดังกล่าว ได้แก่
- ตำแหน่ง;
- การเปลี่ยนแปลง;
- รวมกัน;
- จำนวนองค์ประกอบ;
- แยกเลข
เราจะพูดถึงสามตัวแรกในรายละเอียดเพิ่มเติมในภายหลัง แต่เราจะให้ความสนใจกับการจัดองค์ประกอบและการแยกส่วนในหัวข้อนี้ เมื่อพวกเขาพูดถึงองค์ประกอบของจำนวนหนึ่ง (เช่น a) พวกเขาหมายถึงการแสดงตัวเลข a เป็นผลรวมลำดับของจำนวนบวกบางตัว และการแบ่งเป็นผลรวมที่ไม่เรียงลำดับ
ส่วน
ก่อนที่เราจะพูดถึงสูตรของ combinatorics โดยตรงและการพิจารณาปัญหา คุณควรให้ความสนใจกับความจริงที่ว่า combinatorics เหมือนกับส่วนอื่นๆ ของคณิตศาสตร์ มีส่วนย่อยของตัวเอง ซึ่งรวมถึง:
- แจกแจง;
- โครงสร้าง
- สุดขีด;
- ทฤษฎีแรมซีย์;
- ความน่าจะเป็น;
- ทอพอโลยี;
- อนันต์
ในกรณีแรก เรากำลังพูดถึง combinatorics แบบแจงนับ ปัญหาจะพิจารณาการแจงนับหรือการนับการกำหนดค่าต่างๆ ที่เกิดขึ้นจากองค์ประกอบของเซต ตามกฎแล้วจะมีการกำหนดข้อจำกัดบางประการในชุดเหล่านี้ (ความสามารถในการแยกแยะ การแยกไม่ออก ความเป็นไปได้ของการทำซ้ำ และอื่นๆ) และจำนวนของการกำหนดค่าเหล่านี้คำนวณโดยใช้กฎการบวกหรือการคูณ ซึ่งเราจะพูดถึงในภายหลัง โครงสร้างเชิงผสมผสานรวมถึงทฤษฎีของกราฟและเมทรอยด์ ตัวอย่างของปัญหาเชิงซ้อนสุดโต่งคือมิติที่ใหญ่ที่สุดของกราฟที่ตรงตามคุณสมบัติต่อไปนี้คืออะไร… ในย่อหน้าที่สี่ เรากล่าวถึงทฤษฎีแรมซีย์ ซึ่งศึกษาการมีอยู่ของโครงสร้างปกติในการกำหนดค่าแบบสุ่ม ความน่าจะเป็นcombinatorics สามารถตอบคำถามได้ - ความน่าจะเป็นที่ชุดที่กำหนดมีคุณสมบัติบางอย่างเป็นเท่าใด อย่างที่คุณอาจเดาได้ว่าโทโพโลยี combinatorics ใช้วิธีในโทโพโลยี และสุดท้าย จุดที่เจ็ด - infinitary combinatorics ศึกษาการประยุกต์ใช้วิธี combinatorics กับเซตอนันต์
กฎการเพิ่ม
ในบรรดาสูตรของ combinatorics เราสามารถหาสูตรง่ายๆ ที่เราคุ้นเคยกันมานาน ตัวอย่างคือกฎผลรวม สมมติว่าเราได้รับการกระทำสองอย่าง (C และ E) หากการกระทำทั้งสองไม่เกิดร่วมกัน การกระทำ C สามารถทำได้หลายวิธี (เช่น a) และการกระทำ E สามารถทำได้ในรูปแบบ b การกระทำใด ๆ (C หรือ E) สามารถทำได้ด้วยวิธี a + b.
ในทางทฤษฎี ค่อนข้างเข้าใจยาก เราจะพยายามถ่ายทอดประเด็นทั้งหมดด้วยตัวอย่างง่ายๆ ลองหาจำนวนนักเรียนเฉลี่ยในหนึ่งชั้นเรียน - สมมุติว่าเป็นยี่สิบห้า ในหมู่พวกเขามีเด็กผู้หญิงสิบห้าคนและเด็กชายสิบคน ผู้เข้าร่วมประชุมหนึ่งคนได้รับมอบหมายให้ชั้นเรียนทุกวัน วันนี้มีกี่วิธีในการมอบหมายผู้ดูแลชั้นเรียน การแก้ปัญหานั้นค่อนข้างง่าย เราจะหันไปใช้กฎการบวก เนื้อหาของงานไม่ได้ระบุว่าสามารถปฏิบัติหน้าที่ได้เฉพาะเด็กชายหรือเด็กหญิงเท่านั้น ดังนั้น อาจเป็นเด็กผู้หญิงคนใดคนหนึ่งในสิบห้าคนหรือเด็กผู้ชายสิบคนก็ได้ เมื่อใช้กฎผลรวม เราได้ตัวอย่างง่ายๆ ที่นักเรียนชั้นประถมศึกษาสามารถรับมือได้: 15 + 10 เมื่อคำนวณแล้ว เราได้คำตอบ: ยี่สิบห้า นั่นคือมีเพียงยี่สิบห้าวิธีมอบหมายชั้นหน้าที่สำหรับวันนี้
กฎการคูณ
กฎของการคูณยังเป็นของสูตรพื้นฐานของการรวมกัน เริ่มจากทฤษฎีกันก่อน สมมติว่าเราต้องดำเนินการหลายอย่าง (a): การกระทำแรกดำเนินการใน 1 วิธี ครั้งที่สอง - ใน 2 วิธี ครั้งที่สาม - ใน 3 วิธี และต่อไปเรื่อยๆ จนกว่าการกระทำสุดท้ายจะดำเนินการด้วยวิธี sa จากนั้นการกระทำทั้งหมดเหล่านี้ (ซึ่งเรามีทั้งหมด) สามารถทำได้ใน N วิธี วิธีการคำนวณ N ที่ไม่รู้จัก? สูตรจะช่วยเราในเรื่องนี้: N \u003d c1c2c3…ca.
อีกครั้ง ในทางทฤษฎีไม่มีความชัดเจน เรามาดูตัวอย่างง่ายๆ ของการใช้กฎการคูณกัน เรามาเรียนชั้นเรียนเดียวกันกับกลุ่มละ 25 คน ซึ่งเด็กผู้หญิงสิบห้าคนและเด็กชายสิบคนกำลังเรียนอยู่ เฉพาะครั้งนี้เท่านั้นที่เราต้องเลือกคนดูแลสองคน พวกเขาสามารถเป็นได้ทั้งเด็กผู้ชายหรือเด็กผู้หญิงหรือเด็กผู้ชายกับผู้หญิง เราหันไปหาวิธีแก้ปัญหาเบื้องต้น เราเลือกผู้ดูแลคนแรก ตามที่เราตัดสินใจในย่อหน้าสุดท้าย เรามีตัวเลือกที่เป็นไปได้ยี่สิบห้าตัวเลือก คนที่สองที่ปฏิบัติหน้าที่สามารถเป็นคนใดก็ได้ที่เหลืออยู่ เรามีนักเรียนยี่สิบห้าคน เราเลือกหนึ่งคน ซึ่งหมายความว่าคนใดในยี่สิบสี่คนที่เหลือสามารถเป็นรองได้ สุดท้ายเราใช้กฎการคูณและพบว่าผู้เข้าร่วมสองคนสามารถเลือกได้หกร้อยวิธี เราได้ตัวเลขนี้จากการคูณยี่สิบห้ากับยี่สิบสี่
สลับ
ตอนนี้เราจะพิจารณาสูตรเชิงผสมอีกหนึ่งสูตร ในส่วนของบทความนี้ เรามาพูดถึงการเรียงสับเปลี่ยนกัน พิจารณาปัญหาทันทีด้วยตัวอย่าง เอาลูกบิลเลียดกัน เรามีลูกที่ n เราจำเป็นต้องคำนวณ: มีกี่ตัวเลือกที่จะจัดเรียงพวกมันในแถว นั่นคือเพื่อสร้างชุดคำสั่ง
เริ่มเลย ถ้าเราไม่มีบอล เราก็ไม่มีตัวเลือกตำแหน่ง และถ้าเรามีลูกบอลหนึ่งลูก การจัดเรียงก็เหมือนกัน (ในทางคณิตศาสตร์ สามารถเขียนได้ดังนี้: Р1=1) สามารถจัดเรียงลูกบอลสองลูกได้สองวิธี: 1, 2 และ 2, 1 ดังนั้น Р2=2 สามารถจัดเรียงลูกบอลสามลูกได้หกวิธี (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. และถ้าไม่มีสามลูกดังกล่าว แต่มีสิบหรือสิบห้า? ในการแสดงรายการตัวเลือกที่เป็นไปได้ทั้งหมดนั้นยาวมาก combinatorics ก็เข้ามาช่วยเรา สูตรการเรียงสับเปลี่ยนจะช่วยให้เราพบคำตอบสำหรับคำถามของเรา Pn=nP(n-1). ถ้าเราพยายามทำให้สูตรง่ายขึ้น เราจะได้ Pn=n (n - 1) … 21 และนี่คือผลคูณของจำนวนธรรมชาติตัวแรก ตัวเลขดังกล่าวเรียกว่าแฟกทอเรียล และเขียนแทนด้วย n!
ลองพิจารณาปัญหากัน ผู้นำทุกเช้าสร้างความแตกแยกเป็นแถว (ยี่สิบคน) มีเพื่อนที่ดีที่สุดสามคนในกลุ่ม - Kostya, Sasha และ Lesha ความน่าจะเป็นที่จะอยู่ติดกันเป็นเท่าใด ในการหาคำตอบของคำถาม คุณต้องหารความน่าจะเป็นของผลลัพธ์ที่ "ดี" ด้วยจำนวนผลลัพธ์ทั้งหมด จำนวนการเรียงสับเปลี่ยนทั้งหมดคือ 20!=2.5 quintillion. จะนับจำนวนผลลัพธ์ที่ "ดี" ได้อย่างไร? สมมติว่า Kostya, Sasha และ Lesha เป็นซุปเปอร์แมนคนหนึ่ง แล้วเราเรามีเพียงสิบแปดวิชา จำนวนการเรียงสับเปลี่ยนในกรณีนี้คือ 18=6.5 พันล้านล้าน ด้วยทั้งหมดนี้ Kostya, Sasha และ Lesha สามารถเคลื่อนที่กันเองในสามแยกไม่ได้และนี่คืออีก 3 รายการ!=6 ตัวเลือก ดังนั้นเราจึงมีกลุ่มดาว "ดี" ทั้งหมด 18 กลุ่ม!3! เราแค่ต้องหาความน่าจะเป็นที่ต้องการ: (18!3!) / 20! ซึ่งมีค่าประมาณ 0.016 หากแปลงเป็นเปอร์เซ็นต์จะกลายเป็นเพียง 1.6%
ที่พัก
ตอนนี้เราจะพิจารณาอีกสูตรผสมที่สำคัญและจำเป็นมาก ที่พักเป็นฉบับต่อไปของเรา ซึ่งเราขอแนะนำให้คุณพิจารณาในส่วนนี้ของบทความนี้ เราจะซับซ้อนมากขึ้น สมมติว่าเราต้องการพิจารณาการเรียงสับเปลี่ยนที่เป็นไปได้ ไม่ใช่แค่จากทั้งเซต (n) แต่จากชุดที่เล็กกว่า (m) นั่นคือ เราพิจารณาการเรียงสับเปลี่ยนของ n รายการด้วย m
สูตรพื้นฐานของ combinatorics ไม่ควรที่จะท่องจำแต่ต้องเข้าใจ แม้ว่าข้อเท็จจริงจะซับซ้อนกว่าเนื่องจากเราไม่มีพารามิเตอร์เดียว แต่มีสองตัว สมมติว่า m \u003d 1 จากนั้น A \u003d 1 m \u003d 2 จากนั้น A \u003d n(n - 1) หากเราลดความซับซ้อนของสูตรเพิ่มเติมและเปลี่ยนไปใช้สัญกรณ์โดยใช้แฟกทอเรียล เราก็จะได้สูตรที่ค่อนข้างกระชับ: A \u003d n! / (n - m)!
การรวมกัน
เราได้พิจารณาสูตรพื้นฐานเกือบทั้งหมดของ combinatorics พร้อมตัวอย่างแล้ว ตอนนี้ มาต่อกันที่ขั้นตอนสุดท้ายของการพิจารณาหลักสูตรพื้นฐานของ combinatorics - ทำความรู้จักกับการรวมกัน ตอนนี้เราจะเลือก m รายการจาก n ที่เรามี ในขณะที่เราจะเลือกทั้งหมดในทุกวิถีทางที่เป็นไปได้ แล้วมันต่างจากที่พักยังไง? พวกเราจะไม่พิจารณาสั่งซื้อ ชุดที่ไม่เรียงลำดับนี้จะเป็นชุดค่าผสม
แนะนำสัญกรณ์ทันที: C. เรานำตำแหน่งของ m ball จาก n. เราเลิกสนใจการสั่งซื้อและรับชุดค่าผสมที่ทำซ้ำ เพื่อให้ได้จำนวนชุดค่าผสม เราต้องหารจำนวนตำแหน่งด้วย m! (ม. แฟกทอเรียล). นั่นคือ C \u003d A / m! จึงมีสองสามวิธีในการเลือกจาก n ลูก ประมาณเท่ากับจำนวนที่จะเลือกเกือบทุกอย่าง มีนิพจน์เชิงตรรกะสำหรับสิ่งนี้: การเลือกเพียงเล็กน้อยก็เหมือนกับการทิ้งเกือบทุกอย่าง สิ่งสำคัญคือต้องพูดถึง ณ จุดนี้ด้วยว่าเมื่อพยายามเลือกไอเท็มครึ่งหนึ่งถึงจำนวนชุดค่าผสมสูงสุดได้
เลือกสูตรแก้ปัญหาอย่างไร
เราได้ตรวจสอบรายละเอียดสูตรพื้นฐานของ combinatorics: การจัดวาง การเรียงสับเปลี่ยน และการรวมกัน ตอนนี้งานของเราคืออำนวยความสะดวกในการเลือกสูตรที่จำเป็นสำหรับการแก้ปัญหาในรูปแบบผสมผสาน คุณสามารถใช้รูปแบบที่ค่อนข้างง่ายต่อไปนี้:
- ถามตัวเองว่า: ลำดับขององค์ประกอบถูกนำมาพิจารณาในข้อความของปัญหาหรือไม่
- ถ้าไม่ใช่ ให้ใช้สูตรผสม (C=n! / (m!(n - m)!))
- ถ้าคำตอบคือไม่ คุณต้องตอบคำถามเพิ่มอีกข้อ: องค์ประกอบทั้งหมดรวมอยู่ในชุดค่าผสมหรือไม่
- ถ้าคำตอบคือใช่ ให้ใช้สูตรการเรียงสับเปลี่ยน (P=n!).
- ถ้าคำตอบคือไม่ใช่ ให้ใช้สูตรการจัดสรร (A=n! / (n - m)!).
ตัวอย่าง
เราได้พิจารณาองค์ประกอบของ combinatorics สูตรและปัญหาอื่นๆ งั้นไปต่อกันที่พิจารณาปัญหาที่แท้จริง ลองนึกภาพว่าคุณมีกีวี ส้ม และกล้วยอยู่ข้างหน้าคุณ
คำถามที่หนึ่ง: สามารถจัดเรียงใหม่ได้กี่วิธี? ในการทำเช่นนี้ เราใช้สูตรการเรียงสับเปลี่ยน: P=3!=6 วิธี
คำถามที่สอง: ผลไม้หนึ่งผลสามารถเลือกได้กี่วิธี? เห็นได้ชัดว่าเรามีเพียงสามตัวเลือก - เลือกกีวี ส้มหรือกล้วย แต่เราใช้สูตรผสม: C \u003d 3! / (2!1!)=3.
คำถามที่สาม: เลือกผลไม้ได้กี่วิธี? ตัวเลือกที่เรามีอะไรบ้าง? กีวีและส้ม กีวีและกล้วย ส้มและกล้วย นั่นคือสามตัวเลือก แต่ง่ายต่อการตรวจสอบโดยใช้สูตรผสม: C \u003d 3! / (1!2!)=3
คำถามที่สี่: เลือกผลไม้สามอย่างได้กี่วิธี? อย่างที่คุณเห็น มีทางเดียวเท่านั้นที่จะเลือกผลไม้สามชนิด: กินกีวี ส้ม และกล้วย ค=3! / (0!3!)=1.
คำถามที่ห้า: คุณสามารถเลือกผลไม้อย่างน้อยหนึ่งผลได้กี่วิธี? เงื่อนไขนี้บอกเป็นนัยว่าเราสามารถรับผลไม้ได้หนึ่ง สอง หรือทั้งสามผล ดังนั้นเราจึงเพิ่ม C1 + C2 + C3=3 + 3 + 1=7 นั่นคือ เรามีเจ็ดวิธีในการนำผลไม้อย่างน้อยหนึ่งชิ้นออกจากโต๊ะ