Method of distinguished element
عددی امتزاج کے ریاضیاتی میدان میں، شناخت بعض اوقات ان دلائل کے ذریعے قائم کی جاتی ہیں جو کسی سیٹ کے ایک "ممتاز عنصر" کو الگ کرنے پر انحصار کرتے ہیں۔ تعریف سیٹ کے ذیلی سیٹوں کا ایک خاندان ہونے دیں اور سیٹ کا ایک ممتاز عنصر ہونے دیں۔ پھر فرض کریں کہ کوئی پیش گوئی ہے جو کسی ذیلی سیٹ سے متعلق ہے۔ ذیلی مجموعوں کے اس مجموعے کو ظاہر کریں جس کے لیے صحیح ہے اور ذیلی مجموعوں کا مجموعہ جس کے لیے غلط ہے، پھر اور جداگانہ مجموعے ہیں، اس لیے خلاصہ کے طریقہ کار کے مطابق، کارڈینالیٹیز اضافی ہوتی ہیں۔ اس طرح ممتاز عنصر ایک پیش گوئی کے مطابق سڑنے کی اجازت دیتا ہے جو کہ تقسیم اور فتح الگورتھم کی ایک سادہ شکل ہے۔ امتزاج میں، یہ تکرار کے تعلقات کی تعمیر کی اجازت دیتا ہے۔ مثالیں اگلے حصے میں ہیں۔ مثال بائنومیل گتانک سائز-n سیٹ کے سائز-k ذیلی سیٹوں کی تعداد ہے۔ ایک بنیادی شناخت-جس کے نتائج میں سے ایک یہ ہے کہ بائنومیل کوفیشنٹس بالکل وہی نمبر ہیں جو پاسکل کے مثلث میں ظاہر ہوتے ہیں-بیان کرتا ہے کہ: ثبوت: سائز-(n + 1) سیٹ میں، ایک ممتاز عنصر کا انتخاب کریں۔ تمام سائز-کے ذیلی سیٹوں کے سیٹ پر مشتمل ہے: (1) تمام سائز-کے ذیلی سیٹیں جن میں ممتاز عنصر ہوتا ہے، اور (2) تمام سائز-کے ذیلی سیٹیں جن میں ممتاز عنصر نہیں ہوتا ہے۔ اگر کسی سائز-(n + 1) سیٹ کے سائز-k ذیلی سیٹ میں ممتاز عنصر موجود ہے، تو اس کے دیگر k-1 عناصر کو ہمارے سائز-(n + 1) سیٹ کے دیگر n عناصر میں سے منتخب کیا جاتا ہے۔ لہذا ان کو منتخب کرنے کے طریقوں کی تعداد ہے۔ اگر سائز-k ذیلی سیٹ میں ممتاز عنصر نہیں ہوتا ہے، تو اس کے تمام k اراکین کو دوسرے n "غیر ممتاز" عناصر میں سے منتخب کیا جاتا ہے۔ لہذا ان کو منتخب کرنے کے طریقوں کی تعداد ہے۔ کسی بھی سائز-n سیٹ کے ذیلی سیٹوں کی تعداد 2n ہے۔ ثبوت: ہم ریاضیاتی انڈکشن کا استعمال کرتے ہیں۔ انضمام کی بنیاد n = 0 کی صورت میں اس تجویز کی سچائی ہے۔ خالی سیٹ میں 0 ممبران اور 1 سب سیٹ، اور 20 = 1 ہوتا ہے۔ انڈکشن مفروضہ صورت n میں تجویز ہے ؛ ہم اسے صورت n + 1 کو ثابت کرنے کے لیے استعمال کرتے ہیں۔ سائز-(n + 1) سیٹ میں، ایک ممتاز عنصر کا انتخاب کریں۔ ہر ذیلی سیٹ یا تو ممتاز عنصر پر مشتمل ہوتا ہے یا نہیں۔ اگر کسی ذیلی سیٹ میں ممتاز عنصر موجود ہے، تو اس کے بقیہ عناصر کو دوسرے n عناصر میں سے منتخب کیا جاتا ہے۔ انڈکشن مفروضے کے مطابق، ایسا کرنے کے طریقوں کی تعداد 2n ہے۔ اگر کسی ذیلی سیٹ میں ممتاز عنصر نہیں ہے، تو یہ تمام غیر ممتاز عناصر کے سیٹ کا ذیلی سیٹ ہے۔ انڈکشن مفروضے کے مطابق، اس طرح کے ذیلی مجموعوں کی تعداد 2n ہے۔ آخر میں، ہمارے سائز-(n + 1) سیٹ کے ذیلی سیٹوں کی پوری فہرست 2n + 2n = 2n + 1 عناصر پر مشتمل ہے۔ فرض کریں کہ Bn n واں گھنٹی نمبر ہے، یعنی n اراکین کے سیٹ کی پارٹیشنوں کی تعداد۔ مان لیں کہ Cn اس سیٹ کے تمام پارٹیشنوں میں "پارٹس" (یا "بلاکس"، جیسا کہ مشترکہ ماہرین اکثر انہیں کہتے ہیں) کی کل تعداد ہے۔ مثال کے طور پر، سائز-3 سیٹ {a, b, c} کی پارٹیشنز کو اس طرح لکھا جا سکتا ہے: ہم 5 پارٹیشنز دیکھتے ہیں، جن میں 10 بلاکس ہوتے ہیں، لہذا B3 = 5 اور C3 = 10۔ شناخت میں کہا گیا ہے: ثبوت: سائز-(n + 1) سیٹ میں، ایک ممتاز عنصر کا انتخاب کریں۔ ہمارے سائز-(n + 1) سیٹ کے ہر پارٹیشن میں، یا تو ممتاز عنصر "سنگلٹن" ہوتا ہے، یعنی صرف ممتاز عنصر پر مشتمل سیٹ بلاکس میں سے ایک ہوتا ہے، یا ممتاز عنصر کا تعلق کسی بڑے بلاک سے ہوتا ہے۔ اگر ممتاز عنصر سنگلٹن ہے، تو ممتاز عنصر کو حذف کرنے سے سیٹ کا ایک حصہ نکل جاتا ہے جس میں n غیر ممتاز عناصر ہوتے ہیں۔ ایسا کرنے کے Bn طریقے ہیں۔ اگر ممتاز عنصر کا تعلق کسی بڑے بلاک سے ہے، تو اس کا حذف ہونا سیٹ کی تقسیم میں ایک بلاک چھوڑ دیتا ہے جس میں n غیر ممتاز عناصر ہوتے ہیں۔ ایسے سی این بلاکس ہیں۔ مشترکہ اصول مشترکہ ثبوت حوالہ جات مشترکہ ریاضیاتی اصول بھی دیکھیں۔