Labelled enumeration theorem
संयोजी गणित में, लेबल किया गया गणना प्रमेय लेबल किए गए मामले के लिए पोल्या गणना प्रमेय का समकक्ष है, जहां हमारे पास एक घातीय उत्पादन फलन (ईजीएफ) जी (जेड) द्वारा दी गई लेबल की गई वस्तुओं का एक समूह है जिसे एन स्लॉट में वितरित किया जा रहा है और एक क्रमपरिवर्तन समूह जी जो स्लॉट को क्रमबद्ध करता है, इस प्रकार विन्यास के समतुल्य वर्ग बनाता है। एक विशेष री-लेबलिंग ऑपरेशन है जो स्लॉट में वस्तुओं को फिर से लेबल करता है, 1 से k तक लेबल निर्धारित करता है, जहां k नोड्स की कुल संख्या है, यानी। अलग-अलग वस्तुओं के नोड्स की संख्या का योग। इस पुनः लेबलिंग प्रक्रिया के तहत विभिन्न विन्यासों की संख्या का ई. जी. एफ. विशेष रूप से इस प्रकार दिया जाता है, यदि जी n क्रम का सममित समूह है (इसलिए, |G। = n! ), कार्यों को आगे एकल उत्पन्न करने वाले कार्य में जोड़ा जा सकता हैः जो घातीय डब्ल्यू. आर. टी. है। चर जेड और साधारण डब्ल्यू. आर. टी. चर टी. पुनः लेबलिंग प्रक्रिया हम मानते हैं कि आकार की किसी वस्तु में लेबल वाले आंतरिक नोड्स होते हैं, जिसमें लेबल 1 से मीटर तक जाते हैं। बिना लेबल वाले मामले की तुलना में स्लॉट पर जी की क्रिया बहुत सरल होती है, क्योंकि लेबल स्लॉट में वस्तुओं को अलग करते हैं, और जी के नीचे की कक्षाओं का आकार समान होता है। (ई. जी. एफ. जी. (जेड) में शून्य आकार की वस्तुएँ शामिल नहीं हो सकती हैं। ऐसा इसलिए है क्योंकि वे लेबल द्वारा अलग नहीं किए जाते हैं और इसलिए ऐसी दो या दो से अधिक वस्तुओं की उपस्थिति से ऐसी कक्षाएँ बनती हैं जिनका आकार उनसे कम होता है।) जैसा कि उल्लेख किया गया है, वस्तुओं के नोड्स को फिर से लेबल किया जाता है जब उन्हें स्लॉट में वितरित किया जाता है। मान लीजिए कि आकार की एक वस्तु पहले स्लॉट में जाती है, आकार की एक वस्तु दूसरे स्लॉट में, और इसी तरह, और विन्यास का कुल आकार k है, ताकि पुनः लेबलिंग प्रक्रिया निम्नानुसार काम करेः के लेबल के सेट के विभाजनों में से एक को आकार के सबसेट में चुनें अब प्रत्येक वस्तु के आंतरिक नोड्स को संबंधित सबसेट से लेबल का उपयोग करके फिर से लेबल करें, लेबल के क्रम को संरक्षित करें। ई. जी. यदि पहली वस्तु में 1 से 4 तक लेबल किए गए चार नोड हैं और इस वस्तु के लिए चुने गए लेबल का सेट {2,5,6,10} है, तो नोड 1 लेबल 2, नोड 2, लेबल 5, नोड 3, लेबल 6 और नोड 4, लेबल 10 प्राप्त करता है। इस तरह वस्तुओं पर लगे लेबल वस्तु के लिए चुने गए उपसमुच्चय से लेबल का उपयोग करके एक अद्वितीय लेबलिंग को प्रेरित करते हैं। प्रमेय का प्रमाण यह पुनः-लेबलिंग संरचना से पता चलता है कि कुल आकार k के विभिन्न विन्यास हैं या हैं। सूत्र एक पूर्णांक का मूल्यांकन करता है क्योंकि k <n के लिए शून्य है (याद रखें कि g में आकार शून्य की वस्तुएं शामिल नहीं हैं) और जब हमारे पास है और G का क्रम के क्रम को विभाजित करता है, जो कि लैग्रेंज की प्रमेय द्वारा है। निष्कर्ष यह है कि लेबल किए गए विन्यासों का ई. जी. एफ. इस सूत्र द्वारा दिया गया है जिसे अनुक्रमों की गणना करके भी प्राप्त किया जा सकता है, अर्थात। मामला जब स्लॉट को क्रमबद्ध नहीं किया जा रहा है, और-कारक के बिना उपरोक्त तर्क का उपयोग करके यह दिखाने के लिए कि पुनः लेबलिंग के तहत उनका उत्पादन कार्य इसके द्वारा दिया गया है। अंत में ध्यान दें कि प्रत्येक अनुक्रम आकार की एक कक्षा से संबंधित है, इसलिए कक्षाओं का उत्पादन कार्य संदर्भ फ्रांस्वा बर्गेरॉन, गिल्बर्ट लेबल, पियरे लेरॉक्स, थियोरी डेस एस्पेस एट कॉम्बिनेटायर डेस स्ट्रक्चर्स आर्बोरेसेंटस, एलएसीआईएम, मॉन्ट्रियल (1994) द्वारा दिया गया है। अंग्रेजी संस्करणः संयुक्त प्रजातियाँ और पेड़ जैसी संरचनाएँ, कैम्ब्रिज यूनिवर्सिटी प्रेस (1998)। एन्यूमरेटिव कॉम्बिनेटोरिक्स कॉम्बिनेटोरिक्स में प्रमेय प्रमाण वाले लेख