उच्च माध्यमिक गणित · Bovenbouw

27क्रमचय-संचय और गणना

क्रमचय-संचय बिना सूची बनाए गिनने की कला है। उसके दो प्रारंभिक सिद्धांत — असंयुक्त विकल्पों के आकार जोड़ दीजिए, और स्वतंत्र चुनावों की संख्याएँ गुणा कर दीजिए — किसी परिमित समुच्चय के विन्यास, क्रमचय और उपसमुच्चय गिनने के लिए पर्याप्त हैं, और द्विपद प्रमेय पर जाकर अपनी चरम सीमा छूते हैं।

27.1 गणना के दो सिद्धांत

किसी परिमित समुच्चय $E$ के अवयवों की संख्या (गणनांक) को हम $\abs{E}$ लिखते हैं।

प्रतिज्ञप्ति 27.1 (योग का सिद्धांत)

यदि किसी परिमित समुच्चय $E$ को उपसमुच्चयों $A_1, \dots, A_k$ में विभाजित किया जाए (जो जोड़े-जोड़े असंयुक्त हों और जिनका सम्मिलन $E$ हो), तो

\abs{E} = \abs{A_1} + \abs{A_2} + \dots + \abs{A_k}.

प्रतिज्ञप्ति 27.2 (गुणन का सिद्धांत)

यदि कोई वस्तु $k$ क्रमिक चुनावों से बनती हो, जिनमें पहले चुनाव के लिए $n_1$ विकल्प हों और, पिछले चुनाव चाहे जो हों, $i$ -वें के लिए $n_i$ विकल्प हों, तो बनी हुई वस्तुओं की संख्या $n_1 \times n_2 \times \dots \times n_k$ है।

उपपत्ति. दोनों कथन $k$ पर आगमन से सिद्ध होते हैं; दूसरे की स्थिति $k = 2$ वस्तुतः किसी आयताकार सारणी को पंक्ति-दर-पंक्ति गिनना ही है। ∎

उदाहरण 27.3

किसी भोजनालय में 4 प्रारंभिक व्यंजन, 6 मुख्य व्यंजन और 3 मिष्ठान्न मिलते हैं: इस तरह $4 \times 6 \times 3 = 72$ भिन्न तीन-भागी भोजन बनते हैं।

27.2 सूचियाँ, क्रमचय, क्रमगुणित

परिभाषा 27.4 ( $k$ -सूचियाँ)

किसी समुच्चय $E$ की $k$ -सूची $E$ के अवयवों की क्रमित सूची $(x_1, \dots, x_k)$ है, जिसमें पुनरावृत्ति की छूट है। भिन्न अवयवों वाली $k$ -सूची $E$ के $k$ अवयवों का विन्यास कहलाती है।

प्रतिज्ञप्ति 27.5

मान लीजिए $\abs E = n$ है। $E$ की $k$ -सूचियों की संख्या $n^k$ है। $E$ के $k$ अवयवों के विन्यासों की संख्या ( $0 \leq k \leq n$ ) है

n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!},

जहाँ $n! = 1 \times 2 \times \dots \times n$ (और $0! = 1$ ) $n$ का क्रमगुणित है।

उपपत्ति. गुणन का सिद्धांत: $k$ -सूची के लिए $k$ चरणों में से हर एक पर $n$ विकल्प हैं; और विन्यास के लिए $x_1$ हेतु $n$ विकल्प, फिर $x_2$ हेतु $n - 1$ (एक अवयव काम में आ चुका), …, $x_k$ हेतु $n - k + 1$ । ∎

परिभाषा 27.6 (क्रमचय)

$E$ का क्रमचय $E$ के सभी $n$ अवयवों का विन्यास है: अर्थात् $E$ का एक क्रम। प्रतिज्ञप्ति 27.5 (स्थिति $k = n$ ) से $n$ -अवयवी समुच्चय के क्रमचयों की संख्या $n!$ है।

उदाहरण 27.7

पाँच धावक किसी दौड़ को $5! = 120$ भिन्न क्रमों में पूरा कर सकते हैं। संभव मंच (पहले तीन स्थान) की संख्या $5 \times 4 \times 3 = 60$ है।

27.3 संचय और द्विपद गुणांक

परिभाषा 27.8 (संचय)

$E$ के $k$ अवयवों का संचय $E$ का वह उपसमुच्चय है जिसमें $k$ अवयव हों (न क्रम, न पुनरावृत्ति)। उनकी संख्या $\dbinom{n}{k}$ लिखी जाती है और “ $k$ में से $n$ चुनना” पढ़ी जाती है।

प्रमेय 27.9

$0 \leq k \leq n$ के लिए:

\binom{n}{k} = \frac{n!}{k!\,(n-k)!} .

उपपत्ति. $E$ के $k$ अवयवों के विन्यास दो तरह से गिनिए। सीधे: $\frac{n!}{(n-k)!}$ । वैकल्पिक रूप से, पहले नीचे का उपसमुच्चय चुनिए ( $\binom nk$ तरीक़े), फिर उसे क्रम में लगाइए ( $k!$ तरीक़े); गुणन का सिद्धांत $\binom{n}{k}\,k!$ देता है। दोनों को बराबर रखने पर $\binom nk = \frac{n!}{k!(n-k)!}$ । ∎

प्रतिज्ञप्ति 27.10 (बुनियादी सर्वसमिकाएँ)

$0 \leq k \leq n$ के लिए:

\binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{k} = \binom{n}{n-k},

और पास्कल का नियम: $1 \leq k \leq n-1$ के लिए

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

उपपत्ति. सममिति $\binom nk = \binom{n}{n-k}$ इसलिए सही है कि पूरक लेने पर $k$ -अवयवी उपसमुच्चय $(n-k)$ -अवयवी उपसमुच्चयों से एक-एक करके मिल जाते हैं। पास्कल के नियम के लिए कोई अवयव $a \in E$ नियत कीजिए और $k$ -अवयवी उपसमुच्चयों को दो भागों में बाँटिए: वे जिनमें $a$ है — जो $E \setminus \{a\}$ के किसी $(k-1)$ -अवयवी उपसमुच्चय में $a$ जोड़ने से मिलते हैं और जिनकी संख्या $\binom{n-1}{k-1}$ है — और वे जिनमें $a$ नहीं है, जो $E \setminus \{a\}$ के $k$ -अवयवी उपसमुच्चय हैं और जिनकी संख्या $\binom{n-1}{k}$ है। योग के सिद्धांत से निष्कर्ष निकल आता है। ∎

पास्कल का नियम गुणांकों को पंक्ति-दर-पंक्ति बना देता है — पास्कल त्रिभुज: हर प्रविष्टि अपने ऊपर की दो प्रविष्टियों का योग है।

पास्कल त्रिभुज, पंक्तियाँ n = 0 से 5 तक: पास्कल का नियम 41 + 42 = 52 काम पर। — पास्कल त्रिभुज, पंक्तियाँ $n = 0$ से $5$ तक: पास्कल का नियम $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ काम पर।

प्रमेय 27.11 (द्विपद प्रमेय)

सभी $a, b \in \R$ (या $\C$ ) और $n \in \N$ के लिए:

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{k}\, b^{\,n-k} .

उपपत्ति. गुणनफल $(a+b)(a+b)\cdots(a+b)$ ( $n$ गुणनखंड) का प्रसार कीजिए: प्रसार का हर पद हर गुणनखंड में से $a$ या $b$ उठाता है, जिससे $a^k b^{n-k}$ बनता है, जहाँ $k$ $a$ देने वाले गुणनखंडों की संख्या है। $n$ में से ये $k$ गुणनखंड चुनने के तरीक़ों की संख्या $\binom nk$ है, और इसलिए वही $a^k b^{n-k}$ का गुणांक है। ∎

उपप्रमेय 27.12

$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ और $\displaystyle\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ ( $n \geq 1$ )।

उपपत्ति. द्विपद प्रमेय में $a = b = 1$ , फिर $a = -1$ , $b = 1$ लीजिए। पहली सर्वसमिका का सीधा अर्थ भी है: $n$ -अवयवी समुच्चय के $2^n$ उपसमुच्चय होते हैं (हर अवयव भीतर या बाहर: गुणन का सिद्धांत), जिन्हें आकार के अनुसार छाँट दिया गया है। ∎

विधि 27.13 (सही प्रतिरूप चुनना)

गिनने से पहले दो प्रश्नों का उत्तर दीजिए: क्या क्रम मायने रखता है? और क्या पुनरावृत्ति की छूट है?

	क्रम मायने रखता है	क्रम अप्रासंगिक
पुनरावृत्ति की छूट	$n^k$ (सूचियाँ)	(स्नातक स्तर)
पुनरावृत्ति नहीं	$\frac{n!}{(n-k)!}$ (विन्यास)	$\binom nk$ (उपसमुच्चय)

कलश से गेंदें निकालना: वापसी सहित, क्रम में $\to$ सूचियाँ; बिना वापसी, क्रम में $\to$ विन्यास; एक ही बार में मुट्ठी भर $\to$ उपसमुच्चय।

27.4 अभ्यास

अभ्यास 27.1 ★

किसी वाहन-पट्टिका पर 2 अक्षर ( $A$ – $Z$ ), फिर 3 अंक, फिर 2 अक्षर होते हैं। कितनी पट्टिकाएँ संभव हैं? कितनी ऐसी हैं जिनमें कोई भी चिह्न दोहराया न गया हो?

हल

हल — अभ्यास 27.1.

गुणन का सिद्धांत: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$ ।

बिना दोहराए चिह्नों के, चारों अक्षर भिन्न होने चाहिए ( $26 \times 25 \times 24 \times 23$ तरीक़े, अक्षर वाले स्थान क्रम से भरते हुए) और तीनों अंक भिन्न ( $10 \times 9 \times 8$ ):

26 \times 25 \times 24 \times 23 \times 10 \times 9 \times 8 = 358\,800 \times 720 = 258\,336\,000 .

अभ्यास 27.2 ★

$\dbinom{8}{3}$ , $\dbinom{10}{8}$ निकालिए, और $\dfrac{\binom{n}{2}}{\binom{n+1}{2}}$ को सरल कीजिए।

हल

हल — अभ्यास 27.2.

$\dbinom83 = \dfrac{8 \times 7 \times 6}{3!} = 56$ ; $\dbinom{10}{8} = \dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$ ;

\frac{\binom n2}{\binom{n+1}2} = \frac{n(n-1)/2}{(n+1)n/2} = \frac{n-1}{n+1}.

अभ्यास 27.3 ★

30 विद्यार्थियों की कक्षा में 4 विद्यार्थियों की एक समिति चुननी है, और फिर समिति के भीतर एक अध्यक्ष तथा एक कोषाध्यक्ष (एक ही व्यक्ति दोनों पद नहीं ले सकता)। कितने परिणाम संभव हैं?

हल

हल — अभ्यास 27.3.

समिति चुनिए: $\binom{30}{4}$ तरीक़े। फिर उन 4 में से अध्यक्ष और कोषाध्यक्ष क्रम में चुनिए: $4 \times 3 = 12$ तरीक़े। कुल

\binom{30}{4} \times 12 = 27\,405 \times 12 = 328\,860 .

अभ्यास 27.4 ★

द्विपद प्रमेय से $(x + 2)^5$ और $(1 - x)^6$ का प्रसार कीजिए। $(2x + 3)^7$ में $x^3$ का गुणांक क्या है?

हल

हल — अभ्यास 27.4.

(x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32 ,

(1-x)^6 = 1 - 6x + 15x^2 - 20x^3 + 15x^4 - 6x^5 + x^6 .

$(2x+3)^7$ में $x^3$ वाला पद $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$ है: गुणांक $22\,680$ है।

अभ्यास 27.5 ★★

ताश के 52 पत्तों की गड्डी से मानक पोकर का एक हाथ 5 पत्तों का होता है।

कुल कितने हाथ बनते हैं?
कितने हाथों में ठीक एक इक्का होता है? कम से कम एक इक्का?
कितने हाथ “फ़ुल हाउस” होते हैं (एक कोटि के तीन पत्ते और दूसरी कोटि के दो)?

हल

हल — अभ्यास 27.5.

1. $\dbinom{52}{5} = 2\,598\,960$ ।

2. ठीक एक इक्का: उसे चुनिए ( $4$ तरीक़े) और $4$ ग़ैर-इक्कों से पूरा कीजिए: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . कम से कम एक इक्का: पूरक से गिनकर $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ ।

3. तीन एक जैसे पत्तों की कोटि चुनिए ( $13$ ), उनके रंग ( $\binom43 = 4$ ), फिर जोड़े की कोटि ( $12$ बची हुई), उसके रंग ( $\binom42 = 6$ ): $13 \times 4 \times 12 \times 6 = 3744$ ।

अभ्यास 27.6 ★★

शब्द $\mathrm{MATH}$ के कितने अक्षर-विन्यास (अक्षरों की पुनर्व्यवस्थाएँ, अर्थपूर्ण हों या न हों) बनते हैं? और शब्द $\mathrm{BANANA}$ के? ( $\mathrm{BANANA}$ के लिए संकेत: पहले तीनों $A$ रखिए।)

हल

हल — अभ्यास 27.6.

$\mathrm{MATH}$ में 4 भिन्न अक्षर हैं: $4! = 24$ अक्षर-विन्यास।

$\mathrm{BANANA}$ में 6 अक्षर हैं: तीन $A$ , दो $N$ , एक $B$ । पहले $A$ के स्थान चुनिए ( $\binom63$ ), फिर शेष में से $N$ के ( $\binom32$ ), और $B$ को अंतिम जगह मिल जाती है:

\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60 .

(समतुल्य रूप से $\frac{6!}{3!\,2!\,1!} = 60$ ।)

अभ्यास 27.7 ★★

सर्वसमिका $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ( $1 \leq k \leq n$ ) दो तरह से सिद्ध कीजिए: क्रमगुणित वाले सूत्र से, और $n$ लोगों में से चुने गए युग्मों ( $k$ लोगों की समिति, उसका अध्यक्ष) को दो तरह से गिनकर।

हल

हल — अभ्यास 27.7.

बीजगणित से:

k\binom nk = \frac{k\,n!}{k!(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n\,\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!} = n\binom{n-1}{k-1}.

दोहरी गिनती से: युग्म (के $k$ लोगों की समिति, और उसमें से अध्यक्ष) गिनिए। या तो पहले समिति चुनिए ( $\binom nk$ ) फिर उसका अध्यक्ष ( $k$ ): $k\binom nk$ युग्म। या पहले अध्यक्ष चुनिए ( $n$ विकल्प) और फिर बचे हुए $n-1$ में से शेष $k-1$ सदस्य: $n\binom{n-1}{k-1}$ युग्म।

अभ्यास 27.8 ★★

समतल में कोई पथ $(0,0)$ से $(m, n)$ तक पूर्व या उत्तर दिशा में एक-एक मात्रक के क़दमों से जाता है। दिखाइए कि ऐसे पथों की संख्या $\dbinom{m+n}{m}$ है।

हल

हल — अभ्यास 27.8.

हर पथ में ठीक $m + n$ क़दम होते हैं, जिनमें $m$ पूर्व की ओर और $n$ उत्तर की ओर हैं; और वह पूरी तरह उन क्षणों के समुच्चय से तय हो जाता है ( $m+n$ में से) जिन पर पूर्व की ओर क़दम रखा जाता है। ऐसे $\binom{m+n}{m}$ चुनाव हैं।

अभ्यास 27.9 ★★★

वांडरमोंड की सर्वसमिका सिद्ध कीजिए: $0 \leq k \leq m + n$ के लिए

\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j},

और इसके लिए ऐसे समुच्चय के $k$ -अवयवी उपसमुच्चय गिनिए जो $m$ के एक समूह और $n$ के एक समूह में बँटा हो। इससे $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$ निकालिए।

हल

हल — अभ्यास 27.9.

$m + n$ लोगों के समुच्चय को $m$ के समूह $A$ और $n$ के समूह $B$ में बाँटिए। किसी $k$ -अवयवी उपसमुच्चय में $A$ के कुछ $j$ सदस्य होते हैं ( $0 \leq j \leq k$ ) और $B$ के $k - j$ ; किसी नियत $j$ के लिए ऐसे $\binom mj \binom{n}{k-j}$ उपसमुच्चय हैं, और $j$ पर योग का सिद्धांत वांडरमोंड की सर्वसमिका दे देता है।

$m = n = k$ के साथ:

\binom{2n}{n} = \sum_{j=0}^n \binom nj \binom{n}{n-j} = \sum_{j=0}^n \binom nj^{2},

जहाँ सममिति $\binom{n}{n-j} = \binom nj$ का उपयोग हुआ है।

अभ्यास 27.10 ★★★

द्विपद प्रमेय का उपयोग करके दिखाइए कि सभी $n \geq 1$ के लिए

\sum_{k=1}^{n} k \binom{n}{k} = n\,2^{n-1}.

(संकेत: या तो $(1+x)^n$ का अवकलन कीजिए, या अभ्यास 27.7 का उपयोग कीजिए।)

हल

हल — अभ्यास 27.10.

अभ्यास 27.7 से:

\sum_{k=1}^n k\binom nk = \sum_{k=1}^n n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1},

जो उपप्रमेय 27.12 से मिलता है। अवकलन से: $(1+x)^n = \sum_k \binom nk x^k$ का अवकलन $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ देता है; अब $x = 1$ पर मान निकालिए।

27.5 समस्या: दो बार गिनने की कला

समस्या 27.1

सप्ताहांत समस्या — तारे और छड़ें, बिखरी हुई टोपियाँ, और एक ही वस्तु को दो तरह से गिनकर सिद्ध की गई सर्वसमिकाएँ

क्रमचय-संचय की सबसे गहरी तरकीब निहायत सरल है: एक ही संग्रह को दो अलग-अलग तरीक़ों से गिनिए और दोनों उत्तरों को बराबर रख दीजिए। यह समस्या विधि 27.13 के प्रतिरूपों का अभ्यास कराती है, फिर एक ऐसी तकनीक जोड़ती है जिसकी अध्याय के पाठ्यक्रम को आवश्यकता नहीं पड़ी — कुल्फ़ी गिनने वाले तारे और छड़ें — और फिर प्रसिद्ध बिखरी हुई टोपियाँ ठीक-ठीक गिनती है, और टोपियों के ढेर की तह में प्रतीक्षा करती संख्या $\frac1\eu$ पा लेती है, जो इस पुस्तक में उसका तीसरा दर्शन है।

भाग I — प्रतिरूप का चुनाव।

$2$ अक्षरों और उसके बाद $3$ अंकों वाली वाहन-पट्टिकाएँ गिनिए; फिर $\mathrm{BANANA}$ के अक्षर-विन्यास।
$32$ पत्तों की गड्डी से $5$ पत्तों के हाथ गिनिए; फिर वे हाथ जिनमें $4$ इक्कों में से ठीक $2$ हों।
कोई रोबोट $(0,0)$ से $(4,3)$ तक केवल एक-एक मात्रक के दाएँ या ऊपर वाले क़दमों से चलता है: कितने पथ बनते हैं? (हर पथ को $R$ और $U$ वाले शब्द के रूप में लिखिए।)
द्विपद प्रमेय (प्रमेय 27.11) से $(1 + x)^4$ का प्रसार कीजिए; फिर $x = 1$ और $x = -1$ पर मान निकालिए: संख्याओं $\binom nk$ के बारे में कौन-सी दो सर्वसमिकाएँ निकल आती हैं?
दोहरी गिनती से सिद्ध कीजिए कि $k\binom nk = n\binom{n-1}{k-1}$ (अध्यक्ष-सहित-समितियाँ दो तरह से गिनिए), और $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ निकालिए।

भाग II — तारे और छड़ें।

कुल्फ़ी की एक दुकान $4$ स्वाद बेचती है; आप $10$ गोले मँगाते हैं (स्वाद दोहराए जा सकते हैं, और प्याले में क्रम अप्रासंगिक है)। किसी ऑर्डर को $10$ तारों (गोलों) की पंक्ति के रूप में लिखिए जिन्हें $3$ छड़ें (स्वाद बदलने के बिंदु) अलग करती हों, और ऑर्डर गिनिए।
$x + y + z = 12$ वाले अऋणात्मक पूर्णांकों के त्रिक गिनिए।
$x + y + z = 12$ वाले धनात्मक पूर्णांकों के त्रिक गिनिए ( $x = 1 + x'$ आदि प्रतिस्थापित कीजिए)।
$(a + b + c)^5$ के प्रसार में कितने भिन्न एकपदी आते हैं?
विधि की जाँच कीजिए: $2$ स्वादों से $3$ गोलों के ऑर्डर सूत्र से गिनिए, फिर उन सबकी सूची बनाकर तुलना कीजिए।
ठीक-ठीक बताइए कि “गोले एक जैसे हैं” यह बात इस लेखन में कहाँ घुसी — और विधि 27.13 की जाँच-सूची से गिनिए कि यदि गोले क्रम से खाए जाएँ (भिन्न स्थान) तो इसके बदले क्या होता है।

भाग III — बिखरी हुई टोपियाँ। विपर्यय $n$ टोपियों को उनके $n$ मालिकों में इस तरह बाँटना है कि किसी को भी अपनी टोपी न मिले; मान लीजिए $D_n$ ऐसे बँटवारों की गिनती करता है। (समस्या 18.1 ने दिखाया था कि औसतन एक अतिथि को अपनी टोपी वापस मिल जाती है — अब हम पूरी तरह अभागी दावतें ठीक-ठीक गिनते हैं।)

$D_1$ , $D_2$ , $D_3$ सूची बनाकर निकालिए, और $D_4$ धैर्य से (या चतुराई से)।
पुनरावृत्ति $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ को पुष्ट कीजिए: अतिथि 1 को कोई टोपी $k \neq 1$ मिलती है ( $n - 1$ विकल्प); फिर इस आधार पर बाँटिए कि अतिथि $k$ को टोपी 1 मिलती है या नहीं। जाँचिए कि यह $D_4$ दोबारा दे देती है, और $D_5$ निकालिए।
$n = 3$ के लिए समावेशन–अपवर्जन से सिद्ध कीजिए (कम से कम एक टोपी सही रखने वाले बँटवारे घटाइए, फिर अधिक गिनी गई बातें वापस जोड़िए) कि $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ , और सामान्य सूत्र बताइए।
$\frac{D_5}{5!}$ निकालिए और $\frac1\eu \approx 0.3679$ से तुलना कीजिए: किसी बड़ी फेंटी हुई दावत के पूरी तरह बिखर जाने की प्रायिकता $\frac1\eu$ है — लॉटरी और समस्या 23.1 के सचिव के बाद इस अचर का तीसरा दर्शन। (कारण: प्रश्न 14 का सूत्र $\eu^{-1}$ की एक प्रसिद्ध श्रेणी का आरंभ है, जिसकी कहानी स्नातक खंडों में है।)
$10$ मित्रों के बीच गुप्त उपहार: नाम एकसमान रूप से यादृच्छिक ढंग से निकाले जाते हैं। निकाले का वैध होने (किसी को अपना ही नाम न मिलने) की प्रायिकता क्या है, और समूह को कितनी बार फिर से निकालना पड़ेगा?

भाग IV — दो बार गिनिए, दो बार जीतिए।

हस्तमिलन प्रमेयिका: किसी भी दावत में हर अतिथि ने जितने हाथ मिलाए उनका योग हर हस्तमिलन को ठीक दो बार गिन लेता है। इससे निकालिए कि विषम संख्या में हाथ मिलाने वाले अतिथियों की संख्या सदा सम होती है — और जाँचिए कि तीन अतिथियों की दावत में यह दावा अर्थपूर्ण है।
रत्न $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ आगमन से सिद्ध कीजिए, और $n = 3$ के लिए उसकी पुष्टि कीजिए। (नन्हे गाउस का योग, वर्ग करने पर, घनों की गिनती कर देता है।)
पथों से वांडरमोंड की सर्वसमिका (अभ्यास 27.9): $\binom{2n}{n}$ की व्याख्या प्रश्न 3 जैसे जालक-पथों के रूप में $(0,0)$ से $(n,n)$ तक कीजिए, हर पथ को प्रति-विकर्ण पार करने वाली जगह पर काटिए, और समझाइए कि $\sum_j \binom nj^2$ कैसे प्रकट होता है।
समापन — गिनने वाले की चार चालें, हर एक पर एक पंक्ति और इस समस्या से एक उदाहरण: चरण गुणा कीजिए और स्थितियाँ जोड़िए; चतुराई से लिखिए (तारे और छड़ें, पथ-शब्द); एक ही वस्तु दो बार गिनिए (अध्यक्ष-सहित-समिति, हस्तमिलन); अनचाहे घटाइए और अधिक गिनी बातें सुधारिए (विपर्यय)। और यह भी लिखिए कि यह गिनती आगे कहाँ काम पर लगती है: प्रायिकता में, और आव्यूह-तथा-ग्राफ़ वाले अध्याय के पथों में।

हल

हल — समस्या 27.1.

1. $26^2 \times 10^3 = 676\,000$ पट्टिकाएँ। $\mathrm{BANANA}$ : $6$ अक्षर, जिनमें $A$ तिगुना और $N$ दुगुना है: $\frac{6!}{3!\,2!} = 60$ अक्षर-विन्यास।

2. $\binom{32}{5} = 201\,376$ हाथ; ठीक दो इक्कों वाले $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ ।

3. पथ $4$ बार $R$ और $3$ बार $U$ वाला शब्द है: $U$ के स्थान चुनिए: $\binom73 = 35$ ।

4. $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ । $x = 1$ पर: $\sum_k \binom nk = 2^n$ ; $x = -1$ पर: $\sum_k (-1)^k \binom nk = 0$ — यानी पास्कल त्रिभुज के पंक्ति-योग और एकांतर पंक्ति-योग।

5. $n$ में से अध्यक्ष सहित $k$ लोगों की समितियाँ: या तो समिति फिर उसका अध्यक्ष चुनिए ( $\binom nk \times k$ ), या अध्यक्ष फिर शेष सदस्य ( $n \times \binom{n-1}{k-1}$ ): दोनों बराबर। $k$ पर जोड़ने पर दाहिना पक्ष $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$ हो जाता है।

6. $10$ तारों और $3$ छड़ों की पंक्ति ऑर्डर लिख देती है (पहली छड़ से पहले स्वाद 1 के गोले, इत्यादि); पंक्ति में $13$ चिह्न हैं और वह छड़ों के स्थानों से तय हो जाती है: $\binom{13}{3} = 286$ ऑर्डर।

7. $12$ तारे, $2$ छड़ें: $\binom{14}{2} = 91$ ।

8. $x', y', z' \geq 0$ और $x' + y' + z' = 9$ के साथ: $\binom{11}{2} = 55$ ।

9. $i + j + k = 5$ वाला एकपदी $a^i b^j c^k$ : $\binom72 = 21$ ।

10. सूत्र से: $3$ तारे, $1$ छड़: $\binom41 = 4$ ; सूची: $(3,0)$ , $(2,1)$ , $(1,2)$ , $(0,3)$ : मेल।

11. “एक जैसे” वहाँ घुसा जहाँ यह घोषित किया गया कि ऑर्डर हर स्वाद की गिनती भर है — तारों के कोई नाम नहीं होते। यदि गोले क्रम से खाए जाएँ, तो $10$ भिन्न स्थानों में से हर एक स्वतंत्र रूप से कोई स्वाद चुन लेता है: $4^{10} = 1\,048\,576$ क्रम — यानी अलग प्रतिरूप और अलग संसार (विधि 27.13: सदा पूछिए क्रमित? भिन्न? पुनरावृत्ति की छूट?)।

12. $D_1 = 0$ ; $D_2 = 1$ (अदला-बदली); $D_3 = 2$ (दोनों $3$ -चक्र); $D_4 = 9$ ।

13. अतिथि 1 को टोपी $k \neq 1$ मिलती है: $n - 1$ विकल्प। यदि अतिथि $k$ को टोपी 1 मिले, तो बचे हुए $n - 2$ अतिथि अपनी टोपियों का विपर्यय करते हैं: $D_{n-2}$ तरीक़े। यदि अतिथि $k$ को टोपी 1 न मिले, तो टोपी 1 को अतिथि $k$ की वर्जित टोपी मान लीजिए: बचे हुए $n - 1$ अतिथि विपर्यय करते हैं: $D_{n-1}$ तरीक़े। अतः $D_n = (n-1)(D_{n-1} + D_{n-2})$ । जाँच: $D_4 = 3(2 + 1) = 9$ ; और $D_5 = 4(9 + 2) = 44$ ।

14. $3! = 6$ बँटवारों में से वे घटाइए जो कम से कम एक टोपी सही रखते हैं: किसी दी हुई टोपी को तीन सही रखते हैं (हर एक $2!$ , कुल $3 \times 2 = 6$ ), जिससे युग्म अधिक गिन लिए जाते हैं ( $3$ युग्म, हर एक $1!$ ) और उन्हें लौटाना पड़ता है, और फिर तत्समक को दोबारा घटाना पड़ता है ( $1$ ): $D_3 = 6 - 6 + 3 - 1 = 2$ , अर्थात् $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$ । सामान्य रूप से $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ ।

15. $\frac{D_5}{120} = \frac{44}{120} \approx 0.3667$ , जो $\frac1\eu \approx 0.3679$ के पहले से ही पास है: एकांतर योग $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ $\eu^{-1}$ की ओर बढ़ता है। किसी बड़ी दावत की टोपियाँ लगभग $36.8\,\%$ बार पूरी तरह बिखर जाती हैं — लॉटरी और सचिव वाला वही अचर, तीसरी बार दिखाई देते हुए।

16. $\P(\text{वैध}) = \frac{D_{10}}{10!} \approx 0.368$ । हर बार फिर से निकालने पर सफलता की प्रायिकता $\approx \frac1\eu$ है, इसलिए निकालों की प्रत्याशित संख्या लगभग $\eu \approx 2.7$ है: तीन बार टोपियाँ बाँटने का बजट रखिए।

17. हर हस्तमिलन कुल कोटि-गिनती में $2$ जोड़ता है, इसलिए सभी अतिथियों की हस्तमिलन-संख्याओं का योग सम होता है। पूर्णांकों का योग तभी सम होता है जब विषम पदों की संख्या सम हो: विषम हाथ मिलाने वाले सम संख्या में आते हैं। (तीन अतिथियों पर: संभव हस्तमिलन-चित्रों में कभी ठीक एक या तीन विषम प्रविष्टियाँ नहीं होतीं — चारों संभव ग्राफ़ जाँच लीजिए।)

18. $n = 1$ : $1 = 1$ । यदि $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ हो, तो $(n+1)^3$ जोड़ने पर

\frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2\left(n^2 + 4n + 4\right)}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^{\!2} :

वंशानुगति। $n = 3$ के लिए: $1 + 8 + 27 = 36 = 6^2$ ।

19. $(n, n)$ तक जाने वाला कोई पथ $2n$ क़दम चलता है और प्रति-विकर्ण $x + y = n$ को ठीक एक जालक-बिंदु $(j, n - j)$ पर पार करता है; उसका पहला आधा $n$ क़दमों में $j$ बार $R$ वाला पथ है ( $\binom nj$ चुनाव), और दूसरा आधा, उल्टा पढ़ने पर, वैसा ही (सममिति से फिर $\binom nj$ )। कटान-बिंदु पर जोड़ने पर: $\binom{2n}{n} = \sum_j \binom nj^2$ — वांडरमोंड की सर्वसमिका, खींची हुई।

20. चरण गुणा कीजिए, स्थितियाँ जोड़िए: पट्टिकाएँ और पोकर के हाथ। चतुराई से लिखिए: पथ $R$ – $U$ शब्दों के रूप में, ऑर्डर तारों और छड़ों के रूप में। दो बार गिनिए: अध्यक्ष-सहित-समितियाँ, हस्तमिलन, बीच से कटे पथ। घटाइए और सुधारिए: बिखरी टोपियाँ, जिनका अवशेष $\frac1\eu$ है। अगले पड़ाव: प्रायिकता की भिन्नों के अधीन यही गिनतियाँ, और दो अध्याय आगे आसन्नता आव्यूहों की पथ-गिनने वाली घातें।