הבדלים בין גרסאות בדף "תקציר מבוא לקומבינטוריקה, סמסטר א תשע״ג"
מתוך Math-Wiki
מ |
מ (←נוסחאות נסיגה) |
||
(גרסת ביניים אחת של אותו משתמש אינה מוצגת) | |||
שורה 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: ו־