संचय शास्त्र — गणना, पुनरावृत्ति संबंध व जनक फलन

प्रत्येक गणना-प्रश्न चार आकारों में से एक है, और आकार का नामकरण ही अधिकांश काम है। क्रम महत्वपूर्ण है, और वस्तुएँ दोहराई जा सकती हैं? क्रम व दोहराव-रहित अर्थात् क्रमचय, nPr; क्रम-रहित व दोहराव-रहित अर्थात् संचय, nCr; दोहराव सहित क्रम अर्थात् nʳ; और दोहराव सहित क्रम-रहित वह है जिसे अभ्यर्थी भूलते हैं — C(n + r − 1, r), तारा-व-पट्टी गिनती, जो x₁ + ⋯ + xₙ = r के अनृणात्मक पूर्णांक हलों की संख्या भी है। सूत्र तक पहुँचने से पहले उन दो प्रश्नों का निर्णय इस प्रकरण के लगभग प्रत्येक गलत उत्तर को रोक देता है। दो और उपकरण वह सँभालते हैं जो सादी गणना नहीं कर सकती। समावेशन–अपवर्जन दोहरी गणना सुधारता है: |A ∪ B| = |A| + |B| − |A ∩ B|, और तीन समुच्चयों पर आप एकल जोड़ते हैं, युग्म घटाते हैं और त्रिक फिर जोड़ते हैं — एकांतर चिह्न सजावट नहीं, वे सुधारों के सुधार हैं। और कोष्ठिका-सिद्धांत उन अस्तित्व-प्रश्नों का उत्तर देता है जो रचना माँगते दिखते हैं: तेरह व्यक्तियों में दो एक ही मास में जन्मे होंगे, क्योंकि बारह मास हैं, और व्यक्ति चुनने की कोई भी चतुराई इससे नहीं बचाती। अध्याय का दूसरा भाग पुनरावृत्ति संबंध है, और अचर गुणांकों वाला रैखिक समघात पुनरावृत्ति संबंध ठीक उसी आकार के अवकल समीकरण की तरह हल होता है: अभिलक्षणिक समीकरण लिखें, उसके मूल खोजें, और घातें संयोजित करें। aₙ = 5aₙ₋₁ − 6aₙ₋₂ हेतु अभिलक्षणिक समीकरण x² − 5x + 6 = 0 है जिसके मूल 2 व 3 हैं, अतः aₙ = A·2ⁿ + B·3ⁿ, और प्रारंभिक शर्तें A व B नियत करती हैं। बंद रूप को पुनरावृत्ति दो-तीन चरण चलाकर सदा जाँचें — इसमें सेकंड लगते हैं और A या B में चिह्न-त्रुटि पकड़ने का यही एकमात्र उपाय है। जनक फलन वही विचार भिन्न मुद्रा में हैं: अनुक्रम को घात-श्रेणी के गुणांकों के रूप में कूटित करें, श्रेणी पर बीजगणित करें, और उत्तर गुणांक के रूप में पढ़ लें। अत्यंत दृढ़ता से जानने योग्य एक प्रसार 1/(1 − x)ᵏ है, जिसमें xⁿ का गुणांक C(n + k − 1, k − 1) है — जो फिर वही तारा-व-पट्टी सूत्र है, दूसरी दिशा से आता हुआ।

चार आकार, दो प्रश्नों से तय

n में से r वस्तुएँ चुनना
क्रम महत्वपूर्ण?दोहराव अनुमत?गिनती, हल किए मान सहित
हाँनहींnPr = n!/(n − r)!। P(10, 3) = 10 × 9 × 8 = 720।
नहींनहींnCr = n!/(r!(n − r)!)। C(10, 3) = 120, जो 720/3! है।
हाँहाँnʳ। 26-अक्षरी वर्णमाला से दोहराव सहित तीन अक्षर: 26³।
नहींहाँC(n + r − 1, r) — तारा व पट्टी। x₁ + x₂ + x₃ = 10 के अनृणात्मक हल: C(12, 2) = 66।
🧠 धन हल: पहले प्रत्येक चर से एक घटाएँ
तारा व पट्टी अनृणात्मक हल गिनती है। यदि प्रश्न कड़ाई से धन हल चाहे, तो प्रत्येक चर को उसका अनिवार्य 1 पहले दे दें और शेष गिनें: x₁ + x₂ + x₃ = 10 के धन हल y₁ + y₂ + y₃ = 7 के अनृणात्मक हल हैं, जो 66 के बजाय C(9, 2) = 36 है। वही प्रतिस्थापन किसी भी अधो परिबंध को सँभालता है — "प्रत्येक xᵢ ≥ 2" गिनने से पहले कुल से 6 हटा देता है। शून्य अनुमत है या नहीं यह पढ़ना ही दोनों उत्तरों का पूरा अंतर है, और दोनों विकल्पों में होंगे।
  • समावेशन–अपवर्जन, तीन समुच्चय: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|। एकल 30, 25, 20; युग्म 12, 10, 8; तीनों में 5 होने पर संघ 30 + 25 + 20 − 12 − 10 − 8 + 5 = 50 है। त्रिक-सर्वनिष्ठ तीन बार घटाया और तीन बार जोड़ा गया है, अतः उसे एक बार और जोड़ना है — अंतिम धन वहीं से आता है।
  • कोष्ठिका-सिद्धांत: n कोष्ठों में n + 1 वस्तुएँ किसी कोष्ठ में दो पर विवश करती हैं। तेरह व्यक्तियों में दो एक ही मास में जन्मे होते हैं। सामान्यीकृत रूप — m वस्तुओं व n कोष्ठों हेतु किसी कोष्ठ में ⌈m/n⌉ — "कितनों को साझा करना ही पड़ेगा" का उत्तर देता है, केवल "क्या दो साझा करते हैं" का नहीं।
  • द्विआधारी स्ट्रिंग छद्म रूप में संचय हैं। ठीक तीन 1 वाली 8-बिट स्ट्रिंगों की संख्या यह चुनने के तरीकों की संख्या है कि कौन तीन स्थान उन्हें रखें: C(8, 3) = 56। "ठीक k अमुक वस्तु वाली कितनी स्ट्रिंग" जैसा लगभग प्रत्येक प्रश्न यही प्रतिस्थापन है।

पुनरावृत्ति संबंध — अभिलक्षणिक समीकरण

अचर गुणांकों वाला रैखिक समघात पुनरावृत्ति संबंध उसी आकार के अवकल समीकरण जैसे तीन चरणों से हल होता है, और यदि आपने अवकल समीकरणों पर अभियांत्रिकी गणित का अध्याय पढ़ा है तो विधि पहले से परिचित लगेगी — सादृश्य ठीक-ठीक है, चरघातांकियों के स्थान पर घातें सहित।

  1. aₙ₋ₖ को x(−k) से बदलकर व साफ़ करके अभिलक्षणिक समीकरण लिखें: aₙ = 5aₙ₋₁ − 6aₙ₋₂ से x² − 5x + 6 = 0।
  2. उसे हल करें। मूल 2 व 3, भिन्न, अतः व्यापक हल aₙ = A·2ⁿ + B·3ⁿ है। पुनरावृत्त मूल r से (A + Bn)·rⁿ मिलता, ठीक जैसे अवकल समीकरण में पुनरावृत्त मूल गुणक t लाता है।
  3. प्रारंभिक शर्तें फिट करें। a₀ = 1 व a₁ = 5 पर: A + B = 1 तथा 2A + 3B = 5 से B = 3, A = −2, अतः aₙ = 3·3ⁿ − 2·2ⁿ। फिर पुनरावृत्ति चलाकर जाँचें: पुनरावृत्ति से 1, 5, 19, 65, 211, और बंद रूप वही पाँच पद देता है।
⚠️ बंद रूप को पुनरावृत्ति चलाकर जाँचें — उपलब्ध एकमात्र सस्ती जाँच वही है
अभिलक्षणिक मूल गलत करना कठिन है; अचर A व B गलत करना सरल है, क्योंकि वे समय के दबाव में हल किए छोटे रैखिक निकाय से आते हैं और वहाँ चिह्न-त्रुटि ऐसा सूत्र बना देती है जो पूर्णतः उचित दिखता है। पुनरावृत्ति को तीन पद चलाकर तुलना करने में लगभग पंद्रह सेकंड लगते हैं और वह ऐसी प्रत्येक त्रुटि पकड़ लेती है। वह दूसरी आम भूल भी पकड़ती है, जो अचरों को गलत सूचकांकों पर फिट करना है — दिए आँकड़े a₀ व a₁ हैं या a₁ व a₂, यह निकाय बदल देता है, और प्रश्न बताएगा कि कौन।

जनक फलन, व जानने योग्य एक प्रसार

  • 1/(1 − x) = 1 + x + x² + ⋯, अतः प्रत्येक गुणांक 1 है। यह सभी एक वाला अनुक्रम है, और इस प्रकरण का हर दूसरा प्रसार इसी से बनता है।
  • 1/(1 − x)ᵏ में xⁿ का गुणांक C(n + k − 1, k − 1) है। k = 3 व n = 10 हेतु वह C(12, 2) = 66 है — ऊपर के तारा-व-पट्टी उत्तर वाला वही 66, और यह संयोग नहीं: 1 + x + x² + ⋯ की k प्रतियाँ गुणा करना ठीक n समरूप वस्तुओं को k लेबल-युक्त कोष्ठों में बाँटना है।
  • (1 + x)ⁿ में xʳ का गुणांक C(n, r) है — द्विपद प्रमेय को जनक फलन के रूप में पढ़ना। (1 + x)⁸ में x⁵ का गुणांक C(8, 5) = 56 है, 8-बिट स्ट्रिंग गिनती वाला वही 56, फिर उसी कारण से।
  • कातालान संख्याएँ n भिन्न कुंजियों पर द्विआधारी खोज वृक्ष, संतुलित कोष्ठक-स्ट्रिंग व बहुभुज के त्रिभुजन गिनती हैं, और वे Cₙ = C(2n, n)/(n + 1) हैं: C₃ = 5 व C₄ = 14। GATE इसे प्रायः "n कुंजियों पर कितने भिन्न BST" के रूप में पूछता है, और उत्तर n! के बजाय कातालान है ठीक इसलिए कि BST अपने आकार से निर्धारित होता है और तब कुंजियों के जाने का केवल एक स्थान बचता है।

मुख्य बिंदु

  • किसी सूत्र से पहले दो प्रश्न तय करें: क्रम महत्वपूर्ण है, और वस्तुएँ दोहराई जा सकती हैं? चारों उत्तर nPr, nCr, nʳ व C(n + r − 1, r) हैं।
  • तारा व पट्टी अनृणात्मक हल गिनती है। कड़ाई से धन हलों हेतु पहले प्रत्येक चर को उसका अनिवार्य 1 दें: 66 बनकर 36 हो जाता है।
  • समावेशन–अपवर्जन के चिह्न एकांतर होते हैं क्योंकि प्रत्येक सुधार अधिक सुधार कर देता है: एकल घटा युग्म जमा त्रिक।
  • कोष्ठिका-सिद्धांत रचना के बिना अस्तित्व का उत्तर देता है, और उसका सामान्यीकृत रूप ⌈m/n⌉ बताता है कि कितनों को साझा करना पड़ेगा, न कि दो करते हैं या नहीं।
  • रैखिक पुनरावृत्ति संबंध को उसके अभिलक्षणिक समीकरण से हल करें, ठीक अवकल समीकरण की तरह — भिन्न मूल A·r₁ⁿ + B·r₂ⁿ देते हैं, पुनरावृत्त मूल (A + Bn)rⁿ।
  • बंद रूप को पुनरावृत्ति दो-तीन चरण चलाकर सदा जाँचें। मूल गलत करना कठिन है और अचर सरल।
  • 1/(1 − x)ᵏ जानें, जिसमें xⁿ का गुणांक C(n + k − 1, k − 1) है — तारा-व-पट्टी सूत्र दूसरी दिशा से आता हुआ।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. x₁ + x₂ + x₃ = 10 के अनृणात्मक पूर्णांक हलों की संख्या है:

    1. 36
    2. 66
    3. 120
    4. 1000
    उत्तर देखें

    उत्तर: B — 66

    तारा व पट्टी: दस समरूप तारे और तीन समूह अलग करती दो पट्टियाँ, अतः चुनें कि 12 स्थानों में कौन 2 पट्टियाँ रखें — C(12, 2) = 66। विकल्प A कड़ाई से धन हलों की गिनती है, C(9, 2) = 36, जो प्रत्येक चर को उसका अनिवार्य 1 पहले देकर शेष 7 बाँटने पर मिलता है। दोनों संख्याएँ विकल्पों में हैं क्योंकि शून्य अनुमत है या नहीं यह पढ़ना ही पूरा प्रश्न है। विकल्प D, 10³ है, जो उत्तर तब होता यदि चर नियत योग के भाग होने के बजाय दस मानों से क्रमित चुनाव होते।

  2. a₀ = 1 व a₁ = 5 सहित पुनरावृत्ति aₙ = 5aₙ₋₁ − 6aₙ₋₂ का बंद रूप है:

    1. 3·3ⁿ − 2·2ⁿ
    2. 2·2ⁿ − 3·3ⁿ
    3. 2ⁿ + 3ⁿ
    4. (1 + 4n)·2ⁿ
    उत्तर देखें

    उत्तर: A — 3·3ⁿ − 2·2ⁿ

    अभिलक्षणिक समीकरण x² − 5x + 6 = 0 के मूल 2 व 3 हैं, अतः aₙ = A·2ⁿ + B·3ⁿ। a₀ = 1 फिट करने पर A + B = 1 तथा a₁ = 5 से 2A + 3B = 5, अतः B = 3 व A = −2 — बंद रूप 3·3ⁿ − 2·2ⁿ है। पुनरावृत्ति चलाकर जाँचें: पुनरावृत्ति 1, 5, 19, 65, 211 देती है, और सूत्र भी वही। विकल्प B में अचरों के चिह्न बदले हुए हैं, और ठीक वही त्रुटि है जिसे पकड़ने हेतु पुनरावृत्ति-जाँच है — वह a₀ = −1 देता है। विकल्प C किसी शर्त को फिट नहीं करता, और विकल्प D पुनरावृत्त मूल हेतु आकार होता, जो इस समीकरण का नहीं है।

  3. ठीक तीन 1 वाली 8-बिट द्विआधारी स्ट्रिंगों की संख्या है:

    1. 24
    2. 56
    3. 256
    4. 336
    उत्तर देखें

    उत्तर: B — 56

    स्ट्रिंग इससे नियत होती है कि आठ स्थानों में कौन तीन 1 रखें, और स्थान क्रम-रहित व दोहराव-रहित चुने जाते हैं: C(8, 3) = 56। विकल्प D, P(8, 3) = 336 है, जो उत्तर तब होता यदि तीनों 1 विभेद्य होते और उनका क्रम महत्व रखता — वे नहीं हैं, और 336 = 56 × 3! ठीक वही अति-गणना है। विकल्प C, 2⁸ है, बिना किसी शर्त की 8-बिट स्ट्रिंगों की संख्या। नामकरण योग्य सामान्य चाल: "n स्थानों में ठीक k अमुक" सदा संचय है, और यह पहचानना स्ट्रिंग-प्रश्न को किसी स्थिति-विश्लेषण के बिना द्विपद गुणांक बना देता है।

  4. किसी कक्षा में 30 विद्यार्थी गणित, 25 भौतिकी व 20 रसायन पढ़ते हैं; 12 गणित व भौतिकी, 10 गणित व रसायन, 8 भौतिकी व रसायन, तथा 5 तीनों। कम-से-कम एक विषय पढ़ने वालों की संख्या है:

    1. 45
    2. 50
    3. 60
    4. 75
    उत्तर देखें

    उत्तर: B — 50

    समावेशन–अपवर्जन: 30 + 25 + 20 − 12 − 10 − 8 + 5 = 50। अंतिम धन वही चरण है जिसे अभ्यर्थी छोड़ देते हैं, और उसे याद करने के बजाय समझना उपयोगी है: तीनों विषय पढ़ने वाले पाँच विद्यार्थी एकल में तीन बार गिने गए, फिर युग्मों द्वारा तीन बार हटा दिए गए, जिससे वे पूर्णतः बाहर रह गए — अतः उन्हें एक बार फिर जोड़ना ही पड़ेगा। वह पद छोड़ने पर 45 मिलता है, जो विकल्प A है। विकल्प D सादा योग 75 है, जो उत्तर तब होता यदि कोई अतिव्यापन ही न होता, और 75 व 50 के बीच 25 का अंतर ठीक वही दोहरी गणना है जिसे सुधार हटाते हैं।

  5. 1/(1 − x)³ के प्रसार में x¹⁰ का गुणांक है:

    1. 11
    2. 30
    3. 66
    4. 120
    उत्तर देखें

    उत्तर: C — 66

    1/(1 − x)ᵏ में xⁿ का गुणांक C(n + k − 1, k − 1) है, अतः यहाँ वह C(12, 2) = 66 है। वह x₁ + x₂ + x₃ = 10 के अनृणात्मक हलों की संख्या वाला वही 66 है, और यह संयोग ही मुद्दा है: 1 + x + x² + ⋯ की तीन प्रतियाँ गुणा करना व x¹⁰ पद जुटाना दस एकांशों को तीन चरों में बाँटना ही है, अतः जनक फलन व तारा-व-पट्टी का तर्क दो संकेतनों में एक ही गणना हैं। विकल्प A, 1/(1 − x)² हेतु गुणांक है, जो C(11, 1) = 11 है, और उसे देना यह जाँचता है कि आपने हर का घातांक पढ़ा।

  6. निम्नलिखित में कौन सही हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. किन्हीं भी 13 व्यक्तियों में दो का जन्म-मास समान होता है
    2. सभी 0 ≤ r ≤ n हेतु C(n, r) = C(n, n − r)
    3. 4 भिन्न कुंजियों पर द्विआधारी खोज वृक्षों की संख्या 4! = 24 है
    4. n-समुच्चय के उपसमुच्चयों की संख्या 2ⁿ है
    उत्तर देखें

    उत्तर: A — किन्हीं भी 13 व्यक्तियों में दो का जन्म-मास समान होता है; B — सभी 0 ≤ r ≤ n हेतु C(n, r) = C(n, n − r); D — n-समुच्चय के उपसमुच्चयों की संख्या 2ⁿ है

    तीन सत्य हैं। A कोष्ठिका-सिद्धांत है, 13 वस्तुएँ व 12 कोष्ठ। B द्विपद गुणांक की सममिति है — सम्मिलित करने हेतु r चुनना बाहर छोड़ने हेतु n − r चुनने के समान है — और यही वह सर्वसमिका है जो द्विपदों की तालिका में आधा काम बचाती है। D मानक उपसमुच्चय-गिनती है, प्रति अवयव एक द्विआधारी चुनाव। केवल C विफल है: n भिन्न कुंजियों पर BST की संख्या कातालान संख्या Cₙ = C(2n, n)/(n + 1) है, अतः चार कुंजियों पर वह 14 है, 24 नहीं। यह भेद रखने योग्य है: 4! = 24 निवेशन-क्रम गिनता है, और भिन्न क्रम एक ही वृक्ष बना सकते हैं, और ठीक इसीलिए वृक्ष-गिनती क्रमचय-गिनती से छोटी है।

  7. 10 भिन्न वस्तुओं में से 3 चुनने के तरीकों की संख्या, जब क्रम महत्वपूर्ण न हो, _____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 120

    C(10, 3) = (10 × 9 × 8)/(3 × 2 × 1) = 720/6 = 120। संगत क्रमित गिनती P(10, 3) = 720 है, और उनके बीच का गुणक 3! = 6 है — किसी एक चुने त्रिक के क्रमों की संख्या। उस संबंध को ध्यान में रखना दोनों सूत्रों से तेज़ है: अवरोही गुणनफल 10 × 9 × 8 निकालें और r! से भाग केवल तब दें जब क्रम अप्रासंगिक हो। सममिति C(10, 3) = C(10, 7) पर भी ध्यान दें, जिसका अर्थ है कि 10 में से 7 पूछने वाले प्रश्न का उत्तर वही है और उसे नए सिरे से नहीं निकालना चाहिए।

  8. 4 भिन्न कुंजियों से बनाए जा सकने वाले भिन्न द्विआधारी खोज वृक्षों की संख्या _____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 14

    यह कातालान संख्या C₄ = C(8, 4)/5 = 70/5 = 14 है। समय के दबाव में पुनरुत्पादित करने योग्य पुनरावर्ती तर्क यह है: चुनें कौन कुंजी मूल है, और उससे नीचे व ऊपर की कुंजियाँ तब बाएँ व दाएँ उपवृक्षों में विवश हो जाती हैं, अतः मूल के n चुनावों पर Cₙ = Σ Ck·Cn−1−k। चार कुंजियों हेतु वह 5 + 2 + 2 + 5 = 14 है, C₀ = 1, C₁ = 1, C₂ = 2 व C₃ = 5 का प्रयोग करते हुए। उत्तर जान-बूझकर 4! = 24 नहीं है: वह निवेशन-क्रम गिनता है, और भिन्न क्रम प्रायः एक ही वृक्ष बनाते हैं — इसीलिए वही कातालान संख्या संतुलित कोष्ठक-स्ट्रिंग व बहुभुज-त्रिभुजन भी गिनती है।