History of combinatorics
संयोजन विज्ञान के गणितीय क्षेत्र का अध्ययन कई प्राचीन समाजों में अलग-अलग डिग्री में किया गया था। यूरोप में इसका अध्ययन 13वीं शताब्दी ईस्वी में लियोनार्डो फिबोनाची के काम से शुरू होता है, जिसने अरब और भारतीय विचारों को महाद्वीप में पेश किया। आधुनिक युग में इसका अध्ययन जारी है। संयोजन तकनीकों का सबसे पहला अभिलिखित उपयोग रिंड पपाइरस की समस्या 79 से आता है, जो 16 वीं शताब्दी ईसा पूर्व का है। समस्या एक निश्चित ज्यामितीय श्रृंखला से संबंधित है, और 1s और 2s की रचनाओं की संख्या को गिनने की फिबोनाची की समस्या के समान है जो एक दिए गए कुल का योग है। ग्रीस में, प्लूटार्क ने लिखा कि चाल्सेडन के ज़ेनोक्रेट्स (396-314 BC) ने ग्रीक भाषा में संभव विभिन्न अक्षरों की संख्या की खोज की। क्रमपरिवर्तन और संयोजन में एक कठिन समस्या को हल करने के लिए यह रिकॉर्ड पर पहला प्रयास होगा। हालाँकि, दावा अविश्वसनीय हैः यह ग्रीस में संयोजन के कुछ उल्लेखों में से एक है, और उन्हें जो संख्या मिली, 1.002 × 10.12, वह अनुमान से कहीं अधिक है। बाद में, क्रिसिपस (तीसरी शताब्दी ईसा पूर्व) और हिप्पार्कस (दूसरी शताब्दी ईसा पूर्व) के बीच एक नाजुक गणनात्मक समस्या का तर्क, जिसे बाद में श्रोडर-हिप्पार्कस संख्याओं से संबंधित दिखाया गया था, का उल्लेख किया गया है। इस बात के भी प्रमाण हैं कि ओस्टोमैकियन में, आर्किमिडीज (तीसरी शताब्दी ईसा पूर्व) ने एक टाइलिंग पहेली के विन्यास पर विचार किया, जबकि अपोलोनिअस के खोए हुए कार्यों में कुछ संयुक्त हित मौजूद हो सकते हैं। भारत में, भगवती सूत्र में एक संयोजन समस्या का पहला उल्लेख था; समस्या यह थी कि एक, दो, तीन, आदि में स्वाद का चयन करने से स्वाद के कितने संभावित संयोजन संभव थे। छह अलग-अलग स्वादों (मीठा, तीखा, तीखा, खट्टा, नमक और कड़वा) के चयन से। भगवती भी पहला पाठ है जिसमें चयन कार्य का उल्लेख किया गया है। ईसा पूर्व दूसरी शताब्दी में, पिंगल ने चंदा सूत्र (जिसे चंदसूत्र भी कहा जाता है) में एक गणना समस्या को शामिल किया जिसमें पूछा गया था कि छह अक्षरों वाले मीटर को छोटे और लंबे नोटों से कितने तरीकों से बनाया जा सकता है। पिंगला ने उन मीटरों की संख्या पाई जिनमें लंबे नोट और छोटे नोट थे; यह द्विपद गुणांक खोजने के बराबर है। भगवती के विचारों को 850 ईस्वी में भारतीय गणितशास्त्री महावीर द्वारा सामान्यीकृत किया गया था, और छंद पर पिंगल के काम का विस्तार 1100 ईस्वी में भास्कर द्वितीय और हेमचंद्र द्वारा किया गया था। भास्कर सामान्यीकृत विकल्प कार्य की खोज करने वाले पहले ज्ञात व्यक्ति थे, हालाँकि ब्रह्मगुप्त को पहले से पता होगा। हेमचंद्र ने पूछा कि एक निश्चित लंबाई के कितने मीटर मौजूद हैं यदि एक लंबे नोट को एक छोटे नोट से दोगुना लंबा माना जाता है, जो कि फिबोनाची संख्याओं को खोजने के बराबर है। भविष्यवाणी की प्राचीन चीनी पुस्तक I चिंग एक हेक्साग्राम को छह रेखाओं की पुनरावृत्ति के साथ एक क्रमपरिवर्तन के रूप में वर्णित करती है जहां प्रत्येक रेखा दो अवस्थाओं में से एक हो सकती हैः ठोस या डैश। इस तरह से षट्कोणों का वर्णन करते हुए वे निर्धारित करते हैं कि संभावित षट्कोण हैं। एक चीनी भिक्षु ने भी 700 ईस्वी के आसपास गो के समान खेल के विन्यास की संख्या को गिना होगा। हालाँकि चीन ने गणनात्मक संयोजन में अपेक्षाकृत कम प्रगति की थी, लेकिन लगभग 100 ईस्वी में उन्होंने लो शू स्क्वायर को हल किया जो ऑर्डर तीन के सामान्य जादू वर्ग की संयोजनात्मक डिजाइन समस्या है। जादू वर्ग चीन की रुचि बने रहे, और उन्होंने 900 और 1300 ईस्वी के बीच अपने मूल वर्ग को सामान्य बनाना शुरू कर दिया। चीन ने 13वीं शताब्दी में इस समस्या के बारे में मध्य पूर्व के साथ पत्राचार किया। मध्य पूर्व ने भारतीय कार्य से द्विपद गुणांक के बारे में भी सीखा और बहुपद विस्तार से संबंध पाया। हिंदुओं के काम ने अरबों को प्रभावित किया जैसा कि अल-खलील इब्न अहमद के काम में देखा गया है, जिन्होंने अक्षरों की संभावित व्यवस्था को शब्दांश बनाने के लिए माना था। उनकी गणना क्रमपरिवर्तन और संयोजन की समझ को दर्शाती है। अरब गणितशास्त्री उमर अल-खयामी के 1100 के आसपास के काम के एक अंश में, यह पुष्टि की गई है कि हिंदुओं को द्विपद गुणांक का ज्ञान था, लेकिन यह भी कि उनके तरीके मध्य पूर्व तक पहुंच गए थे। अबू बकर इब्न मुहम्मद इब्न अल हुसैन अल-कराजी (c.953-1029) ने द्विपद प्रमेय और पास्कल के त्रिकोण पर लिखा। अल-समावल द्वारा बाद के उद्धरण से ज्ञात अब खोए हुए काम में, अल-कराजी ने गणितीय प्रेरण द्वारा तर्क के विचार को पेश किया। दार्शनिक और खगोलशास्त्री रब्बी अब्राहम इब्न एजरा (सी. 1140) ने दिव्य नाम के उच्चारण में पुनरावृत्तियों के साथ क्रमपरिवर्तनों को गिना। उन्होंने द्विपद गुणांक की समरूपता भी स्थापित की, जबकि एक बंद सूत्र बाद में 1321 में टैल्मुडिस्ट और गणितशास्त्री लेवी बेन गेर्सन (जिसे गेर्सोनाइड्स के नाम से जाना जाता है) द्वारा प्राप्त किया गया था। अंकगणितीय त्रिभुज-एक चित्रमय आरेख जो द्विपद गुणांकों के बीच संबंधों को दर्शाता है-को गणितविदों द्वारा 10वीं शताब्दी के ग्रंथों में प्रस्तुत किया गया था, और अंततः इसे पास्कल के त्रिभुज के रूप में जाना जाने लगा। बाद में, मध्ययुगीन इंग्लैंड में, कैम्पेनोलॉजी ने क्रमपरिवर्तन पर कुछ केली ग्राफों में हैमिल्टनियन चक्रों के रूप में जाने जाने वाले उदाहरण प्रदान किए। पश्चिमी संयोजन विज्ञान में संयोजन 13वीं शताब्दी में गणितविदों लियोनार्डो फिबोनाची और जॉर्डन डी नेमोर के माध्यम से यूरोप में आया था। फिबोनाची के लिबर अबासी ने कई अरबी और भारतीय विचारों को यूरोप में पेश किया, जिसमें फिबोनाची संख्या भी शामिल थी। जॉर्डनस त्रिभुज में द्विपद गुणांकों को व्यवस्थित करने वाले पहले व्यक्ति थे, जैसा कि उन्होंने डी अर्थमेटिका के प्रस्ताव 70 में किया था। यह मध्य पूर्व में भी 1265 में और चीन में 1300 के आसपास किया गया था। आज इस त्रिभुज को पास्कल का त्रिभुज कहा जाता है। अपना नाम रखने वाले त्रिभुज में पास्कल का योगदान इसके बारे में औपचारिक प्रमाणों पर उनके काम और पास्कल के त्रिभुज और संभावना के बीच उनके द्वारा किए गए संबंधों से आता है। डेनियल बर्नौली को भेजे गए एक पत्र से हमें पता चलता है कि लीबनिज़ 17वीं शताब्दी में विभाजन के गणितीय सिद्धांत का औपचारिक रूप से अध्ययन कर रहे थे, हालांकि कोई औपचारिक कार्य प्रकाशित नहीं किया गया था। लीबनिज़ के साथ मिलकर, पास्कल ने 1666 में डी आर्टे कॉम्बिनेटोरिया प्रकाशित किया जिसे बाद में पुनर्मुद्रित किया गया। लीबनिज़ की हाबिलिटेशन थीसिस डी आर्टे कॉम्बिनेटोरिया को 1666 में एक पुस्तक के रूप में प्रकाशित किया गया था और बाद में पास्कल और लीबनिज़ को आधुनिक कॉम्बिनेटोरिक्स के संस्थापक माना जाता है। पास्कल और लीबनिज़ दोनों ने समझा कि द्विपद विस्तार विकल्प फलन के बराबर था। यह धारणा कि बीजगणित और संयोजन विज्ञान मेल खाते हैं, डी मोइवर द्वारा विस्तारित किया गया था, जिन्होंने एक बहुपद का विस्तार पाया। डी मोइवर ने समावेशन-बहिष्करण के सिद्धांत का उपयोग करते हुए विसंगतियों के लिए सूत्र भी पाया, जो निकोलौस बर्नौली से अलग एक विधि है, जिन्होंने इसे पहले पाया था। डी मोइवर भी द्विपद गुणांक और भाज्य का अनुमान लगाने में कामयाब रहे, और उत्पन्न करने वाले कार्यों का आविष्कार करके फिबोनाची संख्याओं के लिए एक बंद रूप पाया। 18वीं शताब्दी में, यूलर ने संयोजन की समस्याओं और संभावना की कई समस्याओं पर काम किया जो संयोजन से जुड़ी हैं। यूलर जिन समस्याओं पर काम कर रहे थे उनमें नाइट्स टूर, ग्रीको-लैटिन स्क्वायर, यूलरियन नंबर और अन्य शामिल हैं। कोनिग्सबर्ग समस्या के सात पुलों को हल करने के लिए उन्होंने ग्राफ सिद्धांत का आविष्कार किया, जिससे टोपोलॉजी का निर्माण भी हुआ। अंत में, उन्होंने उत्पन्न करने वाले कार्यों का उपयोग करके विभाजन के साथ जमीन तोड़ दी। समकालीन संयोजन 19वीं शताब्दी में, आंशिक रूप से क्रमबद्ध सेट और जाली सिद्धांत का विषय डेडेकिंड, पियर्से और श्रोडर के काम में उत्पन्न हुआ। हालाँकि, यह 1967 में प्रकाशित अपनी पुस्तक लैटिस थ्योरी में गैरेट बिरखॉफ का मौलिक कार्य था, और जॉन वॉन न्यूमैन के काम ने वास्तव में विषयों को स्थापित किया। 1930 के दशक में, हॉल (1936) और वीसनर (1935) ने स्वतंत्र रूप से सामान्य मोबियस व्युत्क्रम सूत्र का उल्लेख किया। 1964 में, जियान-कार्लो रोटा की ऑन द फाउंडेशन ऑफ कॉम्बिनेटोरियल थ्योरी I। मोबियस फ़ंक्शंस के सिद्धांत ने पोजेट और जाली सिद्धांत को संयोजन विज्ञान में सिद्धांतों के रूप में पेश किया। रिचर्ड पी. स्टेनली ने मैट्रायड सिद्धांत में अपने काम के लिए, जीटा बहुपदों को पेश करने के लिए, यूलरियन स्थिति को स्पष्ट रूप से परिभाषित करने के लिए, रोटा और पीटर डौबिलेट के साथ द्विपद स्थिति के सिद्धांत को विकसित करने के लिए समकालीन संयोजन विज्ञान में एक बड़ा प्रभाव डाला है। पॉल एर्दोस ने इन योगदानों के लिए वुल्फ पुरस्कार जीतकर पूरी सदी में संयोजन में महत्वपूर्ण योगदान दिया। ।