הבדלים בין גרסאות בדף "תקציר מבוא לקומבינטוריקה, סמסטר א תשע״ג"
מתוך Math-Wiki
מ (←נוסחאות) |
מ (←נוסחאות נסיגה) |
||
(2 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
שורה 8: | שורה 8: | ||
:* ללוח בגודל <math>2\times n</math> קיימים <math>F_n</math> ריצופי דומינו. | :* ללוח בגודל <math>2\times n</math> קיימים <math>F_n</math> ריצופי דומינו. | ||
* '''עקרון שובך יונים:''' בחלוקה של קבוצה סופית <math>A</math> ל־<math>n</math> יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות <math>|A|/n</math>. | * '''עקרון שובך יונים:''' בחלוקה של קבוצה סופית <math>A</math> ל־<math>n</math> יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות <math>|A|/n</math>. | ||
− | * {{הערה|סימונים:}} <math>(\alpha)_k:=\prod_{i=0}^{k-1}(\alpha-i)</math> | + | * {{הערה|סימונים:}} <math>(\alpha)_k:=\prod_{i=0}^{k-1}(\alpha-i)</math> ו־<math>(n)_k=\begin{cases}\frac{n!}{(n-k)!},&k\le n\\0,&\text{else}\end{cases}</math>. בנוסף, <math>\binom nk:=\begin{cases}\frac{n!}{k!(n-k)!},&0\le k\le n\\0,&\text{else}\end{cases}</math> ו־<math>\binom\alpha k:=\frac{(\alpha)_k}{k!}</math>. |
* '''חליפה:''' נניח <math>0\le k\le n</math>. חליפה של <math>k</math> איברים מתוך <math>n</math> היא <math>k</math>־יה סדורה של איברים שונים מקבוצה בת <math>n</math> איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא <math>P(n,k):=(n)_k</math>. | * '''חליפה:''' נניח <math>0\le k\le n</math>. חליפה של <math>k</math> איברים מתוך <math>n</math> היא <math>k</math>־יה סדורה של איברים שונים מקבוצה בת <math>n</math> איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא <math>P(n,k):=(n)_k</math>. | ||
:* '''תמורה''' היא חליפה של <math>n</math> מתוך <math>n</math>, ומספר התמורות הוא <math>P(n):=(n)_n=n!</math>. | :* '''תמורה''' היא חליפה של <math>n</math> מתוך <math>n</math>, ומספר התמורות הוא <math>P(n):=(n)_n=n!</math>. | ||
שורה 33: | שורה 33: | ||
:* יש <math>2^{n-1}</math> פירוקים של <math>n</math> (כאשר יש חשיבות לסדר (<math>2+1</math> שונה מ־<math>1+2</math>) וחזרות מותרות (<math>1+1+1</math> ייספר כפירוק של 3)). | :* יש <math>2^{n-1}</math> פירוקים של <math>n</math> (כאשר יש חשיבות לסדר (<math>2+1</math> שונה מ־<math>1+2</math>) וחזרות מותרות (<math>1+1+1</math> ייספר כפירוק של 3)). | ||
* '''מקדם מולטינומי:''' מספר המילים מאורך <math>n</math> שבהן המספר <math>i</math> מופיע <math>n_i</math> פעמים (<math>\sum_i n_i=n</math>) הוא <math>\binom n{n_1,n_2,\dots}=n!\left/\prod_i n_i!\right.</math>. | * '''מקדם מולטינומי:''' מספר המילים מאורך <math>n</math> שבהן המספר <math>i</math> מופיע <math>n_i</math> פעמים (<math>\sum_i n_i=n</math>) הוא <math>\binom n{n_1,n_2,\dots}=n!\left/\prod_i n_i!\right.</math>. | ||
− | * {{הערה|סימונים:}} <math>[n]_q:=\sum_{i=0}^{ | + | * {{הערה|סימונים:}} <math>[n]_q:=\sum_{i=0}^{n-1}q^i</math>. כמו כן, <math>[n]_q!:=\prod_{i=1}^n [i]_q,\ [0]_q!=1</math> ו־<math>\forall 0\le k\le n:\ \begin{bmatrix}n\\k\end{bmatrix}_q:=\frac{[n]_q!}{[k]_q![n-k]_q!}</math>. ניתן להראות ש־<math>\begin{bmatrix}n\\k\end{bmatrix}_q</math> שלם. |
:* <math>[n]_1=n</math> ו־<math>\forall q\ne 1:\ [n]_q=\frac{q^n-1}{q-1}</math>. | :* <math>[n]_1=n</math> ו־<math>\forall q\ne 1:\ [n]_q=\frac{q^n-1}{q-1}</math>. | ||
:* אם <math>q</math> זוגי אז <math>\begin{bmatrix}n\\k\end{bmatrix}_q</math> אי־זוגי. | :* אם <math>q</math> זוגי אז <math>\begin{bmatrix}n\\k\end{bmatrix}_q</math> אי־זוגי. | ||
שורה 86: | שורה 86: | ||
:* '''נוסחת נסיגה לינארית''' מסדר <math>k</math> היא נוסחה מהצורה <math>\forall n\ge k:\ a_n=f(n)+\sum_{i=1}^k c_i(n)a_{n-i}</math>. אם <math>c_i</math> פונקציות קבועות אז נאמר שהנוסחה עם מקדמים קבועים. אם <math>f(n)\equiv0</math> אז נאמר שהיא הומוגנית. | :* '''נוסחת נסיגה לינארית''' מסדר <math>k</math> היא נוסחה מהצורה <math>\forall n\ge k:\ a_n=f(n)+\sum_{i=1}^k c_i(n)a_{n-i}</math>. אם <math>c_i</math> פונקציות קבועות אז נאמר שהנוסחה עם מקדמים קבועים. אם <math>f(n)\equiv0</math> אז נאמר שהיא הומוגנית. | ||
::* קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר <math>k</math> היא מרחב וקטורי ממימד <math>k</math>. | ::* קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר <math>k</math> היא מרחב וקטורי ממימד <math>k</math>. | ||
− | * נרצה לחשב את אברי <math>(a_i)_{i=0}^\infty</math> בהינתן תנאי ההתחלה <math>(a_i)_{i=0}^{k-1}</math> ונוסחת נסיגה <math>\forall i\ge k:\ a_i= | + | * נרצה לחשב את אברי <math>(a_i)_{i=0}^\infty</math> בהינתן תנאי ההתחלה <math>(a_i)_{i=0}^{k-1}</math> ונוסחת נסיגה <math>\forall i\ge k:\ a_i=g(a_{i-1},\dots,a_{i-k})</math>. נעזר בפונקציה היוצרת <math>f(x)=\sum_{i=0}^\infty a_i x^i</math> ואם קיימת פונקציה <math>G</math> עבורה {{left|<math>\begin{align}f(x)&=\sum_{i=0}^{k-1} a_i x^i+\sum_{i=k}^\infty g(a_{i-1},\dots,a_{i-k})x^i\\&=\sum_{i=0}^{k-1} a_i x^i+G\!\left(x,\sum_{i=k}^\infty a_{i-1}x^{i-1},\dots,\sum_{i=k}^\infty a_{i-k}x^{i-k}\right)\\&=\sum_{i=0}^{k-1} a_i x^i+G\!\left(x,f(x)-\sum_{i=0}^{k-2} a_ix^i,\dots,f(x)\right)\end{align}</math>}}אז נבודד את <math>f(x)</math> ונקבל נוסחה מפורשת למקדמים <math>a_i</math> של <math>x^i</math>. |
− | * תהי נוסחת נסיגה לינארית הומוגנית <math>a_n=\sum_{i=1}^k c_i a_{n-i}</math> מסדר <math>k</math>. נניח שיש <math>\alpha\in\mathbb C</math> עבורו <math>\forall n:\ a_n=\alpha^n</math> (לא תמיד זה נכון). אזי <math>\alpha=0</math> פתרון. <math>x^k-\sum_{i=1}^k c_i x^{k-i}</math> נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם <math>\alpha\ne0</math> אז הוא שווה ל־0 בנקודה <math>\alpha</math>. יש לו <math>k</math> שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם <math>\alpha_1,\dots,\alpha_k</math> אז <math>\forall n,i:\ a_n=\alpha_i^n</math>. המרחב הווקטורי של הפתרונות הוא אם כן <math>\left\{\left(\sum_{i=1}^k r_i\alpha_i^n\right)_{n=0}^\infty:\ \forall i:\ r_i\in\mathbb C\right\}</math>. אם נתונים תנאי ההתחלה ניתן גם לחשב את ה־<math>r_i</math>־ים. | + | * תהי נוסחת נסיגה לינארית הומוגנית עם מקדמים קבועים <math>a_n=\sum_{i=1}^k c_i a_{n-i}</math> מסדר <math>k</math>. נניח שיש <math>\alpha\in\mathbb C</math> עבורו <math>\forall n:\ a_n=\alpha^n</math> (לא תמיד זה נכון). אזי <math>\alpha=0</math> פתרון. <math>x^k-\sum_{i=1}^k c_i x^{k-i}</math> נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם <math>\alpha\ne0</math> אז הוא שווה ל־0 בנקודה <math>\alpha</math>. יש לו <math>k</math> שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם <math>\alpha_1,\dots,\alpha_k</math> אז <math>\forall n,i:\ a_n=\alpha_i^n</math>. המרחב הווקטורי של הפתרונות הוא אם כן <math>\left\{\left(\sum_{i=1}^k r_i\alpha_i^n\right)_{n=0}^\infty:\ \forall i:\ r_i\in\mathbb C\right\}</math>. אם נתונים תנאי ההתחלה ניתן גם לחשב את ה־<math>r_i</math>־ים. |
=== נוסחאות === | === נוסחאות === |
גרסה אחרונה מ־13:06, 9 באוקטובר 2013
בתקציר זה, אלא אם צוין אחרת, כל המשתנים והנעלמים שלמים ואי־שליליים למעט .
ראשוני ו־
אינו שלם או אי־שלילי רק במקרים בהם הוא מוצג כמשתנה בפולינום.
שדה.
- נסמן
.
היא קבוצת כל התמורות על
.
- חלוקת קבוצות של
ל־
היא בחירה של תתי־קבוצות
זרות עבורן
.
- סדרת פיבונצ׳י תסומן
והיא מקיימת
.
- ריצוף דומינו של
הוא כיסוי של
על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־
.
- ללוח בגודל
קיים ריצוף דומינו אם״ם
זוגי.
- ללוח בגודל
קיימים
ריצופי דומינו.
- ללוח בגודל
- עקרון שובך יונים: בחלוקה של קבוצה סופית
ל־
יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות
.
- סימונים:
ו־
. בנוסף,
ו־
.
- חליפה: נניח
. חליפה של
איברים מתוך
היא
־יה סדורה של איברים שונים מקבוצה בת
איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא
.
- תמורה היא חליפה של
מתוך
, ומספר התמורות הוא
.
- חליפה עם חזרות היא
־יה סדורה של
איברים (לא דווקא שונים) מתוך
. יש
חליפות עם חזרות.
- תמורה היא חליפה של
- צירוף: נניח
. צירוף של
איברים מתוך
הוא תת־קבוצה של קבוצה בת
איברים (כלומר, צירוף הוא בחירה ללא חזרות ובלי חשיבות לסדר). מספר הצירופים הוא
.
- צירוף עם חזרות: הוא רב־קבוצה מסדר
של איברים מתוך קבוצה בת
איברים. יש
צירופים עם חזרות.
- מספר הצירופים עם חזרות של
מתוך
שווה למספר הדרכים לבחור
עצמים מתוך
סוגים, ששווה למספר הפתרונות השלמים ואי־שליליים ל־
.
- מספר הצירופים עם חזרות של
- צירוף עם חזרות: הוא רב־קבוצה מסדר
- הווקטור האופייני של קבוצה
מוגדר ע״י
.
- סדרה אונימוצלית היא סדרה
כך שקיים
עבורו
עולה במובן הרחב ו־
יורדת במובן הרחב.
-
היא סדרה אונימוצלית כאשר אם
זוגי אז
ואחרת
(כי
).
-
- הפרת סדר בתמורה
היא זוג
כך ש־
. מספר הפרות הסדר מסומן
וסימן התמורה מוגדר כ־
. התמרה
תקרא זוגית אם
ואי־זוגית אחרת. יש
התמרות מכל סוג שסדרן
.
- מורד: עבור
נקרא ל־
מורָד (descent) אם
. קבוצת המורדות תסומן
.
-
.
-
- אי־סדר מלא הוא תמורה
כך ש־
. קבוצת האי־סדרים המלאים ב־
מסומנת
ומקיימת
.
- אם
אז
.
- יהי פולינום
. נסמן
.
-
.
- משפט פרמה הקטן:
.
- פיתוח של מספר לפי ראשוני: נניח
ו־
. אזי קיימים
שלמים כך ש־
ו־
. סכום זה נקרא "הפיתוח של
לפי
".
- אם
אז
. לפיכך,
.
- משפט לוקאס: נניח ש־
ו־
פיתוחים לפי
. אזי
.
-
אם״ם בפיתוחים
יש
עבורו
.
- פירוק/קומפוזיציה של
הוא הצגה של
כסכום של טבעיים.
- יש
פירוקים של
(כאשר יש חשיבות לסדר (
שונה מ־
) וחזרות מותרות (
ייספר כפירוק של 3)).
- יש
- מקדם מולטינומי: מספר המילים מאורך
שבהן המספר
מופיע
פעמים (
) הוא
.
- סימונים:
. כמו כן,
ו־
. ניתן להראות ש־
שלם.
-
ו־
.
- אם
זוגי אז
אי־זוגי.
- מספר התתי־מרחבים ממימד
של מרחב וקטורי
(כאשר ל־
יש
איברים) הוא
.
-
- אם
אז
, כלומר זה פולינום במשתנה
שמקדמיו שלמים ואי־שליליים. למעשה, הוא גם מתוקן, דרגתו
והוא סימטרי (כלומר המקדם של
שווה למקדם של
לכל
).
- הילוך שריג הוא סדרת צעדים בין נקודות ב־
שכל אחד מהם הוא הוספת 1 לאחת מהקואורדינטות של הנקודה בה נמצאים.
- יש
הילוכי שריג מ־
ל־
.
- נסמן
כמספר הילוכי השריג מ־
ל־
שהשטח המוגבל על־ידם, ציר ה־x והישר
הוא
. בנוסף, נגדיר
. אזי
.
- יש
- נסמן
. אזי
.
- יהי
וקטור שרכיביו אפסים ואחדות. אם
ו־
נכנה זאת הפרת סדר. אם נסמן
אז
.
- חלוקה של
היא וקטור
שסכום רכיביו הוא
(כלומר
) והם מסודרים בסדר יורד במובן הרחב. מספר החלוקות מסומן
.
- מספר החלוקות של
עם לכל היותר
רכיבים הוא המקדם של
בפולינום
, כלומר
.
- מספר החלוקות של
- דיאגרמת יאנג של חלוקה
היא דיאגרמת משבצות כך שבשורה ה־
יש
משבצות המיושרות לשמאל.
- טבלת יאנג היא התאמה חח״ע ממשבצות של דיאגרמת יאנג נתונה (שנוצרת מחלוקה של
) על
כך שהמספרים עולים לאורך השורות העמודות.
-
היא מספר טבלאות יאנג שקיימות לדיאגרמת יאנג הנוצרת מהחלוקה
.
-
.
- נוסחת הווים: תהי
ונרצה לחשב את
. לכל משבצת בדיאגרמת יאנג נתאים "אורך וו" (hook length) כמספר המשבצות באותה שורה או עמודה שאחרי המשבצת הנתונה ועוד 1. נסמן
כמכפלת אורכי הווים של כל המשבצות. אזי
.
-
-
- הילוכי דיק הם הילוכי שריג מ־
ל־
שנמצאים על ומעל הישר
.
- מספר קטלן הוא מספר הילוכי דיק ל־
, מסומן
ושווה ל־
.
- נניח ש־
. יש
הילוכי דיק ל־
שאינם עוברים על הישר
למעט בנקודה
.
- מילת דיק מאורך
היא סדרה
כך ש־
,
ו־
. יש
מילות דיק מאורך
.
- עץ בינארי שלם/מלא הוא עץ כך שלכל אב יש בדיוק 2 בנים, כלומר לכל קודקוד שאינו עלה יש דרגה 3 למעט קודקוד אחד, שנקרא שורש. אם מבדילים בין הבן הימני לבן השמאלי אז יש
עצים בינארים מלאים עם
עלים.
- בהינתן מכפלה לא אסוציאטיבית
יש
דרכים להוסיף סוגריים.
- שילוש של מצולע משוכלל בעל
קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו
אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש
דרכים לשלש מצולע משוכלל בעל
צלעות.
- נניח ש־
- מספר בל הוא מספר חלוקות הקבוצה
ומסומן
.
- מספר סטירלינג הלא מסומן מסוג I הוא מספר התמורות על
עם
מחזורים ומסומן
.
-
.
-
.
-
- מספר סטירלינג מסוג I הוא
.
- יהי
. נסמן
בתור המטריצה שהרכיב בשורה ה־
ובעמודה ה־
שלה הוא
.
-
.
- יהי
- מספר סטירלינג מסוג II הוא מספר חלוקות הקבוצה
ל־
תתי־קבוצות לא ריקות ומסומן
.
-
.
- יהי
. נסמן
בתור המטריצה שהרכיב בשורה ה־
ובעמודה ה־
שלה הוא
.
-
.
-
-
.
פונקציות יוצרות
- טור חזקות פורמלי במשתנה
מכל
(בד״כ
) הוא ביטוי מהצורה
כאשר
. הטור לא חייב להתכנס. אוסף טורי החזקות הפורמליים ב־
מעל
מסומן
.
- אם
אז הטור הוא פולינום. אוסף הפולינומים ב־
מעל
מסומן
.
- אם
- נוסחת טיילור: אם
אז
.
- פונקציה יוצרת: לכל סדרה
נתאים פונקציה
.
- פונקציה יוצרת מעריכית: לכל סדרה
נתאים פונקציה
. פונקציות אלה שימושיות לספירת עצמים עבורם הסדר משנה.
- נרצה לחשב את
. נגדיר
ו־
ולכן
.
- נרצה למצוא את מספר הפתרונות של
כאשר
. נתאים לכל משתנה פונקציה יוצרת
ולכן מספר הפתרונות הדרוש הוא המקדם של
ב־
.
- נרצה למצוא כמה חליפות עם חזרות קיימות של
מתוך
כאשר כל
חייב להופיע מספר פעמים השייך לקבוצה
. נתאים לכל
פונקציה
ולכן הכמות הדרושה היא המקדם של
ב־
.
- אם
משתנה מקרי כש־
ו־
אז
, התוחלת היא
והשונות היא
.
נוסחאות נסיגה
- נוסחת נסיגה מסדר
היא נוסחה מהצורה
.
- איברי סדרה המקיימת נוסחת נסיגה כזו נקבעים ע״י
האיברים הראשונים, והם נקראים תנאי ההתחלה.
- נוסחת נסיגה לינארית מסדר
היא נוסחה מהצורה
. אם
פונקציות קבועות אז נאמר שהנוסחה עם מקדמים קבועים. אם
אז נאמר שהיא הומוגנית.
- קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר
היא מרחב וקטורי ממימד
.
- קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר
- איברי סדרה המקיימת נוסחת נסיגה כזו נקבעים ע״י
- נרצה לחשב את אברי
בהינתן תנאי ההתחלה
ונוסחת נסיגה
. נעזר בפונקציה היוצרת
ואם קיימת פונקציה
עבורה
אז נבודד אתונקבל נוסחה מפורשת למקדמים
של
.
- תהי נוסחת נסיגה לינארית הומוגנית עם מקדמים קבועים
מסדר
. נניח שיש
עבורו
(לא תמיד זה נכון). אזי
פתרון.
נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם
אז הוא שווה ל־0 בנקודה
. יש לו
שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם
אז
. המרחב הווקטורי של הפתרונות הוא אם כן
. אם נתונים תנאי ההתחלה ניתן גם לחשב את ה־
־ים.
נוסחאות
- נוסחת הנסיגה של פסקל:
-
- זהות הקפטן:
- הבינום של ניוטון:
-
-
-
-
-
-
-
-
- נוסחת המולטינום:
-
-
-
-
- נוסחת q־פסקל:
- q־בינום:
- נוסחת נסיגה למספרי קטלן:
ו־
- נוסחת נסיגה למספרי בל:
ו־
- נוסחת נסיגה למספרי סטירלינג לא מסומנים מסוג I:
ו־
- נוסחת נסיגה למספרי סטירלינג מסוג I:
- נוסחת נסיגה למספרי סטירלינג מסוג II:
ו־
-
-
-