קומבינטוריקה- זהו ענף במתמטיקה, שעיקר תפקידו הוא לספור את מספר האפשרויות שעולות במצב נתון. כאשר פותרים בעיות באמצעות ההגדרה הקלאסית של הסתברות, אנו זקוקים לכמה נוסחאות קומבינטוריות.

מקומות לינה.

הגדרה 1.על ידי הצבה ללא חזרה על נאלמנטים על ידי קכל דבר נקרא מְסוּדָרתת-קבוצה של קבוצה נתונה M=(a 1 ,a 2 ,¼,a n ),המכיל k אלמנטים.

שימו לב שמיד נובע מההגדרה שראשית כל המרכיבים בסידור ללא חזרות שונים (אחרת יש שני אלמנטים זהים), ושנית, k £ n, שלישית, שני מיקומים שונים ללא חזרות שונים גם כן הרכבהמרכיבים המרכיבים שלהם, או בסדרהמיקום שלהם. כלומר, הסדר חשוב.

משפט 1.מספר סידורים שונים ללא חזרות של n אלמנטים על ידי k (k £ n)שווים

הוכחה.

תן M={a 1 ,a 2 ,¼,a n). זה נדרש לקבוע את מספר המחרוזות הנבדלות של הטופס ( x 1, x 2, ¼, x k), שבו כל האלמנטים x 1 ,x 2 ,0,x k ОMושונה. אלמנט ראשון איקס 1 יכול לבחור נדרכים. אם x 1כבר נבחר, ואז לבחור איקס 2 אלמנטים שמאליים n-1. כְּמוֹ כֵן, איקס 3 יכולים לבחור נ-2 דרכים וכו'. אלמנט אחרון x kיכול לבחור n-k+1דרכים. מכפלת המספרים הללו נקבל נוסחה (4) המשפט מוכח.

דוגמה 1יש 12 מקצועות בכיתה ו-5 שיעורים שונים ביום שני. בכמה דרכים ניתן לארגן את לוח השיעורים ליום שני?

מספר אפשרויות לוח הזמנים האפשריות הוא, כמובן, מספר הסידורים השונים של 12 אלמנטים של 5, כלומר

מקרה מיוחד חשוב הוא המקרה כאשר n=k, כלומר, כאשר במחרוזת ( x1,x2,¼,xn)כל המרכיבים של הסט מעורבים M. מיתרים ללא חזרות, מורכבים מ-n אלמנטים של הסט Mנקראים תמורות של n אלמנטים. נזכיר שבמתמטיקה דרך נ! ציינו את המכפלה של כל המספרים הטבעיים מ-1 עד n, כלומר ¼, ובהגדרה קחו בחשבון ש-0!=1.

מסקנה 1. באמצעות נוסחה (4), אנו מוצאים את זה מספר תמורות שונות P nמ נאלמנטים שווים P n = n!.

הגדרה 2.מיקום עם חזרות של נאלמנטים לפי k הוא כל מחרוזת מסודרת מ קלהגדיר אלמנטים M=(a 1 ,a 2 ,¼,a n ),חלקם עשויים לחזור על עצמם.

לדוגמה, המילה "אמא" היא מיקום עם חזרות של 2 אלמנטים M=(מ,א) על 4.

משפט 2.מספר מיקומים שונים עם חזרות מ נאלמנטים על ידי ק

הוכחה.

האלמנט הראשון במחרוזת מ קניתן לבחור פריטים נדרכים, כי |M|=n.באופן דומה, ניתן לבחור את האלמנטים ה-2, ה-3, ...,kth ב-n דרכים. מכפילים את המספרים הללו, נקבל

קפַּעַם

המשפט הוכח.

דוגמה 2כמה מספרים דו ספרתיים שונים אפשר ליצור מהמספרים 1, 2, 3, 4, 5?

במשימה זו M=(1, 2, 3, 4, 5), n=5, k=2. לכן, התשובה היא המספר

דוגמה 3בכמה דרכים ניתן לחלק k נוסעים בין n מכוניות, אם עבור כל נוסע יש משמעות רק למספר המכונית, ולא המקום שהוא תופס במכונית?

מספור מחדש את כל הנוסעים. תן איקס 1 - מספר הכרכרה שנבחר על ידי הנוסע הראשון, איקס 2 - מספר המכונית של הנוסע השני, ..., x k- מספר עגלה קהנוסע ה-. קו ( x 1, x 2, ¼, x k) מאפיין באופן מלא את חלוקת הנוסעים בין המכוניות. כל אחד מהמספרים x 1, x 2, ¼, x kיכול לקחת כל ערך מספר שלם מ-1 עד n. אז בדוגמה הזו

M=(1, 2,…,n) ויהיו התפלגויות שונות בין מכוניות כמו שיש שורות באורך k שניתן להרכיב מהאלמנטים של הסט M, זה

נציין שוב כי בהצבות עם חזרות וללא חזרות יש חשיבות לסדר האלמנטים. אם הסדר של האלמנטים אינו משמעותי, אז במקרה זה הם מדברים על שילובים.

שילובים(ללא חזרה).

הגדרה 3.תן M=(a 1 ,a 2 ,0,a n ).כל תת-קבוצה איקססטים Mמֵכִיל קאלמנטים נקראים שילוב של k אלמנטים מתוך n.

נציין מיד שבהגדרה זו סדר מרכיבי הסט איקסלא משמעותי וזה k£n, בגלל ה k=½X½, n=½M½ו XOM.

משפט 3.מספר שילובים שונים קאלמנטים מ נשווים

. (6)

הוכחה.

כל שילוב קאלמנטים מ-n יוצרים ק!סידורים שונים ללא חזרות מ-n עד k בעזרת תמורות שונות (ראה מסקנה 1). לפיכך, כל השילובים של k אלמנטים מתוך n לאחר שונים ק!תמורות מייצרות את כל המיקומים ללא חזרות מ נעַל ק. בגלל זה. כתוצאה מכך,

בקומבינטוריקה נלמדות שאלות לגבי כמה שילובים מסוג מסוים ניתן לעשות מאובייקטים (אלמנטים) נתונים.

לידתה של קומבינטוריקה כמדור קשורה לעבודותיהם של B. Pascal ו-P. Fermat על תורת ההימורים. תרומה גדולה לפיתוח שיטות קומבינטוריות ניתנה על ידי G.V. לייבניץ, ג'יי ברנולי ול' אוילר.

הפילוסוף, הסופר, המתמטיקאי והפיזיקאי הצרפתי בלייז פסקל (1623–1662) הראה בשלב מוקדם את יכולתו המתמטית יוצאת הדופן. מעגל האינטרסים המתמטיים של פסקל היה מגוון מאוד. פסקל הוכיח את זה
ממשפטי היסוד של הגיאומטריה השלכתית (משפט פסקל), תכנן מכונת סיכומים (מכונת החיבור של פסקל), נתן שיטה לחישוב מקדמים בינומיים (משולש פסקל), לראשונה הגדיר ויישם במדויק את שיטת האינדוקציה המתמטית להוכחה, עשה צעד משמעותי בפיתוח של ניתוח אינפיניטסימלי, מילא תפקיד חשוב בהולדת תורת ההסתברות. בהידרוסטטיקה קבע פסקל את חוק היסוד שלו (חוק פסקל). מכתביו של פסקל לפרובינציאל היו יצירת מופת של הפרוזה הקלאסית הצרפתית.

גוטפריד וילהלם לייבניץ (1646–1716) היה פילוסוף, מתמטיקאי, פיזיקאי וממציא, עורך דין, היסטוריון ובלשן גרמני. במתמטיקה, יחד עם I. ניוטון, הוא פיתח חשבון דיפרנציאלי ואינטגרלי. הוא תרם תרומה חשובה לקומבינטוריקה. בפרט, בעיות תיאורטיות המספרים קשורות בשמו.

לגוטפריד וילהלם לייבניץ היה מראה מעט מרשים ולכן עשה רושם של אדם די לא ברור. פעם אחת בפריז, הוא נכנס לחנות ספרים בתקווה לקנות ספר מאת הפילוסוף המכר שלו. כאשר אורח שאל על הספר הזה, מוכר הספרים, לאחר שבחן אותו מכף רגל ועד ראש, ענה בלעג: "למה אתה צריך את זה? האם אתה מסוגל לקרוא ספרים כאלה?" לפני שהמדען הספיק לענות, נכנס מחבר הספר עצמו לחנות במילים: "ברכות וכבוד ללייבניץ הגדול!" המוכר לא הצליח להבין שבאמת יש לו את לייבניץ המפורסם, שספריו היו מבוקשים מאוד בקרב מדענים.

בעתיד, הדברים הבאים ישחקו תפקיד חשוב.

לממה.תן בסט האלמנטים, ובסט - אלמנטים. אז המספר של כל הזוגות הנבדלים, שבו יהיה שווה ל.

הוכחה.ואכן, עם אלמנט אחד מהקבוצה נוכל ליצור זוגות כל כך שונים, אבל רק בקבוצת האלמנטים.

מיקומים, תמורות, שילובים

נניח שיש לנו קבוצה של שלושה אלמנטים. באילו דרכים נוכל לבחור שניים מהאלמנטים הללו? .

הַגדָרָה.סידורים של קבוצה של אלמנטים שונים לפי אלמנטים הם צירופים המורכבים מאלמנטים נתונים לפי > אלמנטים ונבדלים זה מזה באלמנטים עצמם או בסדר האלמנטים.

מספר כל הסידורים של קבוצת אלמנטים לפי אלמנטים מסומן על ידי (מהאות הראשונית של המילה הצרפתית "סידור", שפירושה מיקום), איפה ו.

מִשׁפָּט.מספר המיקומים של קבוצת אלמנטים לפי אלמנטים שווה ל

הוכחה.נניח שיש לנו אלמנטים. תן להיות מיקומים אפשריים. נבנה את המיקומים האלה ברצף. ראשית, הבה נגדיר את רכיב המיקום הראשון. מתוך סט נתון של אלמנטים, ניתן לבחור אותו בדרכים שונות. לאחר בחירת האלמנט הראשון עבור האלמנט השני, יש דרכים לבחור, וכן הלאה. מכיוון שכל בחירה כזו מעניקה מיקום חדש, ניתן לשלב את כל הבחירות הללו באופן חופשי אחד עם השני. לכן יש לנו:

דוגמא.בכמה דרכים דגל יכול להיות מורכב משלושה פסים אופקיים בצבעים שונים אם יש חומר של חמישה צבעים?

פִּתָרוֹן.המספר הרצוי של דגלי שלושה פסים:

הַגדָרָה.תמורה של קבוצת אלמנטים היא סידור האלמנטים בסדר מסוים.

לפיכך, כל התמורות השונות של קבוצה של שלושה אלמנטים הם

המספר של כל התמורות של היסודות מצוין (מהאות הראשונית של המילה הצרפתית "תמורה", שפירושה "תמורה", "תנועה"). לכן, מספר כל התמורות השונות מחושב על ידי הנוסחה

דוגמא.בכמה דרכים אפשר להניח את הצריחים על לוח שחמט כדי שלא יתקפו זה את זה?

פִּתָרוֹן.המספר הנדרש של מיקום הצריח

לפי הגדרה!

הַגדָרָה.שילובים של אלמנטים שונים לפי אלמנטים הם שילובים המורכבים מאלמנטים נתונים לפי אלמנטים ונבדלים זה מזה באלמנט אחד לפחות (במילים אחרות, תת-קבוצות של אלמנטים של קבוצה נתונה של אלמנטים).

כפי שניתן לראות, בשילובים, בניגוד למיקומים, סדר האלמנטים אינו נלקח בחשבון. המספר של כל צירופי האלמנטים לפי אלמנטים בכל אחד מהם מצוין (מהאות הראשונית של המילה הצרפתית "קומבינה", שפירושה "שילוב").

מספרים

כל השילובים מהסט של שניים - .

מאפייני מספר (\sf C)_n^k

ואכן, כל תת קבוצת אלמנטים של קבוצת אלמנטים נתונה תואמת תת קבוצת אלמנטים אחת ויחידה של אותה קבוצה.

ואכן, אנו יכולים לבחור תת-קבוצות של אלמנטים באופן הבא: אנו מתקנים אלמנט אחד; מספר תת-הרכיבים המכילים אלמנט זה הוא ; מספר קבוצות המשנה של אלמנטים שאינן מכילות אלמנט זה הוא .

המשולש של פסקל

במשולש זה, המספרים הקיצוניים בכל שורה שווים ל-1, וכל מספר לא קיצוני שווה לסכום שני המספרים של השורה הקודמת שמעליו. לפיכך, משולש זה מאפשר לך לחשב מספרים.

מִשׁפָּט.

הוכחה.שקול קבוצה של אלמנטים ופתור את הבעיה הבאה בשתי דרכים: כמה רצפים יכולים להיות מורכבים מאלמנטים של נתון
קבוצות שבהן לא מופיע אלמנט פעמיים?

דרך אחת. אנו בוחרים את האיבר הראשון ברצף, לאחר מכן את השני, השלישי וכן הלאה. חבר

2 כיוונים. תחילה אנו בוחרים אלמנטים מקבוצה נתונה, ולאחר מכן מסדרים אותם בסדר מסוים

הכפל את המונה והמכנה של שבר זה ב:

דוגמא.בכמה דרכים אפשר לבחור 5 מספרים מתוך 36 במשחק Sportloto?

מספר הדרכים הרצוי

משימות.

1. מספרי מכוניות מורכבים מ-3 אותיות באלפבית הרוסי (33 אותיות) ו-4 מספרים. כמה מספרי רכב שונים יש?
2. לפסנתר 88 קלידים. בכמה דרכים ניתן להפיק 6 צלילים ברצף?
3. כמה מספרים בני שש ספרות מתחלקים ב-5?
4. בכמה דרכים אפשר להכניס 7 מטבעות שונים לשלושה כיסים?
5. כמה מספרים בני 5 ספרות יכולים להיווצר המכילים את הספרה 5 לפחות פעם אחת בסימון העשרוני?
6. בכמה דרכים אפשר להושיב 20 אנשים ליד שולחן עגול, בהתחשב בכך שהדרכים יהיו זהות, אם ניתן להשיג אותם זה מזה על ידי תנועה במעגל?
7. כמה מספרים בני חמש ספרות המתחלקים ב-5 יש שאין להם אותן ספרות?
8. על נייר משובץ עם צד תא של 1 ס"מ, מציירים עיגול ברדיוס 100 ס"מ, שאינו עובר דרך ראשי התאים ואינו נוגע בדפנות התאים. כמה ריבועים יכול המעגל הזה לחתוך?
9. בכמה דרכים ניתן לסדר מספרים בשורה כך שהמספרים יעמדו זה לצד זה ויתרה מכך, ילכו בסדר עולה?
10. כמה מספרים בני חמש ספרות ניתן ליצור מספרות אם ניתן להשתמש בכל ספרה רק פעם אחת?
11. מהמילה ROT, על ידי סידור מחדש של האותיות, ניתן לקבל גם את המילים הבאות: TOR, ORT, OTR, TRO, RTO. הם נקראים אנגרמות. כמה אנגרמות אתה יכול לעשות עם LOGARITH?
12. בואו נתקשר פְּצִיחָהמספר טבעי הוא הייצוג שלו כסכום של מספרים טבעיים. הנה, למשל, כל המחיצות של מספר:

מחיצות נחשבות שונות אם הן נבדלות במספרים או בסדר הסכומים.

כמה מחיצות שונות של מספר יש?
13. כמה מספרים בני 3 ספרות לא הולכים וגדלים יש?
14. כמה מספרים בני 4 ספרות לא הולכים וגדלים יש?
15. בכמה דרכים אפשר להושיב 17 אנשים בשורה כדי שיהיו זה ליד זה?
16. בנות ובנים יושבים באופן אקראי בשורה של מקומות. בכמה דרכים אפשר להושיב אותם כך שאף בנות לא יושבות זו לצד זו?
17. בנות ובנים יושבים באופן אקראי בשורה של מקומות. בכמה דרכים אפשר להושיב אותם כך שכל הבנות יושבות זו לצד זו?

שילובים. מקומות לינה. תמורות

תמורותנקראים שילובים המורכבים מאותו הדבר נאלמנטים שונים ונבדלים רק בסדר סידורם. מספר כל התמורות האפשריות

שקול דוגמה: כמה מספרים תלת ספרתיים ניתן ליצור מהספרות 1,2,3, אם כל ספרה נכללת בתמונה של המספר רק פעם אחת?

פִּתָרוֹן:

או ככה דוגמא. סדר הדיבורים של שבעה משתתפים בכנס הסטודנטים נקבע בהגרלה. כמה גרסאות שונות של ההגרלה אפשריות?

פִּתָרוֹן:כל גרסה של ההגרלה שונה רק בסדר המשתתפים, כלומר, מדובר בתמורה של 7 אלמנטים. המספר שלהם הוא

דוגמא. 4 אנשים פנו במקביל לקופאית כדי לקבל כסף. בכמה דרכים הם יכולים להסתדר?

פִּתָרוֹן:התור מורכב מ-4 אנשים שונים, לכן, בכל שיטת תור, סדר מיקומם נלקח בחשבון. לפיכך, יש תמורות של ארבעה אנשים, מספרם שווה ל

מיקומים נאלמנטים שונים לפי Mאלמנטים שונים זה מזה בסדר שלהם או בהרכב היסודות.

מספר כל המיקומים האפשריים מחושב

דוגמא:כמה אותות ניתן ליצור מ-6 דגלים בצבעים שונים, שניים על שניים?

פִּתָרוֹן:

דוגמא:לוח הזמנים של יום אחד מורכב מחמישה שיעורים. קבע את מספר אפשרויות לוח הזמנים בעת בחירה מתוך 11 דיסציפלינות.

פִּתָרוֹן:כל אפשרות לוח זמנים מייצגת קבוצה של 5 דיסציפלינות מתוך 11, השונה מאפשרויות אחרות הן בהרכב הדיסציפלינות והן לפי הסדר שהן עוקבות אחריהן, כלומר, מדובר בסידור של 11 אלמנטים לפי 5. מספר לוח הזמנים אפשרויות נמצאות לפי הנוסחה

שילוביםנקראים צירופים המורכבים מ נאלמנטים שונים לפי Mאלמנטים הנבדלים באלמנט אחד לפחות. מספר שילובים

דוגמא:בכמה דרכים ניתן לבחור 2 פריטים מקופסה המכילה 10 פריטים?

פִּתָרוֹן:

דוגמא: 16 אנשים משתתפים בטורניר שחמט. כמה משחקים חייבים לשחק בטורניר אם יש לשחק משחק אחד בין שני משתתפים?

פִּתָרוֹן:כל משחק משוחק על ידי שני משתתפים מתוך 16 והוא שונה רק בהרכב הזוגות של המשתתפים, כלומר, מדובר בשילוב של 16 אלמנטים של שניים.

דוגמא:ישנם 6 זנים של חיידקים. יש לבחור שלושה זנים כדי לקבוע את קצב הגדילה שלהם. בכמה דרכים אפשר לעשות זאת?

פִּתָרוֹן:שיטות הבחירה נחשבות שונות אם כל זן שנבחר שונה באלמנט אחד לפחות. המספר הזה

כלומר, יש 20 דרכים.

נדגיש שמספרי המיקומים, התמורות והשילובים קשורים בשוויון

בעת פתרון בעיות, קומבינטוריקה משתמשת בכללים הבאים.

כלל סכום:אם מתנגד כלשהו אניתן לבחור מתוך קבוצה של אובייקטים Mדרכים, ועוד חפץ בְּניתן לבחור נדרכים, ואז בחר באחת מהן אבל, או בְּדרכים אפשריות.

חוק מוצר:אם חפץ אבלניתן לבחור מתוך קבוצה של אובייקטים Mדרכים ואחרי כל בחירה כזו, האובייקט בְּיכול לבחור נדרכים, ואז זוג חפצים ( א, ב)לפי סדר זה ניתן לבחור בדרכים.

מאמר זה יתמקד בענף מיוחד במתמטיקה הנקרא קומבינטוריקה. נוסחאות, כללים, דוגמאות לפתרון בעיות - כל זה תוכלו למצוא כאן בקריאת המאמר עד הסוף.

אז מה זה הסעיף הזה? קומבינטוריקה עוסקת בסוגיית ספירת החפצים. אבל במקרה זה, החפצים אינם שזיפים, אגסים או תפוחים, אלא משהו אחר. קומבינטוריקה עוזרת לנו למצוא את ההסתברות לאירוע. למשל כשמשחקים קלפים - מה ההסתברות שליריב יש קלף מנצח? או דוגמה כזו - מה ההסתברות שתקבלו בדיוק לבן משקית של עשרים כדורים? זה עבור סוג זה של משימות שאנחנו צריכים לדעת לפחות את היסודות של חלק זה של מתמטיקה.

תצורות קומבינטוריות

בהתחשב בשאלת המושגים והנוסחאות הבסיסיות של קומבינטוריקה, איננו יכולים אלא לשים לב לתצורות קומבינטוריות. הם משמשים לא רק לניסוח, אלא גם כדי לפתור דוגמאות שונות של מודלים כאלה:

• דִיוּר;
• תְמוּרָה;
• קוֹמבִּינַצִיָה;
• הרכב מספרים;
• פיצול המספר.

על שלושת הראשונים נדבר בפירוט רב יותר מאוחר יותר, אך נשים לב לקומפוזיציה ולפיצול בחלק זה. כאשר הם מדברים על הרכב של מספר מסוים (נניח, a), הם מתכוונים לייצוג של המספר a כסכום מסודר של כמה מספרים חיוביים. פיצול הוא סכום לא מסודר.

מקטעים

לפני שנמשיך ישירות לנוסחאות הקומבינטוריקה ולשיקול הבעיות, כדאי לשים לב לעובדה שלקומבינטוריקה, כמו לענפי מתמטיקה אחרים, יש תתי סעיפים משלה. אלו כוללים:

• ספירה;
• מִבנִי;
• קיצוני;
• תיאוריית רמזי;
• הסתברותי;
• טופולוגי;
• אינסופי.

במקרה הראשון, אנחנו מדברים על קומבינטוריקה ספירת, הבעיות מתייחסות לספירה או ספירה של תצורות שונות שנוצרות על ידי אלמנטים של קבוצות. ככלל, על קבוצות אלו מוטלות הגבלות מסוימות (הבחנה, אי-הבחנה, אפשרות חזרה וכדומה). ומספר התצורות הללו מחושב באמצעות כלל החיבור או הכפל, שעליו נדבר מעט מאוחר יותר. קומבינטוריקה מבנית כוללת את התיאוריות של גרפים ומטרואידים. דוגמה לבעיית קומבינטוריקה קיצונית היא מהו הממד הגדול ביותר של גרף המקיים את התכונות הבאות... בפסקה הרביעית הזכרנו את תיאוריית רמזי, החוקרת את נוכחותם של מבנים רגילים בתצורות אקראיות. קומבינטוריקה הסתברותית מסוגלת לענות על השאלה - מהי ההסתברות שלסט נתון יש תכונה מסוימת. כפי שאתה יכול לנחש, קומבינטוריקה טופולוגית מיישמת שיטות בטופולוגיה. ולבסוף, הנקודה השביעית - קומבינטוריקה אינסופית חוקרת את היישום של שיטות קומבינטוריקה על קבוצות אינסופיות.

כלל הוספה

בין הנוסחאות של הקומבינטוריקה אפשר למצוא גם פשוטות למדי, שאנו מכירים כבר זמן רב. דוגמה לכך היא כלל הסכום. נניח שניתנו לנו שתי פעולות (C ו-E), אם הן סותרות זו את זו, פעולה C יכולה להיעשות בכמה דרכים (לדוגמה, a), ופעולה E יכולה להתבצע בדרכים b, אז כל אחת מהן (C או E) ניתן לעשות בדרכים a + b.

בתיאוריה, זה די קשה להבנה, ננסה להעביר את כל הנקודה עם דוגמה פשוטה. ניקח את מספר התלמידים הממוצע בכיתה אחת - נניח שהוא עשרים וחמישה. ביניהם חמש עשרה בנות ועשרה בנים. מלווה אחד מוקצה לכיתה מדי יום. כמה דרכים יש להקצות היום מלווה בכיתה? הפתרון לבעיה די פשוט, נפנה לכלל ההוספה. הטקסט של המשימה לא אומר שרק בנים או רק בנות יכולים להיות בתפקיד. לכן, זה יכול להיות כל אחת מחמש עשרה הבנות או כל אחד מעשרת הבנים. יישום כלל הסכום, נקבל דוגמה פשוטה למדי שתלמיד בית ספר יסודי יכול להתמודד איתה בקלות: 15 + 10. לאחר חישוב, נקבל את התשובה: עשרים וחמש. כלומר, יש רק עשרים וחמש דרכים להקצות שיעור תורן להיום.

כלל הכפל

כלל הכפל שייך גם לנוסחאות הבסיס של הקומבינטוריקה. נתחיל בתיאוריה. נניח שעלינו לבצע מספר פעולות (א): הפעולה הראשונה מתבצעת ב-1 אופנים, השנייה - ב-2 אופנים, השלישית - ב-3 אופנים, וכן הלאה עד שה-a-פעולה האחרונה מתבצעת ב-sa אופנים. לאחר מכן ניתן לבצע את כל הפעולות הללו (שיש לנו סך הכל) ב-N דרכים. כיצד לחשב את ה-N הלא ידוע? הנוסחה תעזור לנו בכך: N \u003d c1 * c2 * c3 * ... * כ.

שוב, שום דבר לא ברור בתיאוריה, נעבור לדוגמא פשוטה של ​​יישום כלל הכפל. בואו ניקח את אותה כיתה של עשרים וחמישה אנשים, שבה לומדים חמש עשרה בנות ועשרה בנים. רק שהפעם אנחנו צריכים לבחור שני מלווים. הם יכולים להיות רק בנים או בנות, או ילד עם ילדה. אנו פונים לפתרון היסודי של הבעיה. אנו בוחרים את המלווה הראשון, כפי שהחלטנו בפסקה האחרונה, אנו מקבלים עשרים וחמש אפשרויות אפשריות. האדם השני בתפקיד יכול להיות כל אחד מהאנשים הנותרים. היו לנו עשרים וחמישה תלמידים, בחרנו אחד, מה שאומר שכל אחד מעשרים וארבעה האנשים הנותרים יכול להיות השני בתפקיד. לבסוף, אנו מיישמים את כלל הכפל ומגלים שניתן לבחור את שני המלווים בשש מאות דרכים. קיבלנו את המספר הזה על ידי הכפלת עשרים וחמש ועשרים וארבע.

תְמוּרָה

כעת נשקול עוד נוסחה אחת של קומבינטוריקה. בחלק זה של המאמר, נדבר על תמורות. שקול את הבעיה מיד עם דוגמה. בוא ניקח כדורי ביליארד, יש לנו מספר n'י מהם. אנחנו צריכים לחשב: כמה אפשרויות יש לסדר אותם בשורה, כלומר, לעשות סט מסודר.

נתחיל, אם אין לנו כדורים, אז יש לנו גם אפס אפשרויות מיקום. ואם יש לנו כדור אחד, אז גם הסידור זהה (מתמטית, ניתן לכתוב זאת כך: Р1 = 1). ניתן לסדר שני כדורים בשתי דרכים שונות: 1.2 ו-2.1. לכן, P2 = 2. ניתן לסדר שלושה כדורים בשש דרכים (P3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3.2.1; 3,1,2. ואם אין שלושה כדורים כאלה, אלא עשרה או חמישה עשר? לפרט את כל האפשרויות האפשריות הוא ארוך מאוד, אז קומבינטוריקה באה לעזרתנו. נוסחת התמורה תעזור לנו למצוא את התשובה לשאלתנו. Pn = n*P(n-1). אם ננסה לפשט את הנוסחה, נקבל: Pn = n* (n - 1) *...* 2 * 1. וזהו המכפלה של המספרים הטבעיים הראשונים. מספר כזה נקרא פקטוריאלי, והוא מסומן כ-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! / (נ - מ')!

קוֹמבִּינַצִיָה

שקלנו כמעט את כל הנוסחאות הבסיסיות של קומבינטוריקה עם דוגמאות. כעת נעבור לשלב האחרון של בחינת הקורס הבסיסי של קומבינטוריקה – היכרות עם השילוב. כעת נבחר m פריטים מתוך ה-n שיש לנו, בעוד שנבחר את כולם בכל הדרכים האפשריות. איך אם כן זה שונה מלינה? לא נשקול סדר. הסט הלא מסודר הזה יהיה שילוב.

אנו מציגים מיד את הסימון: C. אנו לוקחים מיקומים של m כדורים מ-n. אנחנו מפסיקים לשים לב לסדר ומקבלים שילובים חוזרים. כדי לקבל את מספר השילובים, עלינו לחלק את מספר המיקומים ב-m! (מ פקטוריאלי). כלומר, C \u003d A/m! לפיכך, יש כמה דרכים לבחור מתוך n כדורים, בערך שווה לכמה לבחור כמעט הכל. יש לכך ביטוי הגיוני: לבחור מעט זהה לזרוק כמעט הכל. חשוב גם להזכיר בשלב זה שניתן להגיע למספר המרבי של שילובים כאשר מנסים לבחור מחצית מהפריטים.

איך בוחרים נוסחה לפתרון בעיה?

בדקנו בפירוט את הנוסחאות הבסיסיות של קומבינטוריקה: מיקום, תמורה ושילוב. כעת המשימה שלנו היא להקל על הבחירה של הנוסחה הדרושה לפתרון הבעיה בקומבינטוריקה. אתה יכול להשתמש בתוכנית הפשוטה הבאה:

1. שאל את עצמך את השאלה: האם סדר האלמנטים נלקח בחשבון בטקסט המשימה?
2. אם התשובה היא לא, השתמש בנוסחת השילוב (C \u003d n! / (m! * (n - m))).
3. אם התשובה היא לא, אז צריך לענות על שאלה אחת נוספת: האם כל המרכיבים כלולים בשילוב?
4. אם התשובה היא כן, השתמש בנוסחת התמורה (P = n!).
5. אם התשובה היא לא, השתמש בנוסחת ההקצאה (A = n! / (n - m)!).

דוגמא

שקלנו אלמנטים של קומבינטוריקה, נוסחאות ועוד כמה נושאים. עכשיו בואו נעבור לבעיה האמיתית. תארו לעצמכם שיש לפניכם קיווי, תפוז ובננה.

שאלה ראשונה: בכמה דרכים ניתן לסדר אותם מחדש? לשם כך, אנו משתמשים בנוסחת התמורה: P = 3! = 6 דרכים.

שאלה 2: בכמה דרכים אפשר לבחור פרי אחד? זה ברור, יש לנו רק שלוש אפשרויות - בחר קיווי, תפוז או בננה, אבל אנו מיישמים את נוסחת השילוב: C \u003d 3! / (2! * 1!) = 3.

שאלה 3: בכמה דרכים אפשר לבחור שני פירות? אילו אפשרויות עומדות בפנינו? קיווי ותפוז; קיווי ובננה; תפוז ובננה. כלומר, שלוש אפשרויות, אבל זה קל לבדוק באמצעות נוסחת השילוב: C \u003d 3! / (1! * 2!) = 3

שאלה 4: בכמה דרכים אפשר לבחור שלושה פירות? כפי שאתה יכול לראות, יש רק דרך אחת לבחור שלושה פירות: לקחת קיווי, תפוז ובננה. C=3! / (0! * 3!) = 1.

שאלה 5: בכמה דרכים אפשר לבחור לפחות פרי אחד? מצב זה מרמז שאנו יכולים לקחת אחד, שניים או את כל שלושת הפירות. לכן, נוסיף C1 + C2 + C3 = 3 + 3 + 1 = 7. כלומר, יש לנו שבע דרכים לקחת לפחות חתיכת פרי אחת מהשולחן.

תקציר על הנושא:

הושלם על ידי תלמיד מכיתה י' ב'

בית ספר תיכון מס' 53

גלוכוב מיכאיל אלכסנדרוביץ'

נברז'ניה צ'לני

2002
תוֹכֶן

מההיסטוריה של קומבינטוריקה __________________________________________________________	3
כלל סכום _________________________________________________	4
	-
חוק מוצר _____________________________________________	4
דוגמאות למשימות __________________________________________________________	-
קבוצות מצטלבות ____________________________________________	5
דוגמאות למשימות __________________________________________________________	-
מעגלי אוילר __________________________________________________	-
מיקומים ללא חזרות _______________________________________________________	6
דוגמאות למשימות __________________________________________________________	-
תמורות ללא חזרות __________________________________	7
דוגמאות למשימות __________________________________________________________	-
שילובים ללא חזרות __________________________________________	8
דוגמאות למשימות __________________________________________________________	-
מיקומים ושילובים ללא חזרה ______________________________	9
דוגמאות למשימות __________________________________________________________	-
תמורות עם חזרות	9
דוגמאות למשימות __________________________________________________________	-
משימות לפתרון עצמאי ________________________________	10
בִּיבּלִיוֹגְרָפִיָה___________________________________	11

מההיסטוריה של הקומבינטוריקה

קומבינטוריקה עוסקת בסוגים שונים של תרכובות שיכולות להיווצר מיסודות של קבוצה סופית. כמה אלמנטים של קומבינטוריקה היו ידועים בהודו כבר במאה ה-2 לפני הספירה. לִפנֵי הַסְפִירָה ה. הנידים הצליחו לחשב מספרים, אשר נקראים כיום "צירופים". במאה ה- XII. בהסקרה חישב כמה סוגים של שילובים ותמורות. ההנחה היא שמדענים הודים חקרו תרכובות בקשר עם השימוש בהן בפואטיקה, מדע מבנה הפסוק ויצירות פיוטיות. למשל, בקשר לחישוב שילובים אפשריים של הברות מודגשות (ארוכות) ולא מודגשות (קצרות) ברגל של n הברות. כדיסציפלינה מדעית, הקומבינטוריקה נוצרה במאה ה-17. בספר "תיאוריה ופרקטיקה של אריתמטיקה" (1656) מקדיש הסופר הצרפתי א' פרק שלם לצירופים ותמורות.
ב' פסקל ב"מסכת על המשולש האריתמטי" וב"מסכת על סדרים מספריים" (1665) פרש את תורת המקדמים הבינומיים. פ. פרמה ידע על הקשרים בין ריבועים מתמטיים למספרים פיגורטיביים עם תורת התרכובות. המונח "קומבינטוריקה" החל לשמש לאחר פרסום היצירה "שיח על אמנות קומבינטורית" על ידי לייבניץ ב-1665, שבה ניתנה לראשונה ביסוס מדעי של תורת הצירופים והתמורות. ג'יי ברנולי היה הראשון שלמד מיקומים בחלק השני של ספרו "Ars conjectandi" (אמנות החיזוי) בשנת 1713. הסמליות המודרנית של שילובים הוצעה על ידי מחברים שונים של מדריכים חינוכיים רק במאה ה-19.

ניתן לגזור את כל מגוון הנוסחאות הקומבינטוריות משתי הצהרות בסיסיות הנוגעות לקבוצות סופיות - כלל הסכום וכלל המכפלה.

כלל סכום

אם הקבוצות הסופיות אינן מצטלבות, אזי מספר האלמנטים X U Y (או) שווה לסכום מספר היסודות של קבוצת X ומספר האלמנטים של קבוצת Y.

כלומר, אם יש X ספרים על המדף הראשון, ו-Y על השני, אז אתה יכול לבחור ספר מהמדף הראשון או השני בדרכי X + Y.

דוגמאות למשימות

על התלמיד להשלים עבודה מעשית במתמטיקה. הוצעה לו בחירה בין 17 נושאים באלגברה ו-13 נושאים בגיאומטריה. בכמה דרכים הוא יכול לבחור נושא אחד לעבודה מעשית?

פתרון: X=17, Y=13

לפי כלל הסכום X U Y=17+13=30 נושאים.

ישנם 5 כרטיסי לוטו במזומן וביגוד, 6 כרטיסי לוטו ספורט ו-10 כרטיסי הגרלה לרכב. בכמה דרכים ניתן לבחור כרטיס אחד מהגרלת ספורט או הגרלת רכב?

פתרון: מכיוון שהגרלת הכסף והבגדים לא משתתפת בבחירה, יש רק 6 + 10 = 16 אפשרויות.

חוק מוצר

אם ניתן לבחור אלמנט X ב-k דרכים, ואלמנט Y ב-m דרכים, אז ניתן לבחור את הזוג (X,Y) ב-k*m דרכים.

כלומר, אם יש 5 ספרים על המדף הראשון ו-10 על השני, אז אתה יכול לבחור ספר אחד מהמדף הראשון ואחד מהשני ב-5*10 = 50 דרכים.

דוגמאות למשימות

על הקלסר לאגד 12 ספרים שונים בכריכות אדום, ירוק וחומה. בכמה דרכים הוא יכול לעשות זאת?

פתרון: ישנם 12 ספרים ו-3 צבעים, כך שלפי כלל המוצר, אפשריות 12*3 = 36 אפשרויות כריכה.

כמה מספרים בני חמש ספרות יש שקוראים אותו דבר משמאל לימין ומימין לשמאל?

פתרון: במספרים כאלה, הספרה האחרונה תהיה זהה לראשונה, והלפני אחרונה - כמו השנייה. הספרה השלישית תהיה כל אחת. זה יכול להיות מיוצג בתור XYZYX, כאשר Y ו-Z הם כל ספרות ו-X אינו אפס. אז, על פי כלל המוצר, מספר הספרות הנקראות באופן שווה הן משמאל לימין ומימין לשמאל הוא 9 * 10 * 10 = 900 אפשרויות.

סטים חופפים

אבל קורה שהקבוצות X ו-Y מצטלבות, ואז הם משתמשים בנוסחה

, כאשר X ו-Y הם קבוצות, והוא אזור החיתוך. דוגמאות למשימות

20 אנשים יודעים אנגלית ו-10 - גרמנית, 5 מהם יודעים אנגלית וגרמנית. כמה אנשים בסך הכל?

תשובה: 10+20-5=25 איש.

עיגולי אוילר משמשים לעתים קרובות גם כדי לפתור את הבעיה באופן ויזואלי. לדוגמה:

מתוך 100 תיירים שיוצאים לטיול בחו"ל, 30 אנשים דוברים גרמנית, 28 - אנגלית, 42 - צרפתית. 8 אנשים מדברים אנגלית וגרמנית בו זמנית, 10 אנשים מדברים אנגלית וצרפתית, 5 גרמנית וצרפתית, 3 כל שלוש השפות תיירים לא מדברים שום שפה?

פִּתָרוֹן:הבה נבטא את מצב הבעיה בצורה גרפית. תנו לנו לייעד מעגל למי שיודע אנגלית, מעגל נוסף למי שיודע צרפתית ומעגל שלישי למי שיודע גרמנית.

שלושה תיירים דוברים את כל שלוש השפות, מה שאומר שבחלק המשותף של המעגלים אנחנו מכניסים את המספר 3. 10 אנשים מדברים אנגלית וצרפתית, ו-3 מהם מדברים גם גרמנית. לכן, רק אנגלית וצרפתית מדברים על ידי 10-3=7 אנשים.

באופן דומה, אנו מבינים שרק אנגלית וגרמנית דוברים על ידי 8-3=5 אנשים, וגרמנית וצרפתית על ידי 5-3=2 תיירים. אנו מכניסים נתונים אלה בחלקים הרלוונטיים.

הבה נחליט כעת כמה אנשים דוברים רק אחת מהשפות המפורטות. 30 אנשים יודעים גרמנית, אבל 5+3+2=10 מהם דוברים גם שפות אחרות, כך שרק 20 אנשים יודעים גרמנית. באופן דומה, אנו מבינים ש-13 אנשים מדברים אנגלית אחת, ו-30 אנשים מדברים צרפתית אחת.

לפי מצב התקלה יש רק 100 תיירים. 20 + 13 + 30 + 5 + 7 + 2 + 3 = 80 תיירים יודעים לפחות שפה אחת, לכן, 20 אנשים אינם דוברים אף אחת מהשפות הללו.

מיקומים ללא חזרה.

כמה מספרי טלפון יכולים להיות מורכבים מ-6 ספרות כל אחד כך שכל הספרות יהיו ברורות?

זוהי דוגמה לבעיית מיקום ללא חזרות. כאן ממוקמות 10 ספרות של 6. ואפשרויות שבהן אותם מספרים בסדר שונה נחשבות שונות.

אם קבוצת X המורכבת מ- n אלמנטים, m≤n, אז קבוצה מסודרת X המכילה m אלמנטים נקראת קבוצה סדורה X המכילה m אלמנטים.

המספר של כל הסידורים של n אלמנטים ב-m מסומן ב

n! - n-factorial (גורם באנגלית פקטוריאלי) המכפלה של מספרים טבעיים מ-1 למספר n כלשהו

n!=1*2*3*...*n 0!=1

אז התשובה לבעיה לעיל היא

משימה

בכמה דרכים 4 בנים יכולים לבקש מ-4 מתוך 6 בנות לרקוד?

פִּתָרוֹן: שני בנים לא יכולים להזמין את אותה בחורה בו זמנית. והאפשרויות שבהן אותן בנות רוקדות עם בנים שונים נחשבות שונות, לכן:

360 אפשרויות אפשריות.

תמורות ללא חזרה

במקרה של n=m (ראה מיקומים ללא חזרות) של n אלמנטים לפי m נקרא תמורה של קבוצת x.

מספר כל התמורות של n אלמנטים מסומן ב-P n.

תקף עבור n=m:

דוגמאות למשימות

כמה מספרים שונים בני שש ספרות אפשר ליצור מהספרות 0, 1, 2, 3, 4.5 אם המספרים אינם חוזרים במספר?

1) מצא את מספר כל התמורות של המספרים הללו: P 6 =6!=720

2) 0 לא יכול להיות מול המספר, ולכן ממספר זה יש צורך להחסיר את מספר התמורות בהן 0 נמצא מקדימה. וזהו P 5 =5!=120.

P 6 -P 5 \u003d 720-120 \u003d 600

קוף שובב

כן, מישקה

התחיל לנגן רביעייה

עצרו, אחים, עצרו! -

קוף צועק, - רגע!

איך המוזיקה מתנהלת?

אתה לא יושב ככה...

וכך, וכך מושתל - שוב המוזיקה לא הולכת טוב.