ה ניתוח קומבינטורי הוא תחום לימוד במתמטיקה הקשור לכללי ספירה. בתחילת המאה ה -18, חקר המשחקים הכוללים קוביות וקלפים גרם להתפתחות ספירת התיאוריות.
עבודת הקומבינטוריקה מאפשר מימוש ספירות מדויקות יותר ויותר.העיקרון הבסיסי של ספירה (PFC)הפקטוריאל וסוגי הקיבוץ הם דוגמאות למושגים הנלמדים בניתוח קומבינטורי, אשר בנוסף לספק גדול יותר דיוק עוזר לאהתפתחות תחומים אחרים במתמטיקה, כגון ה הסתברות ו או הבינום של ניוטון.
קרא גם: סידור או çקוֹמבִּינַצִיָה?
לשם מה נועד ניתוח קומבינטורי?
ניתוח קומבינטורי קשור לתהליך הספירה, כלומר לימוד תחום זה במתמטיקה מאפשר לנו לפתח כלים המסייעים לנו לבצע נחשב ביעילות רבה יותר. בואו נסתכל על בעיית ספירה טיפוסית, ראו:
דוגמה 1
שקול שלוש ערים A, B ו- C המחוברות בכבישים המהירים R1, ר2, ר3, ר4 ו- ר5. קבע כמה דרכים נוכל להגיע מעיר A לעיר C דרך עיר B.
שימו לב שאנחנו צריכים לעזוב את העיר A וללכת לעיר B, ורק אז נוכל לנסוע לעיר C, אז בואו ננתח את כל אפשרויות לבצע את האירוע בעקבות הכבישים המהירים.
דרך 1: ר1 → ר3
דרך 2: ר1 → ר4
דרך שלישית: ר1 → ר5
דרך רביעית: ר2 → ר3
דרך חמישית: ר2 → ר4
דרך 6: ר2 → ר5
אז יש לנו שש דרכים שונות להגיע מעיר A לעיר C דרך עיר B. עם זאת, שים לב שהבעיה המוצעת היא יחסית פשוטה וכי הניתוח שבוצע היה מעט מאומץ. אז מעתה ואילך אנו נלמד כלים מתוחכמים יותר המאפשרים לפתור בעיות בהרבה פחות עבודה.
אל תפסיק עכשיו... יש עוד אחרי הפרסום;)
עקרון יסוד של ספירה (PFC)
שקול אירוע E שניתן לבצע ב- n צעדים עצמאיים ורצופים. עכשיו שקול שמספר האפשרויות לבצע את הצעד הראשון שווה ל- P1, דמיין גם שמספר האפשרויות לביצוע השלב השני הוא פ.2וכן הלאה, עד שנגיע לשלב האחרון, בו יש Pלא אפשרויות להתבצע.
עקרון הספירה הבסיסי (PFC) קובע כי ה- אפשרויות כולל של קיום האירוע E ניתן על ידי:
פ1 · עמ '2 ·... · עמ 'לא
לפיכך, הסך הכל ניתן על ידי תוצר האפשרויות של כל אחד מהשלבים המהווים אירוע E. שים לב שכדי לקבוע את האפשרויות הכוללות לקיום אירוע E, יש צורך לדעת את סך האפשרויות לכל אחד מהשלבים.
דוגמה 2
בואו נעשה שוב דוגמה 1 תוך שימוש בעקרון הבסיסי של הספירה.
שקול את התמונה בדוגמה 1.
שימו לב שניתן להפעיל את האירוע בשני שלבים, הראשון עובר מעיר א 'לעיר ב', והשני עובר מעיר ב 'לעיר ג'. לביצוע הצעד הראשון יש לנו שתי אפשרויות (כבישים R1 ו- ר2) וכדי לבצע את השלב השני, יש לנו שלוש אפשרויות (R3, ר4 ו- ר5).
שלב ראשון → שתי אפשרויות
שלב שני → שלוש אפשרויות
לפי העיקרון הבסיסי של הספירה, עלינו לְהַכפִּיל האפשרויות הכוללות של כל שלב.
2 · 3
6
לכן, לעבור מעיר A לעיר C דרך עיר B, יש לנו בסך הכל שש אפשרויות.
דוגמה 3
כמה דרכים ניתן לחלק את שלוש המדליות האולימפיות בתחרות של אופני הרים עם חמישה מתחרים?
ארגון חלוקת המדליות הוא אירוע שניתן לבצע בשלושה שלבים. השלב הראשון הוא לנתח את האפשרויות הכוללות מי יקבל את מדליית הזהב, כלומר חָמֵשׁ אפשרויות.
השלב השני הוא לנתח את האפשרויות מי יקבל את מדליית הכסף, כלומר ארבע, מכיוון שהמקום הראשון אינו נכנס לבחירה זו. השלב השלישי הוא ניתוח האפשרויות הכוללות מי יקבל את מדליית הארד, כלומר שְׁלוֹשָׁה, מכיוון ששני הראשונים כבר נבחרו.
שלב ראשון → חמש אפשרויות
שלב שני → ארבע אפשרויות
שלב שלישי → שלוש אפשרויות
אז, לפי העיקרון הבסיסי של הספירה, יש לנו:
5 · 4 · 3
60 אפשרויות
ראה גם: עקרון ספירת תוספים - איחוד של מערך אחד או יותר
פקטוריאל
או מפעל היא דרך של לפרק מספר טבעי. כדי לחשב את הפקטוריון של מספר, פשוט הכפל אותו בכל קודמיו עד למספר 1. המפעל מיוצג על ידי סימן הקריאה - "!".
ראה כמה דוגמאות כיצד לחשב את הפקטוריון של מספרים מסוימים.
ה) 2! (קורא: שני עובדות)
לצורך החישוב, פשוט הכפל את המספר שמלווה את המפעל בכל קודמיו עד למספר 1, כך:
2! = 2 ·1 = 2
ב) 4! = 4 · 3 · 2 ·1 = 24
ç) 5! = 5 · 4 · 3 · 2 · 1 = 120
ד) 1! = 1
רשמית אנו יכולים לכתוב את המפעל כדלקמן:
שקול מספר טבעי n> 2. הפקטוריון של n מסומן על ידי n! וניתן על ידי הכפלת n בכל קודמיו השלמים החיוביים.
לא! = n (n - 1) · (n - 2) · (n - 3) ·... · 1
שימו לב לפקטוריונים הבאים:
4! ו 5!
כעת בצע את הפיתוח של שניהם:
5! = 5 · 4 · 3 · 2 · 1
4! = 4 · 3 · 2 ·1
שימו לב שבפיתוח של 5! נראה ההתפתחות של 4!. כדי שנוכל לכתוב את ה -5! לכן:
5! = 5 · 4 · 3 · 2 · 1
5! = 5 · 4!
דוגמה 4
חשב את שניות הפקטוריאליְלָלָה:
ראה כי 15! פותחה עד ה 13!. שימו לב גם, במניין השבר, האלמנטים מוכפלים, כך שנוכל "לחתוך" את 13!, וכתוצאה מכך רק 15 · 14.
תַצְפִּית:0! = 1
סוגי קיבוץ
חלק מבעיות הספירה מורכבות יותר ונפתרות ביתר קלות בעזרת כלים חדשים. כלים אלה נקראים קיבוץ מכיוון שהם מקבצים אלמנטים בדרכים שונות, מה שמקל על תהליך הספירה. קיבוצים אלה הם: סידור פשוט, תמורה ושילוב פשוט.
סידור פשוט
שקול סט עם אלמנטים נפרדים. בוא נקרא לזה הֶסדֵר מ- n האלמנטים הנלקחים מ- p ל- p, כל רצף המסודר על ידי p והאלמנטים המובהקים שנבחרו בין האלמנטים.
לפיכך, מספר קבוצות המשנה שנוצרו על ידי אלמנטים p יהיה הסדר של n אלמנטים שנלקחו מ- p ל- p. הנוסחה המאפשרת לנו לחשב את מספר הסידורים ניתנת על ידי:
דוגמה 5
חשב את הערך של A.4,2 + א5,2.
כדי לחשב את ערך הביטוי, נקבע כל אחד מהמערכים ואז נוסיף את הערכים הללו. כדי לקבוע את הערך של כל מערך, עלינו להחליף את הערכים בנוסחה.
שים לב ש- n = 4 ו- p = 2, שניהם הוחלפו בנוסחה. כעת, עלינו לחשב את הערך של מערך חמשת האלמנטים שנלקחו שניים ושניים.
אז עלינו:
ה4,2 + א5,2
12 + 20
32
דוגמה 6
כמה מספרים טבעיים מובחנים של ארבע ספרות יכולים להיווצר באמצעות המספרים 2, 3, 4, 5, 6, 7, 8 ו- 9?
בבעיה זו אנו יכולים להשתמש בסידור הפשוט מאז 2435 ≠ 4235. נראה שבמקרים מסוימים סדר היסודות אינו מבדיל אותם, ולכן איננו יכולים להשתמש בסידור.
מכיוון שאנו רוצים לקבוע את סך המספרים שניתן ליצור, שימו לב כי סך האלמנטים שווה ל- שמונה, ואנחנו רוצים לקבץ אותם ארבע על ארבע, אז:
תמורה פשוטה
שקול סט עם אלמנטים n. בוא נקרא לזה תמורה פשוטה של n אלמנטים כל סידור של n אלמנטים שנלקחו n עד n. אז עלינו:
כדי שלא יהיה שום בלבול בין המושגים, בואו נציין את התמורה הפשוטה של n אלמנטים על ידי Pלא. אז עלינו:
פלא = n!
דוגמה 7
חשב את P7 ו פ3.
כדי לחשב תמורות אלה, עלינו להחליף את הערכים בנוסחה. תראה:
פ7 = 7 · 6 · 5· 4 · 3 · 2 · 1
פ7 = 5040
פ3 = 3 · 2 · 1
פ3 = 6
דוגמה 8
קבע כמה אנגרמות יכולות להיות במילה ברזיל.
אנו מבינים כאנגרמה את כל ההעברות האפשריות של אותיות המילה, למשל, "ליסרב" הוא א אֲנַגְרַמָה של המילה ברזיל. כדי לקבוע את מספר האנגרמות, עלינו לחשב את התמורה של האותיות במילה, ולכן עלינו:
פ6 = 6!
פ6 = 6 · 5 · 4 · 3 · 2 · 1
פ6 = 720
לכן, למילה ברזיל יש 720 אנגרמות.
גישה גם: תמורה עם אלמנטים חוזרים ונשנים
שילוב פשוט
שקול סט A עם n אלמנטים מובחנים. בוא נקרא לזה קוֹמבִּינַצִיָה של n האלמנטים שנלקחו p עד p כל תת-קבוצה של A שנוצרת על ידי אלמנטים p. הנוסחה לחישוב השילוב ניתנת על ידי:
דוגמה 9
חשב את השילוב של 10 אלמנטים שנלקחו מארבעה לארבעה.
דוגמה 10
כמה רביעיות נוכל להיווצר עם קודקודים בנקודות A, B, C, D, E ו- F?
שים לב כי רבוע ה- ABCD זהה לארבע CDBA בהקשר זה, לכן עלינו להשתמש בשילוב ולא במערכים. יש לנו בסך הכל שש נקודות ואנחנו רוצים לשלב אותן ארבע על ארבע, כך:
לכן, אנו יכולים ליצור 15 רביעיות נפרדות.
ניתוח משולב והסתברות
המחקר של ההסתברות קשורה קשר הדוק לחקר ניתוח קומבינטורי.. בחלק מבעיות ההסתברות, יש צורך לקבוע את מרחב המדגם, המורכב מערך שנוצר על ידי כל התוצאות האפשריות של אירוע נתון.
במקרים מסוימים, מרחב הדגימה E כתוב באופן ישיר מאוד, כמו בהפכת מטבע הוגן, כאשר התוצאות האפשריות הן ראשים או זנבות ומסומנות כך:
E = {ראשים, זנבות}
עכשיו דמיין את המצב הבא: מת מושלך שלוש פעמים ברציפות ואנחנו מעוניינים לקבוע את שטח הדגימה לניסוי זה. שימו לב כי רישום כל האפשרויות איננו עוד משימה פשוטה, עלינו להשתמש בעקרון הבסיסי של ספירה (PFC). ניתן לבצע את האירוע בשלושה שלבים, בכל אחד מהם יש לנו שש אפשרויות, שכן למות יש שש פנים, כך:
שלב ראשון → שש אפשרויות
שלב שני → שש אפשרויות
שלב שלישי → שש אפשרויות
לפי ה- PFC, יש לנו כי סך האפשרויות הוא:
6 · 6 · 6
216
אז נוכל לומר שמרחב המדגם של אירוע זה הוא 216.
ראה כי לשם חקר ההסתברות זהו נדרש ידע בסיסי בניתוח קומבינטורי.מכיוון שללא קביעת שטח הדגימה של ניסוי, אי אפשר לפתור את הרוב המכריע של תרגילי ההסתברות. לפרטים נוספים על תחום זה של מתמטיקה, קרא את הטקסט:הִסתַבְּרוּת.
תרגילים נפתרו
שאלה 1 - קבע את מספר האנגרמות של המילה טירה. ואז קבע את מספר האנגרמות המתחילות באות c.
פתרון הבעיה
כדי לקבוע את מספר האנגרמות, עלינו לחשב את התמורה של מספר האותיות כך:
פ7 = 7!
פ7 = 7 · 6 · 5 · 4 · 3 · 2 · 1
פ7 = 5040
למילה 5040 אנגרמות. כעת, כדי לקבוע את מספר האנגרמות שמתחילות באות c, עלינו לתקן את האות ולחשב את האנגרמה של האחרות, ראה:
Ç__ __ __ __ __ __
כשאנחנו מתקנים את האות c, שים לב שנותרו שישה שדות לחישוב התמורה, כך:
פ6 = 6!
פ6 = 6 · 5 · 4 · 3 · 2 · 1
פ6 = 720
אז יש לנו 720 אנגרמות של המילה טירה שמתחילות באות c.
שאלה 2 - בכיתה יש חמישה גברים ושבע נשים. כמה קבוצות של שלושה גברים וארבע נשים יכולות להיווצר?
פתרון הבעיה
ראשית, בדוק שהסדר בו אנו בוחרים אנשים לא משנה, למשל הקבוצה שהקים ג'ואו, מרקוס וחוסה היא אותה קבוצה שהוקמה על ידי מרקוס, ז'ואאו וחוסה, לכן עלינו להשתמש בשילוב עבור תַחשִׁיב.
בואו נחשב בנפרד את מספר הקבוצות שיכולות להיווצר על ידי גברים ונשים, וב- אז בואו ונכפיל את התוצאות הללו, מכיוון שכל קבוצת גברים יכולה להתערבב עם כל קבוצה של נשים.
גברים
סה"כ → 5
כמות בקבוצה → 3
נשים
סה"כ → 7
כמות בקבוצה → 4
לכן, המספר הכולל של קבוצות שיכולות להיווצר על ידי שלושה גברים וארבע נשים הוא:
Ç5,3 · Ç7,4
10 · 35
350
מאת רובסון לואיז
מורה למתמטיקה
