यह लेख गणित के एक विशेष खंड पर केंद्रित होगा जिसे कॉम्बिनेटरिक्स कहा जाता है। सूत्र, नियम, समस्या समाधान के उदाहरण - यह सब आप लेख को अंत तक पढ़कर यहाँ पा सकते हैं।
तो, यह खंड क्या है? कॉम्बिनेटरिक्स किसी भी वस्तु की गिनती के मुद्दे से संबंधित है। लेकिन इस मामले में, वस्तुएं प्लम, नाशपाती या सेब नहीं हैं, बल्कि कुछ और हैं। कॉम्बिनेटरिक्स हमें किसी घटना की संभावना खोजने में मदद करता है। उदाहरण के लिए, ताश खेलते समय, क्या प्रायिकता है कि प्रतिद्वंद्वी के पास तुरुप का पत्ता हो? या ऐसा ही एक उदाहरण - क्या प्रायिकता है कि आप बीस गेंदों के थैले से बिल्कुल सफेद हो जाएंगे? इस तरह के कार्यों के लिए हमें कम से कम गणित के इस खंड की मूल बातें जानने की जरूरत है।
संयुक्त विन्यास
कॉम्बीनेटरिक्स की बुनियादी अवधारणाओं और सूत्रों के मुद्दे को ध्यान में रखते हुए, हम कॉम्बीनेटरियल कॉन्फ़िगरेशन पर ध्यान नहीं दे सकते हैं। उनका उपयोग न केवल निर्माण के लिए किया जाता है, बल्कि विभिन्न संयोजन समस्याओं को हल करने के लिए भी किया जाता है। ऐसे मॉडलों के उदाहरण हैं:
- प्लेसमेंट;
- क्रमपरिवर्तन;
- संयोजन;
- संख्या संरचना;
- विभाजन संख्या।
हम पहले तीन के बारे में और अधिक विस्तार से बाद में बात करेंगे, लेकिन हम इस खंड में रचना और विभाजन पर ध्यान देंगे। जब वे एक निश्चित संख्या (जैसे, ए) की संरचना के बारे में बात करते हैं, तो उनका मतलब है कि संख्या को कुछ सकारात्मक संख्याओं के क्रमबद्ध योग के रूप में दर्शाया जाता है। और एक विभाजन एक अनियंत्रित योग है।
अनुभाग
इससे पहले कि हम सीधे कॉम्बिनेटरिक्स के फ़ार्मुलों पर जाएँ और समस्याओं पर विचार करें, यह इस तथ्य पर ध्यान देने योग्य है कि गणित के अन्य वर्गों की तरह, कॉम्बिनेटरिक्स के भी अपने उपखंड हैं। इनमें शामिल हैं:
- गणना;
- संरचनात्मक;
- चरम;
- रैम्सी सिद्धांत;
- संभाव्य;
- टोपोलॉजिकल;
- अनंत।
पहले मामले में, हम एन्यूमरेटिव कॉम्बिनेटरिक्स के बारे में बात कर रहे हैं, समस्याएँ अलग-अलग कॉन्फ़िगरेशन की गणना या गिनती पर विचार करती हैं जो सेट के तत्वों द्वारा बनाई जाती हैं। एक नियम के रूप में, इन सेटों पर कुछ प्रतिबंध लगाए गए हैं (अभेद्यता, अप्रभेद्यता, पुनरावृत्ति की संभावना, और इसी तरह)। और इन विन्यासों की संख्या की गणना जोड़ या गुणा के नियम का उपयोग करके की जाती है, जिसके बारे में हम थोड़ी देर बाद बात करेंगे। स्ट्रक्चरल कॉम्बिनेटरिक्स में ग्राफ़ और मैट्रोइड्स के सिद्धांत शामिल हैं। एक एक्सट्रीम कॉम्बिनेटरिक्स समस्या का एक उदाहरण है कि एक ग्राफ का सबसे बड़ा आयाम क्या है जो निम्नलिखित गुणों को संतुष्ट करता है… चौथे पैराग्राफ में, हमने रैमसे सिद्धांत का उल्लेख किया, जो यादृच्छिक विन्यास में नियमित संरचनाओं की उपस्थिति का अध्ययन करता है। संभाव्यकॉम्बिनेटरिक्स प्रश्न का उत्तर देने में सक्षम है - क्या संभावना है कि किसी दिए गए सेट में एक निश्चित संपत्ति है। जैसा कि आप अनुमान लगा सकते हैं, टोपोलॉजिकल कॉम्बिनेटरिक्स टोपोलॉजी में विधियों को लागू करता है। और अंत में, सातवां बिंदु - इन्फिनिटरी कॉम्बिनेटरिक्स कॉम्बिनेटरिक्स विधियों के अनंत सेटों के अनुप्रयोग का अध्ययन करता है।
जोड़ने का नियम
कॉम्बिनेटरिक्स के फ़ार्मुलों में, काफी सरल सूत्र मिल सकते हैं, जिनसे हम लंबे समय से परिचित हैं। एक उदाहरण योग नियम है। मान लीजिए हमें दो क्रियाएं (सी और ई) दी गई हैं, यदि वे परस्पर अनन्य हैं, तो क्रिया सी कई तरीकों से की जा सकती है (उदाहरण के लिए, ए), और क्रिया ई को बी-तरीकों से किया जा सकता है, फिर उनमें से कोई भी (सी) या ई) a + b तरीकों से किया जा सकता है।
सैद्धांतिक रूप से यह समझना काफी कठिन है, हम एक सरल उदाहरण से पूरी बात बताने की कोशिश करेंगे। आइए एक कक्षा में छात्रों की औसत संख्या लें - मान लें कि यह पच्चीस है। इनमें पंद्रह लड़कियां और दस लड़के हैं। कक्षा में प्रतिदिन एक परिचारक की नियुक्ति की जाती है। आज क्लास अटेंडेंट को असाइन करने के कितने तरीके हैं? समस्या का समाधान काफी सरल है, हम जोड़ नियम का सहारा लेंगे। कार्य का पाठ यह नहीं कहता है कि केवल लड़के या केवल लड़कियां ही ड्यूटी पर हो सकती हैं। इसलिए, यह पंद्रह लड़कियों या दस लड़कों में से कोई भी हो सकता है। योग के नियम को लागू करने पर, हमें एक काफी सरल उदाहरण मिलता है जिसे प्राथमिक विद्यालय का छात्र आसानी से सामना कर सकता है: 15 + 10। गणना करने के बाद, हमें उत्तर मिलता है: पच्चीस। यानी सिर्फ पच्चीस तरीके हैंआज के लिए एक ड्यूटी क्लास असाइन करें।
गुणा नियम
गुणन का नियम भी संयोजन के मूल सूत्रों के अंतर्गत आता है। आइए सिद्धांत से शुरू करते हैं। मान लीजिए कि हमें कई क्रियाएं करने की आवश्यकता है (ए): पहली क्रिया 1 तरीकों से की जाती है, दूसरी - 2 तरीकों से, तीसरी - 3 तरीकों से, और इसी तरह जब तक अंतिम क्रिया एक तरह से नहीं की जाती है। फिर ये सभी क्रियाएं (जिनमें से हमारे पास कुल हैं) एन तरीकों से की जा सकती हैं। अज्ञात एन की गणना कैसे करें? सूत्र इसमें हमारी मदद करेगा: N \u003d c1c2c3…ca.
फिर से, सिद्धांत में कुछ भी स्पष्ट नहीं है, आइए गुणन नियम को लागू करने के एक सरल उदाहरण पर चलते हैं। चलो पच्चीस लोगों की वही क्लास लेते हैं, जिसमें पंद्रह लड़कियां और दस लड़के पढ़ते हैं। सिर्फ इस बार हमें दो अटेंडेंट चुनने हैं। वे या तो केवल लड़के या लड़कियां हो सकते हैं, या एक लड़की वाला लड़का हो सकता है। हम समस्या के प्राथमिक समाधान की ओर मुड़ते हैं। हम पहले अटेंडेंट को चुनते हैं, जैसा कि हमने पिछले पैराग्राफ में तय किया था, हमें पच्चीस संभावित विकल्प मिलते हैं। ड्यूटी पर तैनात दूसरा व्यक्ति शेष लोगों में से कोई भी हो सकता है। हमारे पास पच्चीस छात्र थे, हमने एक को चुना, जिसका अर्थ है कि शेष चौबीस लोगों में से कोई भी दूसरा ड्यूटी पर हो सकता है। अंत में, हम गुणन नियम लागू करते हैं और पाते हैं कि दो परिचारकों को छह सौ तरीकों से चुना जा सकता है। हमें यह संख्या पच्चीस और चौबीस गुणा करने पर मिली है।
स्वैप
अब हम एक और कॉम्बिनेटरिक्स फॉर्मूला पर विचार करेंगे। लेख के इस भाग में, हमचलो क्रमपरिवर्तन के बारे में बात करते हैं। एक उदाहरण के साथ समस्या पर तुरंत विचार करें। चलो बिलियर्ड बॉल लेते हैं, हमारे पास उनमें से n-th नंबर है। हमें गणना करने की आवश्यकता है: उन्हें एक पंक्ति में व्यवस्थित करने के लिए कितने विकल्प हैं, अर्थात एक क्रमित सेट बनाने के लिए।
शुरू करते हैं, अगर हमारे पास बॉल्स नहीं हैं, तो हमारे पास जीरो प्लेसमेंट ऑप्शन भी हैं। और अगर हमारे पास एक गेंद है, तो व्यवस्था भी वही है (गणितीय रूप से, इसे इस प्रकार लिखा जा सकता है: Р1=1)। दो गेंदों को दो अलग-अलग तरीकों से व्यवस्थित किया जा सकता है: 1, 2 और 2, 1. इसलिए, Р2=2. तीन गेंदों को छह तरीकों से व्यवस्थित किया जा सकता है (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. और अगर ऐसी तीन गेंदें नहीं हैं, लेकिन दस या पंद्रह हैं? सभी संभावित विकल्पों को सूचीबद्ध करने के लिए बहुत लंबा है, तो कॉम्बिनेटरिक्स हमारी सहायता के लिए आता है। क्रमपरिवर्तन सूत्र हमें अपने प्रश्न का उत्तर खोजने में मदद करेगा। पीएन=एनपी (एन -1)। यदि हम सूत्र को सरल बनाने का प्रयास करते हैं, तो हमें प्राप्त होता है: Pn=n (n - 1) … 21. और यह पहली प्राकृत संख्याओं का गुणनफल है। ऐसी संख्या को भाज्य कहा जाता है, और इसे n! के रूप में दर्शाया जाता है
आइए समस्या पर विचार करें। नेता हर सुबह एक पंक्ति (बीस लोग) में अपनी टुकड़ी बनाता है। टुकड़ी में तीन सबसे अच्छे दोस्त हैं - कोस्त्या, साशा और लेशा। क्या संभावना है कि वे एक दूसरे के बगल में होंगे? प्रश्न का उत्तर खोजने के लिए, आपको परिणामों की कुल संख्या से "अच्छे" परिणाम की संभावना को विभाजित करने की आवश्यकता है। क्रमपरिवर्तन की कुल संख्या 20 है!=2.5 क्विंटल। "अच्छे" परिणामों की संख्या की गणना कैसे करें? मान लीजिए कि कोस्त्या, साशा और लेशा एक सुपरमैन हैं। फिर हमहमारे पास केवल अठारह विषय हैं। इस मामले में क्रमपरिवर्तन की संख्या 18=6.5 क्वाड्रिलियन है। इस सब के साथ, कोस्त्या, साशा और लेशा अपने अविभाज्य ट्रिपल में मनमाने ढंग से आपस में घूम सकते हैं, और यह 3 और है!=6 विकल्प। तो हमारे पास कुल 18 "अच्छे" नक्षत्र हैं! 3! हमें बस वांछित संभावना ढूंढनी है: (18!3!) / 20! जो लगभग 0.016 है। प्रतिशत में बदलने पर यह केवल 1.6% निकलता है।
आवास
अब हम एक और बहुत ही महत्वपूर्ण और आवश्यक कॉम्बिनेटरिक्स फॉर्मूला पर विचार करेंगे। आवास हमारा अगला मुद्दा है, जिस पर हमारा सुझाव है कि आप लेख के इस भाग में विचार करें। हम और अधिक जटिल होने जा रहे हैं। आइए मान लें कि हम संभावित क्रमपरिवर्तन पर विचार करना चाहते हैं, केवल पूरे सेट (एन) से नहीं, बल्कि एक छोटे से (एम) से। अर्थात्, हम m द्वारा n वस्तुओं के क्रमपरिवर्तन पर विचार करते हैं।
कॉम्बिनेटरिक्स के बेसिक फ़ार्मुलों को केवल कंठस्थ नहीं करना चाहिए, बल्कि समझना चाहिए। इस तथ्य के बावजूद कि वे अधिक जटिल हो जाते हैं, क्योंकि हमारे पास एक पैरामीटर नहीं, बल्कि दो हैं। मान लीजिए कि m \u003d 1, फिर A \u003d 1, m \u003d 2, फिर A \u003d n(n - 1)। यदि हम सूत्र को और सरल करते हैं और भाज्यों का उपयोग करके अंकन पर स्विच करते हैं, तो हमें एक संक्षिप्त सूत्र मिलता है: A \u003d n! / (एन - एम)!
संयोजन
हमने उदाहरण के साथ कॉम्बिनेटरिक्स के लगभग सभी बुनियादी सूत्रों पर विचार किया है। अब आइए कॉम्बिनेटरिक्स के मूल पाठ्यक्रम पर विचार करने के अंतिम चरण पर चलते हैं - संयोजन को जानना। अब हम अपने पास मौजूद n में से m आइटम चुनेंगे, जबकि हम उन सभी को हर संभव तरीके से चुनेंगे। फिर यह आवास से किस प्रकार भिन्न है? हम कभी नहींआदेश पर विचार करें। यह अनियंत्रित सेट एक संयोजन होगा।
तुरंत संकेतन का परिचय दें: C. हम n में से m गेंदों का स्थान लेते हैं। हम ऑर्डर पर ध्यान देना बंद कर देते हैं और दोहराए जाने वाले संयोजन प्राप्त करते हैं। संयोजनों की संख्या प्राप्त करने के लिए, हमें नियुक्तियों की संख्या को m से भाग देना होगा! (एम फैक्टोरियल)। यानी सी \u003d ए / एम! इस प्रकार, n गेंदों में से चुनने के कुछ तरीके हैं, लगभग सभी चीजों को चुनने के लिए कितने के बराबर। इसके लिए एक तार्किक अभिव्यक्ति है: थोड़ा चुनना लगभग सब कुछ फेंकने जैसा ही है। इस बिंदु पर यह उल्लेख करना भी महत्वपूर्ण है कि आधे आइटम का चयन करने का प्रयास करते समय संयोजनों की अधिकतम संख्या प्राप्त की जा सकती है।
किसी समस्या के समाधान के लिए फॉर्मूला कैसे चुनें?
हमने कॉम्बिनेटरिक्स के मूल सूत्रों की विस्तार से जांच की है: प्लेसमेंट, क्रमचय और संयोजन। अब हमारा काम कॉम्बिनेटरिक्स में समस्या को हल करने के लिए आवश्यक सूत्र के चुनाव को सुविधाजनक बनाना है। आप निम्न सरल योजना का उपयोग कर सकते हैं:
- अपने आप से पूछें: क्या समस्या के पाठ में तत्वों के क्रम को ध्यान में रखा गया है?
- यदि उत्तर नहीं है, तो संयोजन सूत्र का उपयोग करें (C=n! / (m!(n - m)!))।
- यदि उत्तर नहीं है, तो आपको एक और प्रश्न का उत्तर देना होगा: क्या संयोजन में सभी तत्व शामिल हैं?
- यदि उत्तर हाँ है, तो क्रमचय सूत्र (P=n!) का उपयोग करें।
- यदि उत्तर नहीं है, तो आवंटन सूत्र (ए=एन! / (एन - एम)!) का उपयोग करें।
उदाहरण
हमने कॉम्बिनेटरिक्स के तत्वों, सूत्रों और कुछ अन्य मुद्दों पर विचार किया है। अब चलते हैंएक वास्तविक समस्या पर विचार करना। कल्पना कीजिए कि आपके सामने एक कीवी, एक संतरा और एक केला है।
प्रश्न एक: उन्हें कितने तरीकों से पुनर्व्यवस्थित किया जा सकता है? ऐसा करने के लिए, हम क्रमपरिवर्तन सूत्र का उपयोग करते हैं: P=3!=6 तरीके।
प्रश्न दो: एक फल को कितने तरीकों से चुना जा सकता है? यह स्पष्ट है, हमारे पास केवल तीन विकल्प हैं - कीवी, नारंगी या केला चुनें, लेकिन हम संयोजन सूत्र लागू करते हैं: सी \u003d 3! / (2!1!)=3.
प्रश्न तीन: दो फलों को कितने प्रकार से चुना जा सकता है? हमारे पास क्या विकल्प हैं? कीवी और नारंगी; कीवी और केला; नारंगी और केला। यही है, तीन विकल्प, लेकिन संयोजन सूत्र का उपयोग करके जांचना आसान है: सी \u003d 3! / (1!2!)=3
प्रश्न चार: तीन फलों को कितने प्रकार से चुना जा सकता है? जैसा कि आप देख सकते हैं, तीन फलों को चुनने का केवल एक ही तरीका है: एक कीवी, एक संतरा और एक केला लें। सी=3! / (0!3!)=1.
प्रश्न पांच: आप कम से कम एक फल को कितने तरीकों से चुन सकते हैं? इस स्थिति का तात्पर्य है कि हम एक, दो या तीनों फल ले सकते हैं। इसलिए, हम C1 + C2 + C3=3 + 3 + 1=7 जोड़ते हैं। यानी, हमारे पास टेबल से फल का कम से कम एक टुकड़ा लेने के सात तरीके हैं।
