प्रूफर कोड का उपयोग करके दिए गए सबग्राफ के साथ लेबल वाले पेड़ों की संख्या।
समस्या का विवरण
मैं शीर्ष सेट के साथ पेड़ों की संख्या गिनना चाहता हूं $V$ = {1, 2, 3, ..., 10} जो है $\\$
पेड़ $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (1 - 2 - 3 जैसा दिखता है) एक सबग्राफ के रूप में।
इसलिए अगर मुझे सही तरीके से लगता है, तो मुझे एन कोने और 2 स्थिर किनारों के साथ लेबल वाले पेड़ों की संख्या खोजने की आवश्यकता है।
केली के फॉर्मूले से हैं $n^{n-2}$ n कोने वाले पेड़।
मेरा लेना यह है कि पेड़ -> प्रूफर कोड एल्गोरिथ्म इस पत्ते के माता-पिता के साथ सबसे छोटा पत्ता, अनुक्रम जोड़ रहा है और इस पत्ती और इसके साथ जुड़े किनारे को हटा रहा है। हमारे पास (2,2), (3,2), (1, 2) के कब्जे वाले हमारे प्रूफर अनुक्रम में दो स्लॉट होंगे। इनमें से एक बाद की शुरुआत हो सकती है$n-1$स्लॉट। अन्य स्लॉट्स का उपयोग किसी भी कोने में किया जा सकता है। तो हम प्राप्त करते हैं$3 \cdot (n-1) \cdot n^{n-4}$। लेकिन यह पूरी तरह से गलत है। मैंने एक निश्चित बढ़त के साथ कुछ परिचित समस्याओं के प्रमाण का उपयोग करने की कोशिश की, लेकिन मुझे यह समझने में समस्या है कि ऐसा लगता है ...
जवाब
उस पेड़ की कल्पना करो $T$( 3---2---1) लेबल वाले एकल शीर्ष पर अनुबंधित है$0$। वहां$8^6$ वर्टेक्स सेट पर लेबल वाले पेड़ $\{0,4,5,6,7,8,9,10\}$। के लिये$k=1,\ldots,7$, इनमें से कितने पेड़ वर्टेक्स करते हैं $0$ डिग्री है $k$?
शिखर $0$ दिखाता है $k-1$ इस तरह के एक पेड़ के Prüfer कोड में बार, और इनमें से प्रत्येक Prüfer कोड है $6$ स्लॉट्स, तो वहाँ हैं $\binom6{k-1}$ जगह के तरीके $k-1$कोड में शून्य। वहाँ तो हैं$7$ शेष में से प्रत्येक के लिए विकल्प $6-(k-1)=7-k$ स्लॉट्स, इसलिए पूरी तरह से हैं $\binom6{k-1}7^{7-k}$ ऐसे पेड़।
इनमें से प्रत्येक वर्कट सेट पर एक से अधिक पेड़ों से मेल खाती है $V$ जिसमें वृक्ष शामिल है $T$। विशेष रूप से, यदि शीर्ष$0$ डिग्री है $k$ इन पेड़ों में से एक में, इसे छोड़ने वाले प्रत्येक किनारे को तीनों में से किसी एक से जोड़ा जा सकता है $1,2$, तथा $3$ जब हम वर्टेक्स का विस्तार करते हैं $0$ सेवा $T$, इसलिए पेड़ का विस्तार होता है $3^k$ शीर्ष पर अलग पेड़ सेट $V$।
समेटना $k=1,\ldots,7$, हम पाते हैं कि पूरी तरह से हैं
$$\begin{align*} \sum_{k=1}^73^k\binom6{k-1}7^{7-k}&=\sum_{k=0}^6\binom6k3^{k+1}7^{6-k}\\ &=3\sum_{k=0}^6\binom6k3^k7^{6-k}\\ &=3(3+7)^6\\ &=3,000,000 \end{align*}$$
शीर्ष पर पेड़ सेट $V$ इसमें शामिल हैं $T$। (दंडात्मक कदम द्विपद प्रमेय का उपयोग करता है।)
यह विश्लेषण लेबल वाले पेड़ों की संख्या के लिए एक सूत्र में आसानी से सामान्यीकृत करता है $n$ वर्टिकल जिसमें एक विशिष्ट सबट्री होती है $T$ साथ में $m$ खड़ी है।