תקציר מבוא לקומבינטוריקה, סמסטר א תשע״ג
מתוך Math-Wiki
בתקציר זה, אלא אם צוין אחרת, כל המשתנים והנעלמים שלמים ואי־שליליים למעט . ראשוני ו־ אינו שלם או אי־שלילי רק במקרים בהם הוא מוצג כמשתנה בפולינום. שדה.
- נסמן . היא קבוצת כל התמורות על .
- חלוקת קבוצות של ל־ היא בחירה של תתי־קבוצות זרות עבורן .
- סדרת פיבונצ׳י תסומן והיא מקיימת .
- ריצוף דומינו של הוא כיסוי של על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־.
- ללוח בגודל קיים ריצוף דומינו אם״ם זוגי.
- ללוח בגודל קיימים ריצופי דומינו.
- עקרון שובך יונים: בחלוקה של קבוצה סופית ל־ יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות .
- סימונים: . לכן . בנוסף, ו־.
- חליפה: נניח . חליפה של איברים מתוך היא ־יה סדורה של איברים שונים מקבוצה בת איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא .
- תמורה היא חליפה של מתוך , ומספר התמורות הוא .
- חליפה עם חזרות היא ־יה סדורה של איברים (לא דווקא שונים) מתוך . יש חליפות עם חזרות.
- צירוף: נניח . צירוף של איברים מתוך הוא תת־קבוצה של קבוצה בת איברים (כלומר, צירוף הוא בחירה ללא חזרות ובלי חשיבות לסדר). מספר הצירופים הוא .
- צירוף עם חזרות: הוא רב־קבוצה מסדר של איברים מתוך קבוצה בת איברים. יש צירופים עם חזרות.
- מספר הצירופים עם חזרות של מתוך שווה למספר הדרכים לבחור עצמים מתוך סוגים, ששווה למספר הפתרונות השלמים ואי־שליליים ל־.
- הווקטור האופייני של קבוצה מוגדר ע״י .
- סדרה אונימוצלית היא סדרה כך שקיים עבורו עולה במובן הרחב ו־ יורדת במובן הרחב.
- היא סדרה אונימוצלית כאשר אם זוגי אז ואחרת (כי ).
- הפרת סדר בתמורה היא זוג כך ש־. מספר הפרות הסדר מסומן וסימן התמורה מוגדר כ־. התמרה תקרא זוגית אם ואי־זוגית אחרת. יש התמרות מכל סוג שסדרן .
- מורד: עבור נקרא ל־ מורָד (descent) אם . קבוצת המורדות תסומן .
- .
- אם אז .
- יהי פולינום . נסמן .
- .
- משפט פרמה הקטן: .
- פיתוח של מספר לפי ראשוני: נניח ו־. אזי קיימים שלמים כך ש־ ו־. סכום זה נקרא "הפיתוח של לפי ".
- אם אז . לפיכך, .
- משפט לוקאס: נניח ש־ ו־ פיתוחים לפי . אזי .
- אם״ם בפיתוחים יש עבורו .
- פירוק/קומפוזיציה של הוא הצגה של כסכום של טבעיים.
- יש פירוקים של (כאשר יש חשיבות לסדר ( שונה מ־) וחזרות מותרות ( ייספר כפירוק של 3)).
- מקדם מולטינומי: מספר המילים מאורך שבהן המספר מופיע פעמים () הוא .
- סימונים: . כמו כן, ו־. ניתן להראות ש־ שלם.
- ו־.
- אם זוגי אז אי־זוגי.
- מספר התתי־מרחבים ממימד של מרחב וקטורי (כאשר ל־ יש איברים) הוא .
- אם אז , כלומר זה פולינום במשתנה שמקדמיו שלמים ואי־שליליים. למעשה, הוא גם מתוקן, דרגתו והוא סימטרי (כלומר המקדם של שווה למקדם של לכל ).
- הילוך שריג הוא סדרת צעדים בין נקודות ב־ שכל אחד מהם הוא הוספת 1 לאחת מהקואורדינטות של הנקודה בה נמצאים.
- יש הילוכי שריג מ־ ל־.
- נסמן כמספר הילוכי השריג מ־ ל־ שהשטח המוגבל על־ידם, ציר ה־x והישר הוא . בנוסף, נגדיר . אזי .
- נסמן . אזי .
- יהי וקטור שרכיביו אפסים ואחדות. אם ו־ נכנה זאת הפרת סדר. אם נסמן אז .
- חלוקה של היא וקטור שסכום רכיביו הוא (כלומר ) והם מסודרים בסדר יורד במובן הרחב. מספר החלוקות מסומן .
- מספר החלוקות של עם לכל היותר רכיבים הוא המקדם של בפולינום , כלומר .
- דיאגרמת יאנג של חלוקה היא דיאגרמת משבצות כך שבשורה ה־ יש משבצות המיושרות לשמאל.
- טבלת יאנג היא התאמה חח״ע ממשבצות של דיאגרמת יאנג נתונה (שנוצרת מחלוקה של ) על כך שהמספרים עולים לאורך השורות העמודות.
- היא מספר טבלאות יאנג שקיימות לדיאגרמת יאנג הנוצרת מהחלוקה .
- .
- נוסחת הווים: תהי ונרצה לחשב את . לכל משבצת בדיאגרמת יאנג נתאים "אורך וו" (hook length) כמספר המשבצות באותה שורה או עמודה שאחרי המשבצת הנתונה ועוד 1. נסמן כמכפלת אורכי הווים של כל המשבצות. אזי .
- הילוכי דיק הם הילוכי שריג מ־ ל־ שנמצאים על ומעל הישר .
- מספר קטלן הוא מספר הילוכי דיק ל־, מסומן ושווה ל־.
- נניח ש־. יש הילוכי דיק ל־ שאינם עוברים על הישר למעט בנקודה .
- מילת דיק מאורך היא סדרה כך ש־, ו־. יש מילות דיק מאורך .
- עץ בינארי שלם/מלא הוא עץ כך שלכל אב יש בדיוק 2 בנים, כלומר לכל קודקוד שאינו עלה יש דרגה 3 למעט קודקוד אחד, שנקרא שורש. אם מבדילים בין הבן הימני לבן השמאלי אז יש עצים בינארים מלאים עם עלים.
- בהינתן מכפלה לא אסוציאטיבית יש דרכים להוסיף סוגריים.
- שילוש של מצולע משוכלל בעל קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש דרכים לשלש מצולע משוכלל בעל צלעות.
- מספר בל הוא מספר חלוקות הקבוצה ומסומן .
- מספר סטירלינג הלא מסומן מסוג I הוא מספר התמורות על עם מחזורים ומסומן .
- .
- .
- מספר סטירלינג מסוג I הוא .
- יהי . נסמן בתור המטריצה שהרכיב בשורה ה־ ובעמודה ה־ שלה הוא .
- .
- מספר סטירלינג מסוג II הוא מספר חלוקות הקבוצה ל־ תתי־קבוצות לא ריקות ומסומן .
- .
- יהי . נסמן בתור המטריצה שהרכיב בשורה ה־ ובעמודה ה־ שלה הוא .
- .
- .
פונקציות יוצרות
- טור חזקות פורמלי במשתנה מכל (בד״כ ) הוא ביטוי מהצורה כאשר . הטור לא חייב להתכנס. אוסף טורי החזקות הפורמליים ב־ מעל מסומן .
- אם אז הטור הוא פולינום. אוסף הפולינומים ב־ מעל מסומן .
- נוסחת טיילור: אם אז .
- פונקציה יוצרת: לכל סדרה נתאים פונקציה .
- פונקציה יוצרת מעריכית: לכל סדרה נתאים פונקציה . פונקציות אלה שימושיות לספירת עצמים עבורם הסדר משנה.
- נרצה לחשב את . נגדיר ו־ ולכן .
- נרצה למצוא את מספר הפתרונות של כאשר . נתאים לכל משתנה פונקציה יוצרת ולכן מספר הפתרונות הדרוש הוא המקדם של ב־.
- נרצה למצוא כמה דרכים יש לחלק כדורים שונים בין תאים כאשר בתא ה־ חייב להיות מספר כדורים השייך לקבוצה וסדר השמת הכדורים משנה. נתאים לכל תא פונקציה ולכן המספר הדרוש הוא המקדם של ב־.
- אם משתנה מקרי כש־ ו־ אז , התוחלת היא והשונות היא .
נוסחאות נסיגה
- נוסחת נסיגה מסדר היא נוסחה מהצורה .
- איברי סדרה המקיימת נוסחת נסיגה כזו נקבעים ע״י האיברים הראשונים, והם נקראים תנאי ההתחלה.
- נוסחת נסיגה לינארית מסדר היא נוסחה מהצורה . אם פונקציות קבועות אז נאמר שהנוסחה עם מקדמים קבועים. אם אז נאמר שהיא הומוגנית.
- קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר היא מרחב וקטורי ממימד .
- נרצה לחשב את אברי בהינתן תנאי ההתחלה ונוסחת נסיגה . נעזר בפונקציה היוצרת ואם קיימת פונקציה עבורה אז נבודד את ונקבל נוסחה מפורשת למקדמים של .
- תהי נוסחת נסיגה לינארית הומוגנית מסדר . נניח שיש עבורו (לא תמיד זה נכון). אזי פתרון. נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם אז הוא שווה ל־0 בנקודה . יש לו שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם אז . המרחב הווקטורי של הפתרונות הוא אם כן . אם נתונים תנאי ההתחלה ניתן גם לחשב את ה־־ים.
נוסחאות
- נוסחת הנסיגה של פסקל:
- זהות הקפטן:
- הבינום של ניוטון:
- אם אז
- אם אז
- נוסחת המולטינום:
- נוסחת q־פסקל:
- q־בינום:
- נוסחת נסיגה למספרי קטלן: ו־
- נוסחת נסיגה למספרי בל: ו־
- נוסחת נסיגה למספרי סטירלינג לא מסומנים מסוג I: ו־
- נוסחת נסיגה למספרי סטירלינג מסוג I:
- נוסחת נסיגה למספרי סטירלינג מסוג II: ו־