היי לכולם, אשמח לקבל עזרה עם השאלה הבאה:
כמה עצים (לא מכוונים) פורשים n צמתים שונים כך שלאף צומת אין דרגה ששווה ל-2?
אני חושב שצריך להשתמש בעקרון הכלה והפרדה אבל לא בטוח כיצד.
תודה לכולם על העזרה
היי לכולם, אשמח לקבל עזרה עם השאלה הבאה:
כמה עצים (לא מכוונים) פורשים n צמתים שונים כך שלאף צומת אין דרגה ששווה ל-2?
אני חושב שצריך להשתמש בעקרון הכלה והפרדה אבל לא בטוח כיצד.
תודה לכולם על העזרה
היי גלעד, אכן צריך להשתמש בעקרון ההכלה והפרדה.
נתאים את הבעיה למילת פרופר ונפתור בעזרת עקרון הכלה והפרדה:
עולם: כל המילים באורך n-2 מעל אלפבית \{1,...,n\} ולכן W(0)=n^{n-2}.
תכונות: יהיו n תכונות רעות כך שמשמעות תכונה p_{i} היא שהאות 1\leq i\leq n מופיעה במילה בדיוק פעם אחת.
יעד: מאחר ומדובר בתכונות רעות, עלינו למצוא את E(0).
נניח כי r תכונות מתקיימות ולכן r צמתים מופיעים בדיוק פעם אחת במילת פרופר המתאימה. נבחר להן את המקומות במילה ב-P_{n-2}^{r} אפשרויות. כעת נותר לשבץ את יתר n-r האותיות ביתר n-2-r המקומות. לכל מקום יש n-r אפשרויות ולכן PP_{n-r}^{n-r-2}. סה"כ נקבל:
אי-לכך נקבל:
מקווה שמובן