שלום לכולם,
כמה עצים פורשים ניתן לבנות על הצמתים \{1,2,\ldots,26\} שבהם לפחות 8 צמתים בעלי דרגה 4?
לא הצלחתי עם שאלה זו, אשמח לפתרון תוך כדי פירוט השלבים.
תודה מראש!
קיימת בייקציה בין קבוצת העצים הלא מכוונים המורכבים מ-n צמתים שונים לבין קבוצת המילים (הנקראים פרופר) באורך n-2 מעל האפלבית \{1,\ldots,n\}. הצמתים יופיעו במילת הפרופר כדרגתם פחות 1. לכן בהינתן קבוצת הצמתים \{1,2,\ldots,26\} שבהם לפחות 8 צמתים בעלי דרגה 4 נובע כי מילת הפרופר המתאימה באורך 24 ובה קיימים לפחות 8 תווים שנמצאים 3 פעמים כל אחד. נשים לב כי מתקיים 3\cdot 8=24 ולכן המילה מכילה בדיוק 8 תווים כך שכל אחד מהם מופיע 3 פעמים (שכן אין מקום לתווים נוספים). שאר הצמתים בגרף בעלי דרגה 1. נותר לבנות מילה באורך 24 שמכילה בדיוק 8 תווים כך שכל אחד מהם מופיע 3 פעמים. ע"פ המקדם המוליטנומי נקבל:
{ 24 \choose 3\, 3\, \ldots \, 3}=\frac{24!}{(3!)^8}