שאלת מבחן במתמטיקה בדידה - אוניברסיטת תל אביב 2015 - קומבינטוריקה

פולינום $\sum_{k=0}^{n} a_k x^k$ נקרא $n$-מיוחד אם $a_n = 1$ ושורשיו היחידים הם $3$, $7$ ו-$10$ (כלומר: $3$, $7$ ו-$10$ הם שורשים שלו, ואין לו שורשים נוספים, גם לא מרוכבים). (א) (10 נק') כמה פולינומים $20$-מיוחדים קיימים? רמז: פרקו את הפולינומים למכפלה של פולינומים ממעלה ראשונה. (ב) (10 נק') לכל $n \in \mathbb{N}$ נגדיר את הקבוצות $S_n$ ו-$B_n$ באופן הבא: i. $S_n$ היא קבוצת משוואות הנסיגה ההומוגניות עם מקדמים קבועים מסדר $n$ שהפולינומים האופייניים שלהן הם $n$-מיוחדים. ii. $B_n$ היא התמונה של הפונקציה $f$, כאשר $f$ היא הפונקציה המתאימה לכל משוואה ב-$S_n$ את הבסיס שמספק האלגוריתם שנלמד בקורס עבור מרחב הפתרונות של משוואה זו. חשבו את $|B_{20}|$.

רמז: בסעיף (א) כל פולינום $n$-מיוחד מתפרק ל-$(x-3)^a(x-7)^b(x-10)^c$ עם $a+b+c=n$ ו-$a,b,c \geq 1$. בסעיף (ב) הבסיס נקבע לפי הריבויים של השורשים, ולכן הוא תלוי רק בשלישייה $(a,b,c)$.

פתרון: **(א)** פולינום $20$-מיוחד הוא מהצורה: $$p(x) = (x - 3)^a (x - 7)^b (x - 10)^c$$ כאשר $a + b + c = 20$ ו-$a, b, c \geq 1$ (כי כל אחד מ-$3, 7, 10$ חייב להיות שורש). זו בעיית **כדורים ותאים** (composition): מספר הפתרונות של $a + b + c = 20$ עם $a, b, c \geq 1$. בהצבת $a' = a-1, b' = b-1, c' = c-1$ (עם $a', b', c' \geq 0$) מקבלים $a' + b' + c' = 17$. מספר הפתרונות: $\binom{17 + 2}{2} = \binom{19}{2} = \boxed{171}$. **(ב)** הפולינום האופייני של משוואת נסיגה $n$-מיוחדת הוא $(x-3)^a(x-7)^b(x-10)^c$ עם $a+b+c = n$, $a,b,c \geq 1$. הבסיס שהאלגוריתם מספק למרחב הפתרונות נקבע על ידי השורשים והריבויים שלהם. עבור שורש $r$ עם ריבוי $m$, הפתרונות המתאימים הם: $$r^n, n \cdot r^n, n^2 \cdot r^n, \ldots, n^{m-1} \cdot r^n$$ לכן הבסיס נקבע **באופן יחיד** על ידי השלישייה $(a, b, c)$. שתי שלישיות שונות $(a_1, b_1, c_1) \neq (a_2, b_2, c_2)$ ייתנו בסיסים שונים. לכן $|B_{20}|$ שווה למספר השלישיות $(a, b, c)$ עם $a + b + c = 20$ ו-$a, b, c \geq 1$, שהוא: $$|B_{20}| = \binom{19}{2} = \boxed{171}$$