הגדרה 1 (פונקציה יוצרת)

נתונה סדרה אינסופית $a_{n}$ . אזי, הפונקציה היוצרת של הסדרה הינה $\displaystyle A(x)=\sum_{i=0}^\infty a_{i}x^i$ .

פונקציות יוצרות הן בעצם טורי חזקות המתכנסים בהחלט בסביבה באורך חיובי של $0$ . המטרה בשימוש בפונקציות יוצרות היא לנתח תכונות של סדרות מספרים ע"י הפונצקיות היוצרות בצורת טורי חזקות.

דוגמה

עבור הסדרה $a_{i}=1$ לכל $i \in \mathbb{N}$ מתקיים:

A(x)=\sum_{i=0}^\infty x^i=\frac{1}{1-x}

דוגמה

עבור הסדרה $a_{i}=\lambda^i$ לכל $i \in \mathbb{N}$ מתקיים:

A(x)=\sum_{i=0}^\infty \lambda^ix^i=\sum_{i=0}^\infty (\lambda x)^i=\frac{1}{1-\lambda x}

דוגמה

עבור $a_{i}=i+1$ לכל $i \in \mathbb{N}$ מתקיים:

A(x)=\sum_{i=0}^\infty (i+1)x^i=1+2x+3x^2+4x^3+\dots=\left( \sum_{i=0}^\infty x^{i} \right)'=\left( \frac{1}{1-x} \right)'=\frac{1}{(1-x)^2}

דוגמה

עבור הסדרה $a_{i}=i$ לכל $i \in \mathbb{N}$ מתקיים:

A(x)=\sum_{i=0}^\infty ix^i=x+2x^2+3x^3+4x^4+\dots=x(1+2x+3x^2+4x^3+\cdots)=\frac{x}{(1-x)^2}

דוגמה

עבור הסדרה $a_{i}=\begin{pmatrix}n\\i\end{pmatrix}$ מתקיים:

A(x)=\sum_{i=0}^\infty \begin{pmatrix} n \\ i \end{pmatrix}x^i=(x+1)^n

דוגמה

עבור $a_{i}=\begin{cases}1 & i< n\\ 0 & i\geq n\end{cases}$ מתקיים:

A(x)=\sum_{i=0}^{n-1}x^i=\frac{x^n-1}{x-1}

משפט

אם $\displaystyle A(x)=\sum_{i=0}^\infty a_{i}x^i$ ו- $A$ אנליטית בסביבת $0$ אזי $\displaystyle a_{k}=\frac{A^{(k)}(0)}{k!}$ .

הוכחה: פיתוח לטור טיילור.

דוגמה

A(x)=\frac{1}{(1-x)^n}

A'(x)=\frac{n}{(1-x)^{n+1}} \quad \quad A''(x)=\frac{n(n+1)}{(1-x)^{n+2}} \quad \quad A'''(x)=\frac{n(n+1)(n+2)}{(1-x)^{n+3}}

A^{(k)}(x)=\frac{n(n+1)(n+2)\cdots(n+k-1)}{(1-x)^{n+k}}=\frac{(n+k-1)!}{(n-1)!}\cdot \frac{1}{(1-x)^{n+k}}

כעת, לפי המשפט מתקיים:

a_{k}=\frac{A^{(k)}(0)}{k!}=\frac{(n+k-1)!}{k!(n-1)!}=\begin{pmatrix} n+k-1 \\ k \end{pmatrix}=\mathbb{C}_{n}^k

לכן מתקיים:

\frac{1}{(1-x)^n}=\sum_{i=0}^\infty \mathbb{C}_{n}^i x^i

מסקנה

\frac{1}{(1-\lambda x)^n}=\sum_{i=0}^\infty \mathbb{C}_{n}^i \lambda^ix^i

משפט (תכונות פונקציות יוצרות)

יהיו $a_{i},b_{i}$ סדרות בעלות פונקציות יוצרות $A(x),B(x)$ בהתאמה.

$A(x)\pm B(x)$ היא הפונקציה היוצרת של הסדרה $c_{i}=a_{i}\pm b_{i}$
$A(x)\cdot B(x)$ היא הפונקציה היוצרת של הסדרה $\displaystyle c_{i}=\sum_{j=0}^i a_{j}b_{i-j}$
$\alpha A(x)$ עבור $\alpha \in \mathbb{R}$ היא הפונקציה היוצרת של הסדרה $c_{i}=\alpha a_{i}$
$xA(x)$ היא הפונקציה היוצרת של הסדרה $c_{i}=\begin{cases}0 & i=0 \\ a_{i-1} & i> 0\end{cases}$

הוכחה (2):

A(x)\cdot B(x)=\left( \sum_{i=0}^\infty a_{i}x^i \right)\left( \sum_{j=0}^\infty b_{j}x^j \right)=(a_{0}+a_{1}x+a_{2}x^2+\dots)(b_{0}+b_{1}x+b_{2}x^2)

A(x)\cdot B(x)=\sum_{i=0}^\infty \sum_{j=0}^\infty a_{i}b_{j}x^{i+j}

לכן מתקיים: $\displaystyle c_{i}=\sum_{j=0}^i a_{j}b_{i-j}$ כנדרש.
∎

שימוש פונקציות יוצרות בקומבינטוריקה

הוכחת זהויות קומבינטוריות

נרצה להוכיח כי $\begin{pmatrix}n+1\\ k\end{pmatrix}=\begin{pmatrix}n \\ k\end{pmatrix}+\begin{pmatrix}n\\ k-1\end{pmatrix}$ באמצעות פונקציות יוצרות.
הוכחה:
נגדיר $a_{k}=\begin{pmatrix}n \\ k\end{pmatrix}$ ו- $b_{k}=\begin{pmatrix}n\\ k-1\end{pmatrix}=a_{k-1}$ . הפונקציות היוצרות שלה הינן:

A(x)=(x+1)^n \qquad \qquad B(x)=x(x+1)^n

כעת, עבור $a_{k}+b_{k}$ מתקיים:

A(x)+B(x)=(x+1)^n+x(x+1)^n=(x+1)^{n+1}

ולכן מתקיים:

c_{k}=a_{k}+b_{k}=\begin{pmatrix} n+1 \\ k \end{pmatrix}

כנדרש.
∎

כעת, נרצה להוכיח כי $\displaystyle \begin{pmatrix}n+m\\ k\end{pmatrix}=\sum_{j=0}^k \begin{pmatrix}n \\ j\end{pmatrix}\begin{pmatrix}m \\ k-j\end{pmatrix}$ באמצעות פונקציות יוצרות.
הוכחה:
נגדיר $a_{k}=\begin{pmatrix}n \\ k\end{pmatrix},b_{k}=\begin{pmatrix}m \\ k\end{pmatrix}$ כאשר $A(x)=(x+1)^n,B(x)=(x+1)^m$ .
בנוסף, נגדיר $c_{k}=\begin{pmatrix}n+m \\ k\end{pmatrix}$ ואז $C(x)=(x+1)^{n+m}$ . ואז מתקיים:

C(x)=(x+1)^{n+m}=(x+1)^n(x+1)^m=A(x)B(x)

ולכן:

\begin{pmatrix} n+m \\ k \end{pmatrix}=c_{k}=\sum_{j=0}^k a_{j}b_{k-j}=\sum_{j=0}^k \begin{pmatrix} n \\ j \end{pmatrix}\begin{pmatrix} m \\ k-j \end{pmatrix}

∎

מציאת מספר פתרונות למשוואה

נרצה למצוא את מספר הפתרונות של $y_{1}+y_{2}+y_{3}=i$ כאשר $0\leq y_{1}\leq 2$ , מתקיים כי $y_{2}$ זוגי ו- $y_{3} \in \left\{ 1,5,7 \right\}$ .
נסמן מספר זה ב- $a_{i}$ .
המשתנה $y_{1}$ מגדיר סדרת מספרים עבור הערכים אותם הוא יכול לקבל ואז $A_{1}(x)=1+x+x^2$ .
המשתנה $y_{2}$ מגדיר סדרת מספרים עבור הערכים אותם הוא יכול לקבל ואז $A_{2}=1+x^2+x^4+x^6+\dots=\frac{1}{1-x^2}$ .
המשתנה $y_{3}$ מגדיר סדרת מספרים עבור הערכים אותם הוא יכול לקבל ואז $A_{3}=x+x^5+x^7$ .
נקבל:

A_{1}A_{2}A_{3}=(1+x+x^2)(1+x^2+x^4+x^6+\cdots)(x+^5+x^7)

המקדם של $x^i$ במכפלה $A_{1}A_{2}A_{3}$ הוא כמספר הפתרונות של המשוואה $y_{1}+y_{2}+y_{3}=i$ עם התנאים שהוצבו.

משפט

תהיינה $Z_{1},Z_{2},\dots,Z_{n}$ קבוצות של מספרים טבעיים. אזי המקדם $a_{k}$ של $x^k$ בביטוי:

A(x)=\left( \sum_{i_{1} \in Z_{1}} x^{i_{1}} \right)\left( \sum_{i_{2} \in Z_{2}} x^{i_{2}} \right)\dots\left( \sum_{i_{n} \in Z_{n}} x^{i_{n}} \right)

שווה למספר הפתרונות של המשוואה $y_{1}+y_{2}+\dots+y_{n}=k$ כאשר $y_{1} \in Z_{1},y_{2} \in Z_{2},\dots,y_{n}\in Z_{n}$ .

הוכחה:

A(x)=\sum_{i_{1} \in Z_{1},i_{2}\in Z_{2},\dots,i_{n}\in Z_{n}} \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! x^{i_{1}+i_{2}+\dots+i_{n}}=\sum_{k=0}^\infty a_{k}x^k

∎

דוגמה

נרצה למצוא את מספר הפתרונות של $y_{1}+y_{2}+\dots+y_{n}=k$ כאשר $y_{1},\dots,y_{n}\in \left\{ 0,1 \right\}$ .
נבחר $Z_{1}=Z_{2}=\dots=Z_{n}=\left\{ 0,1 \right\}$ ונגדיר $A(x)$ כמו במשפט ואז:

A(x)=(1+x)(1+x) \overset{n}{\cdots} (1+x)=(1+x)^n

ולכן, המקדם של $x^k$ בביטוי יהיה $\begin{pmatrix}n \\ k\end{pmatrix}$ .

דוגמה

נרצה למצוא את מספר הפתרונות של $y_{1}+y_{2}+\dots+y_{n}=k$ כאשר $y_{1},y_{2},\dots,y_{n}$ מספרים טבעיים.
נבחר $Z_{1}=Z_{2}=\dots=Z_{n}=\mathbb{N}$ . אזי:

A(x)=(1+x+x^2+\cdots)^n=\frac{1}{(1-x)^n}=\sum_{i=0}^\infty \mathbb{C}_{n}^i x^i

ולכן, המקדם של $x^k$ ב- $A$ הינו $\mathbb{C}_{n}^k$ .

דוגמה

נרצה למצוא את מספר הפתרונות של $y_{1}+y_{2}+\dots+y_{n}=k$ כאשר $y_{1},y_{2},\dots,y_{n}$ טבעיים אי-זוגיים.
נבחר $Z_{1}=Z_{2}=\dots=Z_{n}=\left\{ 1,3,5,\dots \right\}$ ואז $A(x)=(x+x^3+x^5+\cdots)^n=x^n(1+x^2+x^4+\cdots)^n$ ולכן:

A(x)=\frac{x^n}{(1-x^2)^n}=x^n \sum_{i=0}^\infty \mathbb{C}_{n}^i x^{2i}=\sum_{i=0}^\infty \mathbb{C}_{n}^i x^{2i+n}

ולכן, עבור $k=2i+n$ המקדם של $x^k$ ב- $A$ הוא $\mathbb{C}_{n}^i=\mathbb{C}_{n}^{\frac{k-n}{2}}$ כאשר $i=\frac{k-n}{2}$
זאת כאשר $k\geq n$ ול- $k$ ול- $n$ אותה זוגיות.

משפט

אם $\displaystyle A(x)=\sum_{i=0}^\infty a_{i}x^i$ ו- $A$ אנליטית בסביבת $0$ אזי $a_{k}=\frac{A^{(k)}(0)}{k!}$ .

פתרון נוסחאת נסיגה

בהינתן נוסחת נסיגה לרוב נרצה למצוא ביטוי מפורש עבור $n$ . לשם כך יש לנו מספר שיטות:

לסדרות כלליות

השיטות הלא שימושיות

ניתן לפתור באמצעות:

הצבה חוזרת
ניחוש ואינדוקציה

פתרון ע"י פונקציה יוצרת

תהי נוסחת הנסיגה $a_{n}=a_{n-1}+2(n-1)$ כאשר $a_{1}=2$ .
ראשית, נגדיר $a_{0}$ המקיים את נוסחת הנסיגה. נגדיר $a_{0}=2$ .
נפתור זאת באמצעות פונקציה יוצרת:

a_{i}x^i=a_{i-1}x^i+2(i-1)x^i

\sum_{i=1}^\infty a_{i}x^i=\sum_{i=1}^\infty a_{i-1}x^i+\sum_{i=1}^\infty 2(i-1)x^i

נמצא את שני החלקים:

\sum_{i=1}^\infty a_{i-1}x^i=x\sum_{i=1}^\infty a_{i-1}x^{i-1}=xA(x)

2\sum_{i=1}^\infty (i-1)x^i=2x\sum_{i=1}^\infty (i-1)x^{i-1}=2x\sum_{i=1}^\infty ix^i=2x^2\sum_{i=1}^\infty ix^{i-1}=2x^2 \sum_{i=1}^\infty (x^i)'=2x^2\left( \frac{1}{1-x} \right)'

2\sum_{i=1}^\infty (i-1)x^i=\frac{2x^2}{(1-x)^2}

נחבר ונקבל:

A(x)-2=xA(x)+\frac{2x^2}{(1-x)^2}

נעביר אגפים לקבלת התשובה:

A(x)=\frac{2x^2}{(1-x)^3}+\frac{2}{1-x}

כעת נרצה למצוא נוסחה מפורשת עבור איבר בסדרה דרך הפונקציה היוצרת.
נראה את הנוסחה $\displaystyle \frac{1}{(1-x)^m}=\sum_{i=0}^\infty \mathbb{C}_{m}^i x^i$ ואז נקבל:

A(x)=2x^2\sum_{i=0}^\infty \mathbb{C}_{3}^i x^i+2\sum_{i=0}^\infty x^i=\sum_{i=0}^\infty 2\mathbb{C}_{3}^i x^{i+2}+\sum_{i=0}^\infty 2x^i

המקדם של $x^n$ ב- $A(x)$ הינו:

2\mathbb{C}_{3}^{n-2}+2=2\begin{pmatrix} n-2+3-1 \\ 3-1 \end{pmatrix}+2=2 \frac{n(n-1)}{2}+2=n^2-n+2

וזוהי התשובה שלנו.

מקדמים קבועים

נסתכל על נוסחת נסיגה ליניארית מסדר $L$ עם מקדמים קבועים:

a_{n}=q_{1}a_{n-1}+q_{2}a_{n-2}+\dots+q_{L}a_{n-L}+u_{n}

כאשר $q_{L}\neq 0$ ו- $u_{n}$ הינה סדרה נתונה.

הגדרה 2 (נוסחת נסיגה הומוגנית)

כאשר $u_{n}\equiv 0$ נוסחת הנסיגה נקראת הומוגנית

טענה

אם הסדרות $a_{n},b_{n}$ מקיימות אותה נוסחת נסיגה ליניארית הומוגנית,
אזי, גם הסדרה $\alpha a_{n}+\beta b_{n}$ מקיימת אותה לכל $\alpha,\beta$ קבועים.

תרגיל

הוכיחו (נובע מליניאריות)

משפט

A(x)=\frac{r(x)}{q(x)}

כשהפולינום $r(x)$ נקבע ע"פ תנאי ההתחלה ומעלתו מקיימת $\deg r(x)< \deg q(x)=L$ .

דוגמה

עבור נוסחת הנסיגה $a_{n}=2a_{n-1}+3a_{n-2}$ כאשר $a_{0}=1,a_{1}=4$ אזי $q(x)=1-2x-3x^2$ ונקבל:

A(x)=\frac{2x+1}{1-2x-3x^2}=\frac{r(x)}{q(x)}

כעת נרצה למצוא את $r(x)$ .

(a_{0}+a_{1}x+a_{2}x^2+\cdots)(1-2x-3x^2)=r_{0}+r_{1}x

r_{0}=a_{0} \qquad \qquad r_{1}=a_{1}-q_{1}a_{0}

הוכחה:

\sum_{i=0}^\infty r_{i}x^i=r(x) \overset{\Tiny def}{=} q(x)\cdot A(x)=(1-q_{1}x-q_{2}x^2-\dots-q_{L}x^L)\sum_{k=0}^\infty a_{k}x^k

\Downarrow

\begin{cases} r_{0}=a_{0} \\ r_{1}=a_{1}-q_{1}a_{0} \\ r_{2}=a_{2}-q_{1}a_{1}-q_{2}a_{0} \\ r_{L-1}=a_{L-1}-q_{1}a_{L-2}-\dots.-q_{L-1}a_{0} \\ u_{n}=r_{n}=a_{n}-q_{1}a_{n-1}-\dots-q_{L}a_{n-L} \end{cases}

∎

באמצעות פולינום אופייני

נניח יש לנו: $q(x)=1-q_{1}-q_{2}x^2-\dots-q_{L}x^L$ אזי הפולינום האופייני של $q$ הינו:

\overset{\leftharpoonup}{q}(x)=x^L-q_{1}x^{L-1}-q_{2}x^{L-2}-\dots-q_{L}

??????

5 - פונקציות יוצרות

קומבינטוריקה למדעי המחשב

פונקציות יוצרות

5 - פונקציות יוצרות

קומבינטוריקה למדעי המחשב

פונקציות יוצרות

שימוש פונקציות יוצרות בקומבינטוריקה

הוכחת זהויות קומבינטוריות

מציאת מספר פתרונות למשוואה

פתרון נוסחאת נסיגה

לסדרות כלליות

השיטות הלא שימושיות

פתרון ע"י פונקציה יוצרת

מקדמים קבועים

באמצעות פולינום אופייני