מאמר זה יתמקד בחלק מיוחד במתמטיקה הנקרא קומבינטוריקה. נוסחאות, כללים, דוגמאות לפתרון בעיות - כל זה תוכל למצוא כאן על ידי קריאת המאמר עד הסוף.
אז מה זה הקטע הזה? קומבינטוריקה עוסקת בסוגיית ספירת החפצים. אבל במקרה זה, החפצים אינם שזיפים, אגסים או תפוחים, אלא משהו אחר. קומבינטוריקה עוזרת לנו למצוא את ההסתברות לאירוע. למשל, כשמשחקים קלפים, מה ההסתברות שליריב יש קלף מנצח? או דוגמה כזו - מה ההסתברות שתקבלו בדיוק לבן משקית של עשרים כדורים? בשביל משימות מהסוג הזה אנחנו צריכים לדעת לפחות את היסודות של החלק הזה של המתמטיקה.
תצורות קומבינטוריות
בהתחשב בסוגיית המושגים והנוסחאות הבסיסיות של קומבינטוריקה, איננו יכולים אלא לשים לב לתצורות קומבינטוריות. הם משמשים לא רק לניסוח, אלא גם לפתרון בעיות קומבינטוריות שונות. דוגמאות לדגמים כאלה הן:
- placement;
- permutation;
- combination;
- הרכב מספר;
- מספר מפוצל.
נדבר על שלושת הראשונים בפירוט רב יותר מאוחר יותר, אבל נשים לב לקומפוזיציה ולפיצול בחלק זה. כאשר הם מדברים על הרכב של מספר מסוים (נניח, a), הם מתכוונים לייצוג של המספר a כסכום מסודר של כמה מספרים חיוביים. ופיצול הוא סכום לא מסודר.
Sections
לפני שניגש ישירות לנוסחאות הקומבינטוריה ולשיקול הבעיות, כדאי לשים לב לעובדה שלקומבינטוריקה, כמו שאר חלקי המתמטיקה, יש תתי סעיפים משלה. אלה כוללים:
- enumerative;
- structural;
- extreme;
- תיאוריית רמזי;
- probabilistic;
- טופולוגי;
- אינסופי.
במקרה הראשון, אנחנו מדברים על קומבינטוריקה ספירתית, הבעיות מתייחסות לספירה או ספירה של תצורות שונות שנוצרות על ידי אלמנטים של קבוצות. ככלל, על קבוצות אלו מוטלות הגבלות מסוימות (הבחנה, אי-הבחנה, אפשרות חזרה וכדומה). ומספר התצורות הללו מחושב באמצעות כלל החיבור או הכפל, שעליו נדבר מעט מאוחר יותר. קומבינטוריקה מבנית כוללת את התיאוריות של גרפים ומטרואידים. דוגמה לבעיית קומבינטוריקה קיצונית היא מהו הממד הגדול ביותר של גרף המקיים את התכונות הבאות… בפסקה הרביעית הזכרנו את תיאוריית רמזי, החוקרת את נוכחותם של מבנים רגילים בתצורות אקראיות. הסתברותיקומבינטוריקה מסוגלת לענות על השאלה - מהי ההסתברות שלסט נתון יש תכונה מסוימת. כפי שאתה יכול לנחש, קומבינטוריקה טופולוגית מיישמת שיטות בטופולוגיה. ולבסוף, הנקודה השביעית - קומבינטוריקה אינסופית חוקרת את היישום של שיטות קומבינטוריקה על קבוצות אינסופיות.
כלל הוספה
בין הנוסחאות של הקומבינטוריקה אפשר למצוא פשוטות למדי, שאנו מכירים כבר זמן רב. דוגמה לכך היא כלל הסכום. נניח שניתנו לנו שתי פעולות (C ו-E), אם הן סותרות זו את זו, פעולה C יכולה להיעשות בכמה דרכים (לדוגמה, a), ופעולה E יכולה להיעשות ב-b-ways, אז כל אחת מהן (C או E) ניתן לעשות בדרכים a + b.
בתיאוריה, זה די קשה להבנה, ננסה להעביר את כל הנקודה באמצעות דוגמה פשוטה. ניקח את מספר התלמידים הממוצע בכיתה אחת - נניח שהוא עשרים וחמישה. ביניהם חמש עשרה בנות ועשרה בנים. מלווה אחד מוקצה לכיתה מדי יום. כמה דרכים יש להקצות מלווה בכיתה היום? הפתרון לבעיה די פשוט, נפנה לכלל ההוספה. הטקסט של המשימה לא אומר שרק בנים או רק בנות יכולים להיות בתפקיד. לכן, זה יכול להיות כל אחת מחמש עשרה הבנות או כל אחד מעשרת הבנים. ביישום כלל הסכום, נקבל דוגמה פשוטה למדי שתלמיד בית ספר יסודי יכול להתמודד איתה בקלות: 15 + 10. לאחר חישוב, נקבל את התשובה: עשרים וחמש. כלומר, יש רק עשרים וחמש דרכיםלהקצות שיעור חובה להיום.
כלל הכפל
כלל הכפל שייך גם לנוסחאות הבסיס של הקומבינטוריקה. נתחיל בתיאוריה. נניח שעלינו לבצע מספר פעולות (א): הפעולה הראשונה מתבצעת ב-1 אופנים, השנייה - ב-2 אופנים, השלישית - ב-3 אופנים, וכן הלאה עד שה-a-action האחרון מתבצע ב-sa אופנים. אז ניתן לבצע את כל הפעולות הללו (שיש לנו סך הכל) ב-N דרכים. כיצד לחשב את ה-N הלא ידוע? הנוסחה תעזור לנו בכך: N \u003d c1c2c3…ca.
שוב, שום דבר לא ברור בתיאוריה, נעבור לדוגמא פשוטה של יישום כלל הכפל. בואו ניקח את אותה כיתה של עשרים וחמישה אנשים, שבה לומדים חמש עשרה בנות ועשרה בנים. רק שהפעם אנחנו צריכים לבחור שני מלווים. הם יכולים להיות רק בנים או בנות, או ילד עם ילדה. אנו פונים לפתרון היסודי של הבעיה. אנו בוחרים את המלווה הראשון, כפי שהחלטנו בפסקה האחרונה, אנו מקבלים עשרים וחמש אפשרויות אפשריות. האדם השני בתפקיד יכול להיות כל אחד מהאנשים הנותרים. היו לנו עשרים וחמישה תלמידים, בחרנו אחד, מה שאומר שכל אחד מעשרים וארבעה האנשים הנותרים יכול להיות השני בתפקיד. לבסוף, אנו מיישמים את כלל הכפל ומגלים שניתן לבחור את שני המלווים בשש מאות דרכים. השגנו את המספר הזה על ידי הכפלת עשרים וחמש ועשרים וארבע.
Swap
עכשיו נשקול עוד נוסחה קומבינטורית אחת. בחלק זה של המאמר, אנחנובואו נדבר על תמורות. שקול את הבעיה מיד עם דוגמה. בוא ניקח כדורי ביליארד, יש לנו מספר 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. ואם אין שלושה כדורים כאלה, אלא עשרה או חמישה עשר? לפרט את כל האפשרויות האפשריות הוא ארוך מאוד, אז קומבינטוריקה באה לעזרתנו. נוסחת התמורה תעזור לנו למצוא את התשובה לשאלתנו. Pn=nP(n-1). אם ננסה לפשט את הנוסחה, נקבל: Pn=n (n - 1) … 21. וזהו המכפלה של המספרים הטבעיים הראשונים. מספר כזה נקרא פקטוריאלי, והוא מסומן כ-n!
בואו נשקול את הבעיה. המנהיג כל בוקר בונה את הניתוק שלו בשורה (עשרים איש). יש שלושה חברים הכי טובים בגזרה - קוסטיה, סשה ולשה. מה ההסתברות שהם יהיו אחד ליד השני? כדי למצוא את התשובה לשאלה, עליך לחלק את ההסתברות לתוצאה "טובה" במספר הכולל של התוצאות. המספר הכולל של התמורות הוא 20!=2.5 קווינטיליון. איך לספור את מספר התוצאות ה"טובות"? נניח שקוסטיה, סשה ולשה הם סופרמן אחד. אז אנחנויש לנו רק שמונה עשר נושאים. מספר התמורות במקרה זה הוא 18=6.5 קוודריליון. עם כל זה, קוסטיה, סשה ולשה יכולים לנוע באופן שרירותי בינם לבין עצמם בשלושה הבלתי ניתנת לחלוקה, וזה עוד 3!=6 אפשרויות. אז יש לנו 18 קבוצות כוכבים "טובות" בסך הכל!3! אנחנו רק צריכים למצוא את ההסתברות הרצויה: (18!3!) / 20! שזה בערך 0.016. אם ממירים אותו לאחוז, מסתבר שזה רק 1.6%.
לינה
עכשיו נשקול עוד נוסחה קומבינטורית חשובה והכרחית. לינה הוא הנושא הבא שלנו, שאנו מציעים שתשקול אותו בחלק זה של המאמר. אנחנו הולכים להיות מסובכים יותר. נניח שאנו רוצים לשקול תמורות אפשריות, רק לא מכל הסט (n), אלא מקבוצה קטנה יותר (m). כלומר, אנו מתייחסים לתמורות של n פריטים לפי m.
יש לשנן את הנוסחאות הבסיסיות של קומבינטוריקה, אלא להבין אותן. גם למרות העובדה שהם הופכים מסובכים יותר, שכן אין לנו פרמטר אחד, אלא שניים. נניח ש-m \u003d 1, ואז A \u003d 1, m \u003d 2, ואז A \u003d n(n - 1). אם נפשט עוד יותר את הנוסחה ונעבור לסימון באמצעות פרמטרים, נקבל נוסחה תמציתית למדי: A \u003d n! / (נ - מ')!
Combination
שקלנו כמעט את כל הנוסחאות הבסיסיות של קומבינטוריקה עם דוגמאות. כעת נעבור לשלב האחרון של בחינת הקורס הבסיסי של קומבינטוריקה – היכרות עם השילוב. כעת נבחר m פריטים מה-n שיש לנו, בעוד שנבחר את כולם בכל הדרכים האפשריות. איך אם כן זה שונה מלינה? אנחנו לאלשקול סדר. הסט הלא מסודר הזה יהיה שילוב.
הצג מיד את הסימון: ג. אנחנו לוקחים מיקומים של m כדורים מתוך n. אנחנו מפסיקים לשים לב לסדר ומקבלים שילובים חוזרים. כדי לקבל את מספר השילובים, עלינו לחלק את מספר המיקומים ב-m! (מ פקטוריאלי). כלומר, C \u003d A/m! לפיכך, יש כמה דרכים לבחור מתוך n כדורים, בערך שווה לכמה לבחור כמעט הכל. יש לכך ביטוי הגיוני: לבחור במעט זהה לזרוק כמעט הכל. חשוב גם להזכיר בשלב זה שניתן להשיג את המספר המרבי של שילובים כאשר מנסים לבחור מחצית מהפריטים.
איך לבחור נוסחה לפתרון בעיה?
בדקנו בפירוט את הנוסחאות הבסיסיות של קומבינטוריקה: מיקום, תמורה ושילוב. כעת המשימה שלנו היא להקל על הבחירה של הנוסחה הדרושה לפתרון הבעיה בקומבינטוריקה. אתה יכול להשתמש בתוכנית הפשוטה הבאה:
- שאל את עצמך: האם סדר האלמנטים נלקח בחשבון בטקסט הבעיה?
- אם התשובה היא לא, השתמש בנוסחת השילוב (C=n! / (m!(n - m)!)).
- אם התשובה היא לא, אז אתה צריך לענות על שאלה נוספת: האם כל האלמנטים כלולים בשילוב?
- אם התשובה היא כן, השתמש בנוסחת התמורה (P=n!).
- אם התשובה היא לא, השתמש בנוסחת ההקצאה (A=n! / (n - m)!).
דוגמה
שקלנו את המרכיבים של קומבינטוריקה, נוסחאות וכמה נושאים אחרים. עכשיו נעבור לבהתחשב בבעיה אמיתית. תאר לעצמך שיש לפניך קיווי, תפוז ובננה.
שאלה ראשונה: בכמה דרכים ניתן לסדר אותם מחדש? לשם כך, אנו משתמשים בנוסחת התמורה: P=3!=6 דרכים.
שאלה שניה: בכמה דרכים אפשר לבחור פרי אחד? זה ברור, יש לנו רק שלוש אפשרויות - בחר קיווי, תפוז או בננה, אבל אנו מיישמים את נוסחת השילוב: C \u003d 3! / (2!1!)=3.
שאלה שלישית: בכמה דרכים אפשר לבחור שני פירות? אילו אפשרויות יש לנו? קיווי ותפוז; קיווי ובננה; תפוז ובננה. כלומר, שלוש אפשרויות, אבל זה קל לבדוק באמצעות נוסחת השילוב: C \u003d 3! / (1!2!)=3
שאלה רביעית: בכמה דרכים אפשר לבחור שלושה פירות? כפי שאתה יכול לראות, יש רק דרך אחת לבחור שלושה פירות: לקחת קיווי, תפוז ובננה. C=3! / (0!3!)=1.
שאלה חמישית: כמה דרכים אפשר לבחור לפחות פרי אחד? מצב זה מרמז שאנו יכולים לקחת אחד, שניים או את כל שלושת הפירות. לכן, נוסיף C1 + C2 + C3=3 + 3 + 1=7. כלומר, יש לנו שבע דרכים לקחת לפחות חתיכת פרי אחת מהשולחן.
