הבדלים בין גרסאות בדף "תקציר מבוא לקומבינטוריקה, סמסטר א תשע״ג"
מתוך Math-Wiki
מ (המשך יבוא) |
מ (המשך יבוא) |
||
שורה 53: | שורה 53: | ||
:* '''שילוש של מצולע משוכלל''' בעל <math>n</math> קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו <math>n-3</math> אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש <math>C_n</math> דרכים לשלש מצולע משוכלל בעל <math>n+2</math> צלעות. | :* '''שילוש של מצולע משוכלל''' בעל <math>n</math> קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו <math>n-3</math> אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש <math>C_n</math> דרכים לשלש מצולע משוכלל בעל <math>n+2</math> צלעות. | ||
* '''מספר בל''' הוא מספר חלוקות הקבוצות של <math>[n]</math> ומסומן <math>B_n</math>. | * '''מספר בל''' הוא מספר חלוקות הקבוצות של <math>[n]</math> ומסומן <math>B_n</math>. | ||
− | * '''מספר | + | * '''מספר סטירלינג מסוג II''' הוא מספר חלוקות הקבוצות של <math>[n]</math> ל־<math>k</math> תתי־קבוצות לא ריקות ומסומן <math>S(n,k)</math>. |
:* <math>B_n=\sum_{k=1}^n S(n,k)</math>. | :* <math>B_n=\sum_{k=1}^n S(n,k)</math>. | ||
:* יהי <math>N\in\mathbb N</math>. נסמן <math>S_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>S(n,k)</math>. | :* יהי <math>N\in\mathbb N</math>. נסמן <math>S_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>S(n,k)</math>. | ||
:* <math>\sum_{k=1}^n S(n,k)(x)_k=x^n</math>. | :* <math>\sum_{k=1}^n S(n,k)(x)_k=x^n</math>. | ||
− | * '''מספר | + | * '''מספר סטירלינג הלא מסומן מסוג I''' הוא מספר התמורות על <math>[n]</math> עם <math>k</math> מחזורים ומסומן <math>C(n,k)</math>. |
:* <math>n!=\sum_{k=1}^n C(n,k)</math>. | :* <math>n!=\sum_{k=1}^n C(n,k)</math>. | ||
:* <math>C(n,n)=1\ \and\ C(n,1)=(n-1)!</math>. | :* <math>C(n,n)=1\ \and\ C(n,1)=(n-1)!</math>. | ||
− | * '''מספר | + | * '''מספר סטירלינג מסוג I''' הוא <math>s(n,k):=(-1)^{n-k}C(n,k)</math>. |
:* יהי <math>N\in\mathbb N</math>. נסמן <math>s_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>s(n,k)</math>. | :* יהי <math>N\in\mathbb N</math>. נסמן <math>s_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>s(n,k)</math>. | ||
:* <math>\sum_{k=1}^n s(n,k)x^k=(x)_n</math>. | :* <math>\sum_{k=1}^n s(n,k)x^k=(x)_n</math>. | ||
שורה 98: | שורה 98: | ||
* '''נוסחת נסיגה למספרי קטלן:''' <math>\forall n>1:\ C_n=\sum_{i=1}^{n-1}C_i C_{n-i}</math> ו־<math>C_0=C_1=1</math> | * '''נוסחת נסיגה למספרי קטלן:''' <math>\forall n>1:\ C_n=\sum_{i=1}^{n-1}C_i C_{n-i}</math> ו־<math>C_0=C_1=1</math> | ||
* '''נוסחת נסיגה למספרי בל:''' <math>\forall n>0:\ \sum_{k=1}^n\binom{n-1}{k-1}B_{n-k}</math> ו־<math>B_0=1</math> | * '''נוסחת נסיגה למספרי בל:''' <math>\forall n>0:\ \sum_{k=1}^n\binom{n-1}{k-1}B_{n-k}</math> ו־<math>B_0=1</math> | ||
− | * '''נוסחת נסיגה למספרי | + | * '''נוסחת נסיגה למספרי סטירלינג מסוג II:''' <math>\forall n\in\mathbb N,k\in[n]:\ S(n,k)=S(n-1,k-1)+k S(n-1,k)</math> ו־<math>S(0,0)=1\ \and\ \forall n<k:\ s(n,k)=0\ \and\ \forall n>0:\ S(n,0)=0</math> |
− | * '''נוסחת נסיגה למספרי | + | * '''נוסחת נסיגה למספרי סטירלינג לא מסומנים מסוג I:''' <math>\forall n\in\mathbb N,k\in[n]:\ C(n,k)=C(n-1,k-1)+(n-1)C(n-1,k)</math> ו־<math>C(0,0)=1\ \and\ \forall n<k:\ C(n,k)=0\ \and\ \forall n>0:\ C(n,0)=0</math> |
− | * '''נוסחת נסיגה למספרי | + | * '''נוסחת נסיגה למספרי סטירלינג מסוג I:''' <math>\forall n\in\mathbb N,k\in[n]:\ s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)</math> |
* <math>\binom{-1/2}n=\left(\frac{-1}4\right)^n\binom{2n}n</math> | * <math>\binom{-1/2}n=\left(\frac{-1}4\right)^n\binom{2n}n</math> | ||
* <math>\forall n\in\mathbb N:\ \binom{1/2}n=\frac{C_{n-1}}2\left(\frac{-1}4\right)^{n-1}</math> | * <math>\forall n\in\mathbb N:\ \binom{1/2}n=\frac{C_{n-1}}2\left(\frac{-1}4\right)^{n-1}</math> | ||
* <math>\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty\frac1{1-x^n}</math> | * <math>\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty\frac1{1-x^n}</math> |
גרסה מ־23:17, 2 בפברואר 2013
בתקציר זה, אלא אם צוין אחרת, כל המשתנים והנעלמים שלמים ואי־שליליים למעט .
ראשוני ו־
אינו שלם או אי־שלילי רק במקרים בהם הוא מוצג כמשתנה בפולינום.
שדה.
- נסמן
.
היא קבוצת כל התמורות על
.
- חלוקת קבוצות של
ל־
היא בחירה של תתי־קבוצות
זרות עבורן
.
- סדרת פיבונצ׳י תסומן
.
- ריצוף דומינו של
הוא כיסוי של
על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־
.
- ללוח בגודל
קיים ריצוף דומינו אם״ם
זוגי.
- ללוח בגודל
קיימים
ריצופי דומינו.
- ללוח בגודל
- עקרון שובך יונים: בחלוקה של קבוצה סופית
ל־
יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות
.
- סימונים:
. לכן
. בנוסף,
ו־
.
- חליפה: נניח
. חליפה של
איברים מתוך
היא
־יה סדורה של איברים שונים מקבוצה בת
איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא
.
- תמורה היא חליפה של
מתוך
, ומספר התמורות הוא
.
- חליפה עם חזרות היא
־יה סדורה של
איברים (לא דווקא שונים) מתוך
. יש
חליפות עם חזרות.
- תמורה היא חליפה של
- צירוף: נניח
. צירוף של
איברים מתוך
הוא תת־קבוצה של קבוצה בת
איברים (כלומר, צירוף הוא בחירה ללא חזרות ובלי חשיבות לסדר). מספר הצירופים הוא
.
- צירוף עם חזרות: הוא רב־קבוצה מסדר
של איברים מתוך קבוצה בת
איברים. יש
צירופים עם חזרות.
- מספר הצירופים עם חזרות של
מתוך
שווה למספר הדרכים לבחור
עצמים מתוך
סוגים, ששווה למספר הפתרונות השלמים ואי־שליליים ל־
.
- מספר הצירופים עם חזרות של
- צירוף עם חזרות: הוא רב־קבוצה מסדר
- הווקטור האופייני של קבוצה
מוגדר ע״י
.
- סדרה אונימוצלית היא סדרה
כך שקיים
עבורו
עולה במובן הרחב ו־
יורדת במובן הרחב.
-
היא סדרה אונימוצלית כאשר אם
זוגי אז
ואחרת
(כי
).
-
- הפרת סדר בתמורה
היא זוג
כך ש־
. מספר הפרות הסדר מסומן
וסימן התמורה מוגדר כ־
. התמרה
תקרא זוגית אם
ואי־זוגית אחרת. יש
התמרות מכל סוג שסדרן
.
- מורד: עבור
נקרא ל־
מורָד (descent) אם
. קבוצת המורדות תסומן
.
-
.
-
- אם
אז
.
- יהי פולינום
. נסמן
.
-
.
- משפט פרמה הקטן:
.
- פיתוח של מספר לפי ראשוני: נניח
ו־
. אזי קיימים
שלמים כך ש־
ו־
. סכום זה נקרא "הפיתוח של
לפי
".
- אם
אז
. לפיכך,
.
- משפט לוקאס: נניח ש־
ו־
פיתוחים לפי
. אזי
.
-
אם״ם בפיתוחים
יש
עבורו
.
- פירוק/קומפוזיציה של
הוא הצגה של
כסכום של טבעיים.
- יש
פירוקים של
(כאשר יש חשיבות לסדר (
שונה מ־
) וחזרות מותרות (
ייספר כפירוק של 3)).
- יש
- מקדם מולטינומי: מספר המילים מאורך
שבהן המספר
מופיע
פעמים (
) הוא
.
- סימונים:
. כמו כן,
ו־
. ניתן להראות ש־
שלם.
-
ו־
.
- אם
זוגי אז
אי־זוגי.
- מספר התתי־מרחבים ממימד
של מרחב וקטורי
(כאשר ל־
יש
איברים) הוא
.
-
- אם
אז
, כלומר זה פולינום במשתנה
שמקדמיו שלמים ואי־שליליים. למעשה, הוא גם מתוקן, דרגתו
והוא סימטרי (כלומר המקדם של
שווה למקדם של
לכל
).
- הילוך שריג הוא סדרת צעדים בין נקודות ב־
שכל אחד מהם הוא הוספת 1 לאחת מהקואורדינטות של הנקודה בה נמצאים.
- יש
הילוכי שריג מ־
ל־
.
- נסמן
כמספר הילוכי השריג מ־
ל־
שהשטח המוגבל על־ידם, ציר ה־x והישר
הוא
. בנוסף, נגדיר
. אזי
.
- יש
- נסמן
. אזי
.
- יהי
וקטור שרכיביו אפסים ואחדות. אם
ו־
נכנה זאת הפרת סדר. אם נסמן
אז
.
- חלוקה של
היא וקטור
שסכום רכיביו הוא
(כלומר
) והם מסודרים בסדר יורד במובן הרחב. מספר החלוקות מסומן
.
- מספר החלוקות של
עם לכל היותר
רכיבים הוא המקדם של
בפולינום
, כלומר
.
- מספר החלוקות של
- דיאגרמת יאנג של חלוקה
היא דיאגרמת משבצות כך שבשורה ה־
יש
משבצות המיושרות לשמאל.
- הילוכי דיק הם הילוכי שריג מ־
ל־
שנמצאים על ומעל הישר
.
- מספר קטלן הוא מספר הילוכי דיק ל־
, מסומן
ושווה ל־
.
- נניח ש־
. יש
הילוכי דיק ל־
שאינם עוברים על הישר
למעט בנקודה
.
- מילת דיק מאורך
היא סדרה
כך ש־
,
ו־
. יש
מילות דיק מאורך
.
- עץ בינארי שלם/מלא הוא עץ כך שלכל אב יש בדיוק 2 בנים, כלומר לכל קודקוד שאינו עלה יש דרגה 3 למעט קודקוד אחד, שנקרא שורש. אם מבדילים בין הבן הימני לבן השמאלי אז יש
עצים בינארים מלאים עם
עלים.
- בהנתן מכפלה לא אסוציאטיבית
יש
דרכים להוסיף סוגריים.
- שילוש של מצולע משוכלל בעל
קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו
אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש
דרכים לשלש מצולע משוכלל בעל
צלעות.
- נניח ש־
- מספר בל הוא מספר חלוקות הקבוצות של
ומסומן
.
- מספר סטירלינג מסוג II הוא מספר חלוקות הקבוצות של
ל־
תתי־קבוצות לא ריקות ומסומן
.
-
.
- יהי
. נסמן
בתור המטריצה שהרכיב בשורה ה־
ובעמודה ה־
שלה הוא
.
-
.
-
- מספר סטירלינג הלא מסומן מסוג I הוא מספר התמורות על
עם
מחזורים ומסומן
.
-
.
-
.
-
- מספר סטירלינג מסוג I הוא
.
- יהי
. נסמן
בתור המטריצה שהרכיב בשורה ה־
ובעמודה ה־
שלה הוא
.
-
.
- יהי
-
.
פונקציות יוצרות
- טור חזקות פורמלי במשתנה
מכל
(בד״כ
) הוא ביטוי מהצורה
כאשר
. הטור לא חייב להתכנס. אוסף טורי החזקות הפורמליים ב־
מעל
מסומן
.
- אם
אז הטור הוא פולינום. אוסף הפולינומים ב־
מעל
מסומן
.
- אם
- נוסחת טיילור: אם
אז
.
- פונקציה יוצרת: לכל סדרה
נתאים פונקציה
.
- פונקציה יוצרת מעריכית: לכל סדרה
נתאים פונקציה
. פונקציות אלה שימושיות לספירת עצמים עבורם הסדר משנה.
- נרצה לחשב את
. נגדיר
ו־
ולכן
.
- נרצה למצוא את מספר הפתרונות של
כאשר
. נתאים לכל משתנה פונקציה יוצרת
ולכן מספר הפתרונות הדרוש הוא המקדם של
ב־
.
- אם
משתנה מקרי כש־
ו־
אז
, התוחלת היא
והשונות היא
.
נוסחאות
- נוסחת הנסיגה של פסקל:
-
- זהות הקפטן:
- הבינום של ניוטון:
- אם
אז
-
-
-
-
- אם
אז
-
-
- נוסחת המולטינום:
-
-
-
-
- נוסחת q־פסקל:
- q־בינום:
- נוסחת נסיגה למספרי קטלן:
ו־
- נוסחת נסיגה למספרי בל:
ו־
- נוסחת נסיגה למספרי סטירלינג מסוג II:
ו־
- נוסחת נסיגה למספרי סטירלינג לא מסומנים מסוג I:
ו־
- נוסחת נסיגה למספרי סטירלינג מסוג I:
-
-
-