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

פונקציה יוצרת של סדרת מספרים $a_{n}$ היא טור החזקות שלה: $\displaystyle f(x)=\sum_{n=0}^\infty a_{n}x^n$ .

דוגמה

נניח ויש לנו את הסדרה $1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,\dots$
אזי, הפונקציה היוצרת שנוצרת ממנה היא:

f(x)=\sum_{n=0}^\infty x^n = \frac{1}{1-x} \;\;\;where\;\; |x|<1

שזהו טור הנדסי.

דוגמה

נניח ויש לנו את הסדרה $\begin{pmatrix}n \\0\end{pmatrix},\begin{pmatrix}n\\ 1\end{pmatrix},\begin{pmatrix}n\\ 2\end{pmatrix},\dots,\begin{pmatrix}n\\ n\end{pmatrix},0,0,0,0,\dots$
נרצה לראות את הפונקציה היוצרת שלה:

f(x)=\sum_{i=0}^\infty b_{i}x^i=\sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix}x^i\cdot 1^{n-i} \underset{\begin{matrix} \downarrow \\ \R{\text{הבינום של ניוטון}} \end{matrix}}{=}(x+1)^n

הערה

גם אם הסכום בסוף הוא סופי, נדרש להתחיל מטור אינסופי שכן זוהי ההגדרה של פונקציה יוצרת.

תרגיל

כמה פתרונות יש למשוואה $t_{1}+t_{2}+t_{3}=30$ כאשר $t_{1},t_{3}$ אי זוגיים, $t_{2}$ זוגי ומתקיים $t_{1}\geq 1,\;t_{2}\geq 4,\; t_{3}\geq 7$ .

תחילה נסמן:

t_{1}'=t_{1}-1 \qquad \qquad t_{2}'=t_{2}-4 \qquad \qquad t_{3}'=t_{3}-7

ואז הבעיה החדשה שלנו תהיה:

t_{1}'+t_{2}'+t_{3}'=30-1-4-7=18

כאשר $t_{1}',t_{2}',t_{3}'$ זוגיים.
מספר הפתרונות של המשוואה הזו הוא $\mathbb{C}_{3}^{\frac{18}{2}}$ .

כעת, נפתור את אותה הבעיה באמצעות פונקציות יוצרות:
הפתרון הוא המקדם של $x^{30}$ בפונקציה הבאה:

\begin{align*} f(x)&=(x+x^3+x^5+\dots)(x^4+x^6+x^8+\dots)(x^7+x^9+x^{11}+\dots) \\ &=x\cdot x^4\cdot x^7(1+x^2+x^4+\dots)^3=x^{12} \frac{1}{(1-x^2)^3} \end{align*}

ע"י שימוש בנוסחה ממקודם:

x^{12}\sum_{k=0}^\infty \mathbb{C}_{3}^k x^{2k}=\sum_{k=0}^\infty \mathbb{C}_{3}^k x^{2k+12}

$x^{30}$ מתקבל כאשר $k=9$ והמקדם הוא $\mathbb{C}_{3}^9$ וזוהי גם התשובה.

[להשלים תרגיל]

הבסיס לתורת הגרפים

תרגיל

כמה גרפים עם $n$ צמתים שונים ו- $m$ קשתות קיימים כאשר:

הגרפים לא מכוונים ופשוטים כאשר הקשתות זהות
הגרפים לא מכוונים ופשוטים כאשר הקשתות שונות
הגרפים לא מכוונים כאשר הקשתות זהות
הגרפים לא מכוונים כאשר הקשתות שונות
הגרפים מכוונים ופשוטים כאשר הקשתות זהות
הגרפים מכוונים ופשוטים כאשר הקשתות שונות
הגרפים מכוונים כאשר הקשתות זהות
הגרפים מכוונים כאשר הקשתות שונות

נבנה את הטבלה:

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline & & & & \R{\text{קשתות זהות}} \\ \hline & & & & \R{\text{קשתות שונות}} \\ \hline \end{array}

ונמלא אותה.

עבור גרף לא מכוון ופשוט, כל קשת מחברת בין שני הצמתים. מספר הקשתות החוקיות בגרף שווה למספר הדרכים לבחור שני ערכים בלי חשיבות לסדר(כי זה גרף לא מכוון) ובלי חזרות(כי הגרף פשוט ללא לולאות עצמיות) ולכך יש לנו $\begin{pmatrix}n \\ 2\end{pmatrix}$ אפשרויות. כלומר, יש לנו קבוצה של $\begin{pmatrix}n\\ 2\end{pmatrix}$ קשתות זהות.
כעת, נדרש לבחור $m$ קשתות מתוך הקבוצה.
אם יש סדר בבחירה אז הקשתות שונות ואם אין סדר בבחירה הקשתות שונות.
אם אין לנו חזרות, אזי לא יהיו לנו קשתות מקבילות ואם נבחר עם חזרות, אז יהיו לנו קשתות מקבילות.
לכן, למקרה שלנו נבחר בלי סדר ובלי חזרות ולכן יש לנו בחירה של $m$ מתוך $\begin{pmatrix}n \\ 2\end{pmatrix}$ בלי חשיבות לסדר ובלי חזרות ולכך יש לנו $\begin{pmatrix}\begin{pmatrix}n\\ 2\end{pmatrix}\\ m\end{pmatrix}$ אפשרויות.
לבחירה עם חשיבות לסדר ובלי חזרות נקבל כי יש לנו $P_{\begin{pmatrix}n\\ 2\end{pmatrix}}^{m}=\begin{pmatrix}\begin{pmatrix}n\\ 2\end{pmatrix} \\ m\end{pmatrix}m!$ שכן הקשתות בהכרח שונות.

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline & & & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix} & \R{\text{קשתות זהות}} \\ \hline & & & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix}m! & \R{\text{קשתות שונות}} \\ \hline \end{array}

[המתרגל לא עשה את השאר אבל לפי דף התרגול נקבל את הטבלה:]

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline \begin{pmatrix} m+n^2-1 \\ m \end{pmatrix} & \begin{pmatrix} n(n-1) \\ m \end{pmatrix} & \begin{pmatrix} m+\begin{pmatrix} n+1 \\ 2 \end{pmatrix}-1 \\ m \end{pmatrix} & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix} & \R{\text{קשתות זהות}} \\ \hline (n^2)^m & \begin{pmatrix} n(n-1) \\ m \end{pmatrix}m! & \begin{pmatrix} n+1 \\ 2 \end{pmatrix}^m & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix}m! & \R{\text{קשתות שונות}} \\ \hline \end{array}

או בהצגה אלגנטית יותר:

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline \mathbb{C}_{\mathbb{P}_{n}^2}^m & C_{P_{n}^2}^m & \mathbb{C}_{\mathbb{C}_{n}^2}^m & C_{C_{n}^2}^m & \R{\text{קשתות זהות}} \\ \hline \mathbb{P}_{\mathbb{P}_{n}^2}^m & P_{P_{n}^2}^m & \mathbb{P}_{\mathbb{C}_{n}^2}^m & P_{C_{n}^2}^m & \R{\text{קשתות שונות}} \\ \hline \end{array}

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

פונקציה יוצרת של סדרת מספרים $a_{n}$ היא טור החזקות שלה: $\displaystyle f(x)=\sum_{n=0}^\infty a_{n}x^n$ .

דוגמה

f(x)=\sum_{n=0}^\infty x^n = \frac{1}{1-x} \;\;\;where\;\; |x|<1

שזהו טור הנדסי.

דוגמה

f(x)=\sum_{i=0}^\infty b_{i}x^i=\sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix}x^i\cdot 1^{n-i} \underset{\begin{matrix} \downarrow \\ \R{\text{הבינום של ניוטון}} \end{matrix}}{=}(x+1)^n

הערה

גם אם הסכום בסוף הוא סופי, נדרש להתחיל מטור אינסופי שכן זוהי ההגדרה של פונקציה יוצרת.

תרגיל

כמה פתרונות יש למשוואה $t_{1}+t_{2}+t_{3}=30$ כאשר $t_{1},t_{3}$ אי זוגיים, $t_{2}$ זוגי ומתקיים $t_{1}\geq 1,\;t_{2}\geq 4,\; t_{3}\geq 7$ .

תחילה נסמן:

t_{1}'=t_{1}-1 \qquad \qquad t_{2}'=t_{2}-4 \qquad \qquad t_{3}'=t_{3}-7

ואז הבעיה החדשה שלנו תהיה:

t_{1}'+t_{2}'+t_{3}'=30-1-4-7=18

כאשר $t_{1}',t_{2}',t_{3}'$ זוגיים.
מספר הפתרונות של המשוואה הזו הוא $\mathbb{C}_{3}^{\frac{18}{2}}$ .

כעת, נפתור את אותה הבעיה באמצעות פונקציות יוצרות:
הפתרון הוא המקדם של $x^{30}$ בפונקציה הבאה:

\begin{align*} f(x)&=(x+x^3+x^5+\dots)(x^4+x^6+x^8+\dots)(x^7+x^9+x^{11}+\dots) \\ &=x\cdot x^4\cdot x^7(1+x^2+x^4+\dots)^3=x^{12} \frac{1}{(1-x^2)^3} \end{align*}

ע"י שימוש בנוסחה ממקודם:

x^{12}\sum_{k=0}^\infty \mathbb{C}_{3}^k x^{2k}=\sum_{k=0}^\infty \mathbb{C}_{3}^k x^{2k+12}

$x^{30}$ מתקבל כאשר $k=9$ והמקדם הוא $\mathbb{C}_{3}^9$ וזוהי גם התשובה.

[להשלים תרגיל]

הבסיס לתורת הגרפים

תרגיל

כמה גרפים עם $n$ צמתים שונים ו- $m$ קשתות קיימים כאשר:

הגרפים לא מכוונים ופשוטים כאשר הקשתות זהות
הגרפים לא מכוונים ופשוטים כאשר הקשתות שונות
הגרפים לא מכוונים כאשר הקשתות זהות
הגרפים לא מכוונים כאשר הקשתות שונות
הגרפים מכוונים ופשוטים כאשר הקשתות זהות
הגרפים מכוונים ופשוטים כאשר הקשתות שונות
הגרפים מכוונים כאשר הקשתות זהות
הגרפים מכוונים כאשר הקשתות שונות

נבנה את הטבלה:

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline & & & & \R{\text{קשתות זהות}} \\ \hline & & & & \R{\text{קשתות שונות}} \\ \hline \end{array}

ונמלא אותה.

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline & & & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix} & \R{\text{קשתות זהות}} \\ \hline & & & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix}m! & \R{\text{קשתות שונות}} \\ \hline \end{array}

[המתרגל לא עשה את השאר אבל לפי דף התרגול נקבל את הטבלה:]

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline \begin{pmatrix} m+n^2-1 \\ m \end{pmatrix} & \begin{pmatrix} n(n-1) \\ m \end{pmatrix} & \begin{pmatrix} m+\begin{pmatrix} n+1 \\ 2 \end{pmatrix}-1 \\ m \end{pmatrix} & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix} & \R{\text{קשתות זהות}} \\ \hline (n^2)^m & \begin{pmatrix} n(n-1) \\ m \end{pmatrix}m! & \begin{pmatrix} n+1 \\ 2 \end{pmatrix}^m & \begin{pmatrix} \begin{pmatrix} n \\ 2 \end{pmatrix} \\ m \end{pmatrix}m! & \R{\text{קשתות שונות}} \\ \hline \end{array}

או בהצגה אלגנטית יותר:

\begin{array}{|c|c|c|c|c|} \hline \R{\text{מכוון}} & \R{\text{מכוון ופשוט}} & \R{\text{לא מכוון}} & \R{\text{לא מכוון ופשוט}} \\ \hline \mathbb{C}_{\mathbb{P}_{n}^2}^m & C_{P_{n}^2}^m & \mathbb{C}_{\mathbb{C}_{n}^2}^m & C_{C_{n}^2}^m & \R{\text{קשתות זהות}} \\ \hline \mathbb{P}_{\mathbb{P}_{n}^2}^m & P_{P_{n}^2}^m & \mathbb{P}_{\mathbb{C}_{n}^2}^m & P_{C_{n}^2}^m & \R{\text{קשתות שונות}} \\ \hline \end{array}

9+10 - פונקציות יוצרות והבסיס לתורת הגרפים

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

9+10 - פונקציות יוצרות והבסיס לתורת הגרפים

9+10 - פונקציות יוצרות והבסיס לתורת הגרפים

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

9+10 - פונקציות יוצרות והבסיס לתורת הגרפים

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

הבסיס לתורת הגרפים

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

הבסיס לתורת הגרפים