คณิตศาสตร์ไม่ต่อเนื่อง - ทฤษฎีการนับ

ในชีวิตประจำวันหลาย ๆ ครั้งเราต้องค้นหาจำนวนผลลัพธ์ที่เป็นไปได้ทั้งหมดสำหรับเหตุการณ์ต่างๆ ตัวอย่างเช่นสามารถเลือกคณะผู้พิพากษาที่ประกอบด้วยชาย 6 คนและหญิง 4 คนจากชาย 50 คนและหญิง 38 คนได้กี่วิธี สามารถสร้างตัวเลข PAN ที่เป็นตัวอักษร 10 ตัวได้กี่ตัวโดยที่ตัวอักษรห้าตัวแรกเป็นตัวพิมพ์ใหญ่สี่ตัวถัดไปเป็นตัวเลขและตัวสุดท้ายเป็นตัวพิมพ์ใหญ่อีกครั้ง สำหรับการแก้ปัญหาเหล่านี้จะใช้ทฤษฎีการนับทางคณิตศาสตร์Counting ส่วนใหญ่ครอบคลุมกฎการนับพื้นฐานกฎการเรียงสับเปลี่ยนและกฎการรวมกัน

กฎของผลรวมและผลิตภัณฑ์

Rule of Sum และ Rule of Product ใช้เพื่อแยกปัญหาการนับที่ยากให้กลายเป็นปัญหาง่ายๆ

The Rule of Sum- หากลำดับของงาน $ T_1, T_2, \ dots, T_m $ สามารถทำได้ใน $ w_1, w_2, \ dots w_m $ ตามลำดับ (เงื่อนไขคือไม่สามารถดำเนินการพร้อมกันได้) จำนวนวิธีในการ ทำงานอย่างใดอย่างหนึ่งคือ $ w_1 + w_2 + \ dots + w_m $ ถ้าเราพิจารณาสองงาน A และ B ซึ่งไม่ปะติดปะต่อกัน (เช่น $ A \ cap B = \ emptyset $) ตามหลักคณิตศาสตร์ $ | A \ cup B | = | A | + | B | $
The Rule of Product- ถ้าลำดับของงาน $ T_1, T_2, \ dots, T_m $ สามารถทำได้ใน $ w_1, w_2, \ dots w_m $ ตามลำดับและทุกงานมาถึงหลังจากเกิดภารกิจก่อนหน้าแล้วจะมี $ w_1 \ times w_2 \ times \ dots \ times w_m $ วิธีในการดำเนินการ ในทางคณิตศาสตร์ถ้างาน B มาถึงหลังจากงาน A ดังนั้น $ | A \ times B | = | A | \ times | B | $

ตัวอย่าง

Question- เด็กชายคนหนึ่งอาศัยอยู่ที่ X และต้องการไปโรงเรียนที่ Z จากบ้านของเขา X เขาต้องไปถึง Y ก่อนจากนั้น Y ถึง Z เขาอาจไป X ถึง Y โดยรถประจำทาง 3 สายหรือ 2 เส้นทางรถไฟ จากนั้นเขาสามารถเลือกรถบัสได้ 4 เส้นทางหรือรถไฟ 5 เส้นทางเพื่อไปยัง Z มีวิธีการเดินทางจาก X ไป Z กี่วิธี?

Solution- จาก X ถึง Y เขาสามารถไปได้ $ 3 + 2 = 5 $ วิธี (Rule of Sum) หลังจากนั้นเขาสามารถไป Y ถึง Z ด้วยวิธี $ 4 + 5 = 9 $ (Rule of Sum) ดังนั้นจาก X ถึง Z เขาสามารถไปได้ใน $ 5 \ คูณ 9 = 45 $ วิธี (Rule of Product)

เรียงสับเปลี่ยน

ก permutationเป็นการจัดเรียงองค์ประกอบบางอย่างที่ลำดับมีความสำคัญ กล่าวอีกนัยหนึ่งคือการเรียงสับเปลี่ยนเป็นการรวมองค์ประกอบตามลำดับ

ตัวอย่าง

จากชุด S = {x, y, z} โดยรับครั้งละสองชุดการเรียงสับเปลี่ยนทั้งหมดคือ -

$ xy, yx, xz, zx, yz, zy $
เราต้องสร้างการเปลี่ยนแปลงของตัวเลขสามหลักจากชุดตัวเลข $ S = \ lbrace 1, 2, 3 \ rbrace $ ตัวเลขสามหลักที่แตกต่างกันจะเกิดขึ้นเมื่อเราจัดเรียงตัวเลข การเรียงสับเปลี่ยนจะเป็น = 123, 132, 213, 231, 312, 321

จำนวนการเรียงลำดับ

จำนวนการเรียงสับเปลี่ยนของ 'n' สิ่งต่างๆที่ใช้ 'r' ในแต่ละครั้งแสดงด้วย $ n_ {P_ {r}} $

$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$

โดยที่ $ n! = 1.2.3 \ dots (n - 1) .n $

Proof - ให้มีองค์ประกอบที่แตกต่างกัน 'n'

มีวิธีการเติม n อันดับแรก หลังจากเติมองค์ประกอบที่หนึ่ง (n-1) แล้วจะเหลือจำนวนองค์ประกอบ ดังนั้นจึงมีวิธี (n-1) ในการเติมตำแหน่งที่สอง หลังจากเติมตำแหน่งที่หนึ่งและที่สองแล้วจะเหลือ (n-2) จำนวนองค์ประกอบ ดังนั้นจึงมี (n-2) วิธีในการเติมตำแหน่งที่สาม ตอนนี้เราสามารถสรุปหลายวิธีในการเติมตำแหน่ง r-th เป็น [n - (r – 1)] = n – r + 1

ดังนั้นจำนวนทั้งหมด วิธีการเติมจากที่หนึ่งถึง r-th-place -

$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $

$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ dots 3.2.1] / [(nr) (nr-1) \ dots 3.2.1] $

ดังนั้น

$ n_ {P_ {r}} = n! / (nr)! $

สูตรที่สำคัญบางประการของการเปลี่ยนแปลง

หากมีnองค์ประกอบที่ $ a_1 $ เหมือนกันบางชนิด, $ $ A_2 เหมือนกันของชนิดอื่น $ a_3 $ เหมือนกันกับประเภทที่สามและอื่น ๆ และ $ a_r $ เป็นของ $ r ^ {th} $ ชนิดโดยที่ $ (a_1 + a_2 + ... a_r) = n $

จากนั้นจำนวนการเรียงสับเปลี่ยนของวัตถุ n เหล่านี้คือ = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.
จำนวนการเรียงสับเปลี่ยนขององค์ประกอบที่แตกต่างกัน n การรับ n องค์ประกอบในแต่ละครั้ง = $ n_ {P_n} = n! $
จำนวนการเรียงสับเปลี่ยนขององค์ประกอบที่ไม่เหมือนกันที่รับองค์ประกอบ r ในแต่ละครั้งเมื่อ x สิ่งใดสิ่งหนึ่งครอบครองตำแหน่งที่แน่นอนเสมอ = $ n-x_ {p_ {rx}} $
จำนวนการเรียงสับเปลี่ยนของ n องค์ประกอบที่แตกต่างกันเมื่อ r สิ่งที่ระบุมารวมกันเสมอคือ - $ r! (n − r + 1)! $
จำนวนการเรียงสับเปลี่ยนของ n องค์ประกอบที่แตกต่างกันเมื่อ r สิ่งที่ระบุไม่มารวมกันคือ - $ n! - [r! (n − r + 1)!] $
จำนวนการเรียงสับเปลี่ยนแบบวงกลมของ n องค์ประกอบที่แตกต่างกันที่นำมา x องค์ประกอบในเวลา = $ ^ np_ {x} / x $
จำนวนการเรียงสับเปลี่ยนแบบวงกลมของ n สิ่งต่างๆ = $ ^ np_ {n} / n $

ปัญหาบางอย่าง

Problem 1 - จากไพ่ 6 ใบที่แตกต่างกันเราจะอนุญาตมันได้กี่วิธี?

Solution- ในขณะที่เรารับไพ่ครั้งละ 6 ใบจากสำรับไพ่ 6 ใบการเรียงสับเปลี่ยนจะเป็น $ ^ 6P_ {6} = 6! = 720 $

Problem 2 - ตัวอักษรของคำว่า 'READER' สามารถจัดเรียงได้กี่วิธี?

Solution - มีตัวอักษร 6 คำ (2 E, 1 A, 1D และ 2R.) ในคำว่า 'READER'

การเปลี่ยนแปลงจะเป็น $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $

Problem 3 - วิธีการจัดเรียงตัวอักษรของคำว่า 'ORANGE' เพื่อให้พยัญชนะอยู่ในตำแหน่งคู่เท่านั้น?

Solution- มีสระ 3 ตัวและพยัญชนะ 3 ตัวในคำว่า 'ORANGE' จำนวนวิธีจัดพยัญชนะกันเอง $ = ^ 3P_ {3} = 3! = 6 $. สถานที่ว่างที่เหลืออีก 3 แห่งจะถูกเติมด้วยเสียงสระ 3 ตัวใน $ ^ 3P_ {3} = 3! = 6 $ วิธี ดังนั้นจำนวนการเปลี่ยนแปลงทั้งหมดคือ $ 6 \ times 6 = 36 $

ชุดค่าผสม

ก combination คือการเลือกองค์ประกอบที่กำหนดซึ่งลำดับไม่สำคัญ

จำนวนชุดค่าผสมทั้งหมดของ n สิ่งที่นำมาครั้งละ r คือ -

$$ ^ nC_ {{r}} = \ frac {n! } {ร! (nr)! } $$

Problem 1

ค้นหาจำนวนชุดย่อยของชุด $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ ที่มี 3 องค์ประกอบ

Solution

จำนวนสมาชิกของเซตคือ 6 และเราต้องเลือก 3 องค์ประกอบจากเซต ที่นี่การสั่งซื้อไม่สำคัญ ดังนั้นจำนวนชุดย่อยจะเป็น $ ^ 6C_ {3} = 20 $

Problem 2

มีผู้ชาย 6 คนและผู้หญิง 5 คนอยู่ในห้อง เราสามารถเลือกผู้ชาย 3 คนและผู้หญิง 2 คนจากห้องได้กี่วิธี?

Solution

จำนวนวิธีในการเลือกผู้ชาย 3 คนจากผู้ชาย 6 คนคือ $ ^ 6C_ {3} $ และจำนวนวิธีในการเลือกผู้หญิง 2 คนจากผู้หญิง 5 คนคือ $ ^ 5C_ {2} $

ดังนั้นจำนวนวิธีทั้งหมดคือ - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $

Problem 3

คุณสามารถเลือกกลุ่มที่แตกต่างกัน 3 กลุ่มของนักเรียน 3 คนจากนักเรียนทั้งหมด 9 คนได้กี่วิธี?

Solution

ให้เรานับกลุ่มเป็น 1, 2 และ 3

สำหรับการเลือก 3 สำหรับนักเรียน 1 ^{เซนต์}กลุ่มจำนวนวิธีที่ - $ ^ 9C_ {3} $

จำนวนของวิธีการเลือก 3 สำหรับนักเรียน 2 ^{ครั้ง}กลุ่มหลังจากที่เลือกกลุ่มที่ 1 - $ ^ 6C_ {3} $

จำนวนของวิธีการเลือก 3 สำหรับนักเรียน 3 ^ถกลุ่มหลังจากเลือก 1 ^{เซนต์}และ 2 ^{ครั้ง}กลุ่ม - $ ^ 3C_ {3} $

ดังนั้นจำนวนวิธีทั้งหมด $ = ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680 $

เอกลักษณ์ของปาสคาล

ตัวตนของปาสคาลมาครั้งแรกโดย Blaise Pascal ใน 17 ^THศตวรรษที่ระบุว่าจำนวนของวิธีการที่จะเลือกองค์ประกอบ k จากองค์ประกอบ n มีค่าเท่ากับผลรวมของจำนวนของวิธีการที่จะเลือก (k-1) องค์ประกอบจาก (n-1) องค์ประกอบ และจำนวนวิธีในการเลือกองค์ประกอบจากองค์ประกอบ n-1

ในทางคณิตศาสตร์สำหรับจำนวนเต็มบวก k และ n: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $

Proof -

$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$

$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {ก! (nk-1)! } $

$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $

$ = (n-1)! \ frac {n} {k! (nk)! } $

$ = \ frac {น! } {ก! (nk)! } $

$ = n_ {C_ {k}} $

หลักการ Pigeonhole

ในปีค. ศ. 1834 ปีเตอร์กุสตาฟเลเจิร์นดิริชเล็ตนักคณิตศาสตร์ชาวเยอรมันได้กล่าวถึงหลักการที่เขาเรียกว่าหลักการลิ้นชัก ตอนนี้เรียกได้ว่าเป็นหลักการของนกพิราบ

Pigeonhole Principleระบุว่าหากมีรูของนกพิราบน้อยกว่าจำนวนนกพิราบทั้งหมดและนกพิราบแต่ละตัวถูกใส่ไว้ในหลุมของนกพิราบจะต้องมีหลุมนกพิราบอย่างน้อยหนึ่งหลุมที่มีนกพิราบมากกว่าหนึ่งตัว ถ้าใส่นกพิราบ n เข้าไปใน m pigeonholes โดยที่ n> m มีรูที่มีนกพิราบมากกว่าหนึ่งตัว

ตัวอย่าง

มีผู้ชายสิบคนอยู่ในห้องและพวกเขามีส่วนร่วมในการจับมือกัน หากแต่ละคนจับมือกันอย่างน้อยหนึ่งครั้งและไม่มีผู้ชายคนใดจับมือของชายคนเดียวกันมากกว่าหนึ่งครั้งแสดงว่ามีผู้ชายสองคนเข้าร่วมในจำนวนการจับมือเดียวกัน
ต้องมีอย่างน้อยสองคนในคลาส 30 คนที่ชื่อขึ้นต้นด้วยตัวอักษรเดียวกัน

หลักการรวม - การยกเว้น

Inclusion-exclusion principleคำนวณจำนวนที่สำคัญของการรวมกันของชุดที่ไม่ปะติดปะต่อกันหลายชุด สำหรับสองชุด A และ B หลักการระบุ -

$ | A \ cup B | = | A | + | B | - | A \ cap B | $

สำหรับสามชุด A, B และ C หลักการระบุ -

$ | A \ cup B \ cup C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ ฝา C | + | A \ cap B \ cap C | $

สูตรทั่วไป -

$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ LIMIT_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ LIMIT_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $

Problem 1

จำนวนเต็ม 1 ถึง 50 เป็นจำนวนเต็มของ 2 หรือ 3 แต่ไม่ใช่ทั้งสองจำนวน

Solution

ตั้งแต่ 1 ถึง 100 มีตัวเลข $ 50/2 = 25 $ ซึ่งเป็นทวีคูณของ 2

มีตัวเลข $ 50/3 = 16 $ ซึ่งเป็นทวีคูณของ 3

มีตัวเลข $ 50/6 = 8 $ ซึ่งเป็นตัวเลขทวีคูณของทั้ง 2 และ 3

ดังนั้น $ | A | = 25 $, $ | B | = 16 $ และ $ | A \ cap B | = 8 $

$ | A \ cup B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $

Problem 2

ในกลุ่มนักเรียน 50 คน 24 คนชอบเครื่องดื่มเย็น ๆ และชอบดื่มร้อน 36 คนและนักเรียนแต่ละคนชอบเครื่องดื่มอย่างน้อยหนึ่งในสองแก้ว หลายคนชอบทั้งกาแฟและชา?

Solution

ให้ X เป็นชุดของนักเรียนที่ชอบเครื่องดื่มเย็นและ Y เป็นชุดของคนที่ชอบเครื่องดื่มร้อน