היי לכולם, אשמח לעזרה עם השאלה הבאה בנושא גרפים:
כמה יערות לא מסודרים עם 2 עצים מכוונים וסה"כ n צמתים הממוספרים 1,2,...,n קיימים?
האם אני צריך להפריד למקריים זרים? כיצד אני סופר את המקריים?
היי גלעד,
נפריד למקריים זרים לפי כמות הצמתים שמכיל עץ ראשון. נסמן מספר זה ב- 1\leq k\leq n-1. נבחר את k הצמתים אשר יהיו בעץ הראשון ב- C_{n}^{k} אפשרויות. ע"פ קיילי נקבל k^{k-2} אפשרויות. עבור העץ השני (אשר מכיל n-k צמתים) יש (n-k)^{n-k-2} אפשרויות. נכוון את העץ הראשון ע"י בחירת שורש ב-k אפשרויות. כמו כן, נכוון את העץ השני ע"י בחירת שורש ב-(n-k) אפשרויות. אין משמעות לסדר בין העצים ולכן נחלק ב-2. ע"פ עקרון הכפל נקבל:
\frac{1}{2}\cdot C_{n}^{k}\cdot k^{k-2}\cdot(n-k)^{n-k-2}\cdot k\cdot(n-k)=\frac{1}{2}\cdot C_{n}^{k}\cdot k^{k-1}\cdot(n-k)^{n-k-1}
מאחר ומדובר במקריים זרים, נסכום ע"פ עקרון החיבור:
\frac{1}{2}\cdot\sum_{k=1}^{n-1}C_{n}^{k}\cdot k^{k-1}\cdot(n-k)^{n-k-1}
מקווה שמובן 