Labelled enumeration theorem
مشترکہ ریاضی میں، لیبل شدہ گنتی تھیوریم لیبل شدہ کیس کے لیے پولیا گنتی تھیوریم کا ہم منصب ہے، جہاں ہمارے پاس لیبل شدہ اشیاء کا ایک مجموعہ ہے جو ایک ایکسپونینشیل جنریٹنگ فنکشن (ای جی ایف) جی (زیڈ) کے ذریعے دیا گیا ہے جسے این سلاٹس میں تقسیم کیا جا رہا ہے اور ایک پرموٹیشن گروپ جی جو سلاٹس کو پرموٹ کرتا ہے، اس طرح ترتیبات کی مساوات کی کلاسیں پیدا کرتا ہے۔ ایک خاص دوبارہ لیبلنگ آپریشن ہے جو سلاٹس میں موجود اشیاء کو دوبارہ لیبل کرتا ہے، 1 سے k تک لیبل تفویض کرتا ہے، جہاں k نوڈس کی کل تعداد ہے، یعنی۔ انفرادی اشیاء کے نوڈس کی تعداد کا مجموعہ۔ اس دوبارہ لیبلنگ کے عمل کے تحت مختلف ترتیبات کی تعداد کا ای جی ایف خاص طور پر، اگر جی ترتیب n کا سمیٹرک گروپ ہے (اس لیے، |G | = n! )، افعال کو مزید ایک واحد جنریٹنگ فنکشن میں جوڑا جا سکتا ہے: جو کہ ایکسپونینشل ڈبلیو آر ٹی ہے۔ متغیر زیڈ اور عام ڈبلیو آر ٹی۔ متغیر t۔ دوبارہ لیبلنگ کا عمل ہم فرض کرتے ہیں کہ سائز کی کسی شے کی نمائندگی کرنے والے لیبل والے اندرونی نوڈس پر مشتمل ہوتے ہیں، جن کے لیبل 1 سے میٹر تک جاتے ہیں۔ غیر لیبل والے کیس کے مقابلے میں سلاٹس پر G کا عمل بہت آسان ہوتا ہے، کیونکہ لیبل سلاٹس میں موجود اشیاء میں فرق کرتے ہیں، اور G کے نیچے مدار سب کا سائز ایک جیسا ہوتا ہے۔ (ای جی ایف جی (زیڈ) میں سائز صفر کی اشیاء شامل نہیں ہو سکتی ہیں۔ اس کی وجہ یہ ہے کہ وہ لیبل کے ذریعے ممتاز نہیں ہوتے ہیں اور اس لیے ایسی دو یا زیادہ اشیاء کی موجودگی ایسے مدار بناتی ہے جن کا سائز اس سے کم ہوتا ہے۔) جیسا کہ ذکر کیا گیا ہے، اشیاء کے نوڈس کو دوبارہ لیبل کیا جاتا ہے جب انہیں سلاٹس میں تقسیم کیا جاتا ہے۔ فرض کریں کہ سائز کی کوئی چیز پہلے سلاٹ میں جاتی ہے، سائز کی کوئی چیز دوسرے سلاٹ میں، اور اسی طرح، اور ترتیب کا کل سائز k ہے، تاکہ دوبارہ لیبلنگ کا عمل مندرجہ ذیل کام کرے: k لیبلز کے سیٹ کی پارٹیشن میں سے کسی ایک کو سائز کے ذیلی سیٹوں میں منتخب کریں اب ہر شے کے اندرونی نوڈس کو متعلقہ ذیلی سیٹ سے لیبلز کا استعمال کرتے ہوئے دوبارہ لیبل کریں، لیبلز کی ترتیب کو محفوظ رکھیں۔ ای۔ جی۔ اگر پہلے آبجیکٹ میں 1 سے 4 تک کے لیبل والے چار نوڈس ہوتے ہیں اور اس آبجیکٹ کے لیے منتخب کردہ لیبلز کا سیٹ {2,5,6,10} ہے، تو نوڈ 1 کو لیبل 2، نوڈ 2، لیبل 5، نوڈ 3، لیبل 6 اور نوڈ 4، لیبل 10 موصول ہوتا ہے۔ اس طرح اشیاء پر لگے لیبلز شے کے لیے منتخب کردہ ذیلی سیٹ سے لیبلز کا استعمال کرتے ہوئے ایک منفرد لیبلنگ کو جنم دیتے ہیں۔ نظریہ کا ثبوت یہ دوبارہ لیبلنگ کی تعمیر سے ملتا ہے کہ کل سائز k کی یا مختلف ترتیبات ہیں۔ فارمولہ ایک عدد کا اندازہ کرتا ہے کیونکہ k <n کے لیے صفر ہے (یاد رکھیں کہ g میں سائز صفر کی اشیاء شامل نہیں ہیں) اور جب ہمارے پاس ہے اور G کی ترتیب کی ترتیب کو تقسیم کرتا ہے، جو کہ لگرینج کے نظریہ سے ہے۔ نتیجہ یہ ہے کہ لیبل شدہ ترتیبات کا ای جی ایف اس کے ذریعے دیا جاتا ہے۔ یہ فارمولا ترتیبات کی گنتی کے ذریعے بھی حاصل کیا جا سکتا ہے، یعنی۔ اس صورت میں جب سلاٹس کو پرموٹ نہیں کیا جا رہا ہو، اور-فیکٹر کے بغیر مندرجہ بالا دلیل کا استعمال کرتے ہوئے یہ ظاہر کرنے کے لیے کہ دوبارہ لیبلنگ کے تحت ان کا جنریٹنگ فنکشن اس کے ذریعے دیا گیا ہے۔ آخر میں نوٹ کریں کہ ہر ترتیب کا تعلق سائز کے مدار سے ہے، اس لیے مداروں کی پیداواری تقریب حوالہ جات فرانکوئس برجرون، گلبرٹ لیبل، پیئر لیروکس، تھیوری ڈیس ایسپیسیس ایٹ کمبینٹوائر ڈیس اسٹرکچرز آربوریسینٹس، لاسیم، مونٹریال (1994) کے ذریعے دی گئی ہے۔ انگریزی ورژن: مشترکہ انواع اور درخت جیسی ساخت، کیمبرج یونیورسٹی پریس (1998)۔ اعدادوشمار کے امتزاج میں نظریہ ثبوت پر مشتمل مضامین