היי לכולם, אשמח לקבל עזרה עם השאלה הבאה:
כמה עצים (לא מכוונים) פורשים 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}. סה"כ נקבל:
W(p_{1},...,p_{r})=PP_{n-r}^{n-r-2}\cdot P_{n-2}^{r}\Rightarrow W(r)={n \choose r}\cdot PP_{n-r}^{n-r-2}\cdot P_{n-2}^{r}
אי-לכך נקבל:
E(0)=\sum_{r=0}^{n}(-1)^{r}\cdot W(r)=\sum_{r=0}^{n}(-1)^{r}\cdot{n \choose r}\cdot PP_{n-r}^{n-r-2}\cdot P_{n-2}^{r}
מקווה שמובן 
לייק 1