ה שילוב פשוט היא אחת הקבוצות שנלמדו ב ניתוח קומבינטורי. אנו יודעים כשילוב את ספירת כל קבוצות המשנה של k אלמנטים שאנחנו יכולים ליצור מתוך קבוצה של לא אלמנטים.
די מקובל לראות מצבים שבהם אנו משתמשים בשילוב, למשל, לחישוב כל התוצאות אפשרי במשחקי לוטו או במשחקי פוקר, ובמצבים אחרים, כמו למשל בחקר ההסתברות ו סטטיסטיקה.
קיבוץ נוסף נפוץ מאוד הוא ההסדר. מה שמבדיל בין סידור לשילוב הוא העובדה שבסידור סדר היסודות חשוב, ובשילוב הסדר אינו חשוב. לכן, אנו משווים את השילוב עם בחירת קבוצות המשנה.
קרא גם: עקרון יסוד של ספירה - משמש לכימות האפשרויות
מהו שילוב פשוט?
בניתוח קומבינטורי נלמד מספר האשכולות האפשריים. בין הקבוצות הללו יש מה שמכונה שילוב פשוט. השילוב הפשוט הוא לא יותר מ- ספירת כל קבוצות המשנה עם k אלמנטים של סט נתון, לדוגמא: המגאסנה, בה נמשכים 6 מספרים באופן אקראי.
במקרה זה, אתה יכול לראות שהסדר בו נבחרו 6 המספרים הללו אינו משנה, כלומר הסדר לא משנה, מה שהופך את התוצאה הזו לקבוצת משנה. מאפיין זה הוא מהותי כדי להבין מהו שילוב ולהבדיל אותו מהקבוצות האחרות - בשילוב אין חשיבות לסדר האלמנטים של הסט.
אל תפסיק עכשיו... יש עוד אחרי הפרסום;)
נוסחת שילוב פשוטה
בעיות הכרוכות בשילוב מחושבות על ידי נוסחה. השילוב של לא אלמנטים שנלקחו מ k ב k é:
n → סך האלמנטים בסט
k → סך האלמנטים בקבוצת משנה
ראה גם: עקרון ספירת תוספים - איחוד של אלמנטים של שתי קבוצות או יותר
איך מחשבים שילוב?
במקום הראשון, חשוב לדעת מתי בעיה היא שילוב. לשם המחשה, מצא את כל השילובים האפשריים של מַעֲרֶכֶת {A, B, C, D} עם שני אלמנטים:
רישומי שילובים עם שני אלמנטים, הם: {A, B}, {A, C}, {A, D}, {B, C}, {B, D} ו- {C, D}. במקרה זה ניתן לראות כי ישנם 6 צירופים אפשריים, וכדאי גם לציין כי קבוצות המשנה {A, B} ו- {B, A} שוות, מכיוון שבשילוב הסדר אינו חשוב .
מתברר שלא תמיד ניתן לרשום את כל השילובים האפשריים או אפילו שזה לא הכרחי, כמו העניין הגדול ביותר הוא במספר הצירופים ולא ברשימה של כל אחד מהם. לשם כך, זה מאוד מעשי להשתמש בנוסחה.
דוגמא:
בית ספר ישוך שלושה כרטיסים, אחד לכל תלמיד, בין 10 הראשונים באולימפיאדת המתמטיקה. לאחר סיום המבחן והכרת 10 המקומות הראשונים, חישב את השילובים האפשריים לתוצאת הגרלה.
שים לב כי בתוצאת הגרלה הסדר אינו חשוב ולכן אנו עובדים עם בעיית שילוב.
לאחר מכן נחשב את השילוב של 10 אלמנטים שנלקחו מ -3 מתוך 3. החלפת הנוסחה, עלינו:
עכשיו בואו לבצע את הפשטות של המפעלים. בשלב זה, חיוני לשלוט בחישוב ה- מפעל של מספר. כמו 10! גדול יותר מכל אחד מהמפעלים במכנה, וכאשר מסתכלים על המכנה, 7! הוא הגדול שבהם, בואו נעשה את הכפל של 10 על ידי קודמיו עד להגיע ל -7!, כך שיהיה אפשר לפשט.
המשולש של פסקל
אחד המכשירים הנמצאים בשימוש נרחב בניתוח קומבינטורי, בעיקר לצורך חישוב a הבינום של ניוטון, הוא המשולש של פסקל. המשולש הזה הוא בנוי מתוצאות השילובים, דרך נוספת לייצג את השילוב של שני מספרים היא כדלקמן:
המשולש של פסקל מתחיל בשורה 0 ובעמודה 0, על ידי שילוב 0 אלמנטים שנלקחו מ -0 ל -0. הקווים זהים ל- לא, והעמודים שווים ל- k, המרכיב את הדמות הבאה:
החלפת הערכים הנובעים מהצירופים:
דרך השורות והעמודות של המשולש של פסקל, ניתן למצוא את ערך השילוב הרצוי לנו. במידת הצורך נוכל למצוא את המונחים של כמה שורות לפי הצורך. למידע נוסף על שיטת רזולוציה זו, קרא את הטקסט: המשולש של פסקל.
ההבדל בין סידור לשילוב
סידור ושילוב הם שתי קבוצות לא פחות חשובות שנחקרו בניתוח קומבינטורי. חיוני לדעת מה ההבדל בין כל אחת מהקבוצות הללו, כלומר אם אנחנו הולכים לחשב אותן על ידי a סידור או אחד קוֹמבִּינַצִיָה.
מתברר כי ב קוֹמבִּינַצִיָה, בעת הרכבת האשכולות, סדר האלמנטים של הסט אינו חשוב., כלומר {A, B} = {B, A}, אך ישנם מקרים בהם הסדר חשוב בקיבוץ, במקרה זה אנו עובדים עם מערך.
ב הֶסדֵר, לאחר מכן, סדר היסודות שונהכלומר, {A, B} ≠ {B, A}, דוגמה להסדר נפוץ מאוד יהיה לחשב כמה דרכים שונות אנו יכולים ליצור בימה של תחרות נתונה בין 10 אנשים. שים לב שבדוגמא זו סדר חשוב, מה שהופך אותו לפתור על ידי נוסחת הסידור. בנוסף להגדרה התיאורטית, הנוסחאות שונות, וה- נוסחת סידור é:
תרגילים נפתרו
שאלה 1 - (אויב) 12 קבוצות נרשמו לטורניר כדורגל חובבים. משחק פתיחת הטורניר נבחר באופן הבא: ראשית הוגרלו 4 קבוצות המרכיבות את הקבוצה א '. ואז, בין הקבוצות בקבוצה A, הוגרלו 2 קבוצות למשחק הפתיחה של הטורניר, הראשונה בה תשחק בשדה שלהן, והשנייה תהיה הקבוצה האורחת. ניתן לחשב את מספר הבחירות האפשרי עבור קבוצה A ואת מספר הבחירות של הקבוצות במשחק הפתיחה
א) שילוב וסידור, בהתאמה.
ב) סידור ושילוב, בהתאמה.
ג) הסדר ותמורה, בהתאמה.
ד) שני שילובים.
ה) שני סידורים.
פתרון הבעיה
חלופה א
כדי להבדיל בין סידור ושילוב, יש צורך לנתח אם סדר חשוב בקיבוץ או לא. שים לב, בקיבוץ הראשון, הסדר אינו רלוונטי, מכיוון שקבוצה A נוצרת על ידי 4 הצוותים הנמשכים ללא תלות בסדר, כלומר יש, ראשית, שילוב.
בניתוח הקיבוץ השני, ניתן לראות שהסדר חשוב בו, מכיוון שהצוות הראשון שיוגרל יקבל את הפקודה בשטח, מה שהופך את הקיבוץ הזה לסדר.
באופן זה, הצו הוא שילוב והסדר.
שאלה 2 - משפחה המורכבת משבעה מבוגרים, לאחר שהחליטה על מסלול הנסיעה, התייעצה באתר חברת תעופה ומצאה כי הטיסה לתאריך הנבחר כמעט מלאה. באיור, הזמין באתר, המושבים הכבושים מסומנים ב- X והמושבים היחידים הזמינים הם בצבע לבן.
מספר הדרכים השונות לאירוח המשפחה בטיסה זו מחושב על ידי:
פתרון הבעיה
חלופה B. בניתוח המצב, שים לב שהסדר, כלומר איזה בן משפחה יישב באיזה כסא, אינו רלוונטי. מה שחשוב הם 7 הכורסאות שנבחרו על ידי המשפחה. אז אנחנו עובדים עם שילוב. ישנם 9 מושבים פנויים, ו -7 ייבחרו. אז בואו נחשב את השילוב בין 9 ל -7. החלפת הנוסחה, עלינו:
מאת ראול רודריגס דה אוליביירה
מורה למתמטיקה
