विश्वविद्यालय गणित — स्नातक वर्ष 1 · Bachelor Year 1

2गणना

परिमित समुच्चयों की गणना प्रारंभिक लगती है — और शीघ्र ही सूक्ष्म हो जाती है। यह अध्याय गणनांक की उचित परिभाषा देता है (एकैकी आच्छादनों के द्वारा, अध्याय 1 की भावना में), उन गिनी-चुनी गणना-नियमों को स्थापित करता है जिनसे सब कुछ निकलता है, और उनसे चिरपरिचित गणनाएँ व्युत्पन्न करता है: सूचियाँ, क्रमचय, उपसमुच्चय, द्विपद गुणांक।

2.1 परिमित समुच्चयों का गणनांक

परिभाषा 2.1 (परिमित समुच्चय, गणनांक)

$n \in \N^*$ के लिए $\intint{1}{n} = \{1, 2, \dots, n\}$ लिखिए। समुच्चय $E$ परिमित तब कहलाता है जब $E = \emptyset$ हो, या किसी $n \in \N^*$ के लिए $\intint{1}{n}$ से $E$ पर कोई एकैकी आच्छादन हो; यह $n$ अद्वितीय होता है (प्रमेय 2.2) और $E$ का गणनांक कहलाता है, जिसे $\abs{E}$ लिखा जाता है ( $\abs{\emptyset} = 0$ के साथ)।

प्रमेय 2.2 (गणनांक सुपरिभाषित है)

यदि $m \neq n$ , तो $\intint{1}{m}$ से $\intint{1}{n}$ पर कोई एकैकी आच्छादन नहीं है। और अधिक ठीक-ठीक: यदि $m > n$ , तो $\intint{1}{m}$ से $\intint{1}{n}$ में कोई एकैकी प्रतिचित्रण नहीं है।

उपपत्ति. हम $n$ पर आगमन से यह कथन सिद्ध करते हैं: सभी $m > n$ के लिए कोई एकैकी प्रतिचित्रण $\intint{1}{m} \to \intint{1}{n}$ नहीं है। $n = 0$ के लिए लक्ष्य रिक्त है और $m \geq 1$ : कोई प्रतिचित्रण है ही नहीं। कथन को $n$ के लिए मान लीजिए, और मान लीजिए $f \colon \intint{1}{m} \to \intint{1}{n+1}$ एक एकैकी प्रतिचित्रण है, जहाँ $m > n + 1$ । यदि मान $n + 1$ प्राप्त नहीं होता, तो $f$ $\intint{1}{n}$ में एकैकी प्रतिचित्रण है, जो आगमन परिकल्पना का विरोध करता है। अन्यथा ठीक एक $a$ के लिए $f(a) = n + 1$ ; $f(a)$ और $f(m)$ की अदला-बदली कीजिए (औपचारिक रूप से: दोनों मानों के व्यत्यास के साथ संयोजन कीजिए), जिससे नए एकैकी प्रतिचित्रण $g$ के लिए $g(m) = n + 1$ हो जाए। तब $\intint{1}{m-1}$ पर $g$ का प्रतिबंधन $\intint{1}{n}$ में एकैकी प्रतिचित्रण है, जहाँ $m - 1 > n$ — फिर विरोधाभास। ∎

उपप्रमेय 2.3 (कबूतरखाना सिद्धांत)

यदि $\abs{E} > \abs{F}$ , तो कोई भी प्रतिचित्रण $f \colon E \to F$ एकैकी नहीं है: $E$ के कोई दो अवयव अपना प्रतिबिंब साझा करते हैं।

उपपत्ति. $\abs E = m$ , $\abs F = n$ लिखिए, जहाँ $m > n$ , और एकैकी आच्छादन $u \colon \intint1m \to E$ तथा $v \colon F \to \intint1n$ चुनिए। यदि $f$ एकैकी होता, तो $v \circ f \circ u$ $\intint1m$ से $\intint1n$ में एकैकी प्रतिचित्रण होता (एकैकी प्रतिचित्रणों का संयोजन, प्रतिज्ञप्ति 1.26), जो प्रमेय 2.2 का विरोध करता। ∎

टिप्पणी 2.4 (मध्यांतर: प्रमेय की उपपत्ति में अदला-बदली क्यों?)

प्रमेय 2.2 की उपपत्ति में इस अध्याय की पहली सचमुच चतुर चाल है, जिसे धीरे-धीरे दोहराना उचित है। बाधा यह है: आगमन परिकल्पना लगाने के लिए हम स्रोत का अंतिम बिंदु $m$ और लक्ष्य का अंतिम बिंदु $n+1$ दोनों हटाना चाहते हैं, पर $f$ किसी दूसरे बिंदु $a$ को $n + 1$ पर भेज सकता है, और तब लक्ष्य-बिंदु हटाने से प्रतिचित्रण अन्यत्र बिगड़ जाता है। उपाय: $f$ को दोनों मानों $f(a)$ और $f(m)$ के व्यत्यास के साथ संयोजित कीजिए — यह लक्ष्य का एकैकी आच्छादन है, अतः एकैकीयता बनी रहती है — इसके बाद कष्टप्रद मान $n + 1$ निरापद स्थान $m$ पर आ बैठता है और दोनों विलोपन स्वच्छ हो जाते हैं। “पहले मानकीकरण, फिर कटाई” का यह प्रतिरूप बार-बार लौटता है: इसी से इस अध्याय की सप्ताहांत समस्या में व्यत्यय-पुनरावृत्ति $\sigma^{-1}(n+1)$ की दिशा बदलती है, और इसी से अध्याय 7 की सममित समूह वाली समस्या में क्रमचयों की मरम्मत होती है।

प्रतिज्ञप्ति 2.5 (एकैकी, आच्छादक प्रतिचित्रण और गणनांक)

मान लीजिए $E, F$ परिमित समुच्चय हैं, जहाँ $\abs{E} = \abs{F}$ , और $f \colon E \to F$ । तब

f \text{ एकैकी} \iff f \text{ आच्छादक} \iff f \text{ एकैकी आच्छादक}.

उपपत्ति. मान लीजिए $f$ एकैकी है। तब $f$ $E$ से $f(E)$ पर एकैकी आच्छादन है, अतः $\abs{f(E)} = \abs{E} = \abs{F}$ । यदि $f(E)$ $F$ के किसी बिंदु $y_0$ तक न पहुँचता, तो $f$ $E$ का $F \setminus \{y_0\}$ में एकैकी प्रतिचित्रण होता, जिसका गणनांक $\abs{F} - 1 < \abs{E}$ है — कबूतरखाना सिद्धांत से असंभव। अतः $f(E) = F$ : $f$ आच्छादक है, अतः एकैकी आच्छादक भी।

मान लीजिए $f$ आच्छादक है। प्रत्येक $y \in F$ के लिए एक पूर्वप्रतिबिंब $s(y) \in E$ चुनिए; तब $f \circ s = \mathrm{id}_F$ , अतः $s$ एकैकी है (प्रतिज्ञप्ति 1.26)। पिछले अनुच्छेद को $s$ पर लगाने से (गणनांक बराबर हैं) $s$ एकैकी आच्छादक है। $f \circ s = \mathrm{id}_F$ से $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ मिलता है, अतः $f$ एकैकी आच्छादक है। अंत में, एकैकी आच्छादक प्रतिचित्रण परिभाषा से ही एकैकी और आच्छादक दोनों है, जिससे निहितार्थों का चक्र बंद हो जाता है। ∎

उदाहरण 2.6 (परिमितता अनिवार्य है)

किसी परिमित समुच्चय पर प्रतिज्ञप्ति 2.5 एक सशक्त संक्षेप है: $E$ से स्वयं उसी में जाने वाला कोई भी एकैकी प्रतिचित्रण स्वतः $E$ का क्रमचय होता है — एकैकी आच्छादकता का आधा भाग मुफ़्त मिल जाता है। अनंत समुच्चयों पर दोनों निहितार्थ ढह जाते हैं: $n \mapsto n + 1$ $\N$ से $\N$ में एकैकी है पर $0$ तक नहीं पहुँचता, और $0 \mapsto 0$ तथा $n \geq 1$ के लिए $n \mapsto n - 1$ भेजने वाला प्रतिचित्रण $\N \to \N$ आच्छादक है पर एकैकी नहीं। जब भी यह प्रतिज्ञप्ति लगाई जाती है, परिमितता की परिकल्पना सचमुच काम कर रही होती है — यही विषय अध्याय 1 की सप्ताहांत समस्या दूसरी ओर से देखती है, जहाँ अनंत समुच्चय ठीक वही हैं जो ऐसे स्व-प्रतिचित्रण स्वीकार करते हैं।

उदाहरण 2.7 (आधा काम, मुफ़्त में)

$\{0, 1, \dots, 6\}$ पर उस प्रतिचित्रण $f$ पर विचार कीजिए जो $k$ को $7$ से भाग देने पर $3k$ के शेषफल पर भेजता है; उसकी मान-सारणी यह है

0,\ 3,\ 6,\ 2,\ 5,\ 1,\ 4 .

क्या $f$ एकैकी आच्छादक है? केवल एकैकीयता पर्याप्त है (प्रतिज्ञप्ति 2.5): यदि $3k$ और $3k'$ के शेषफल समान हों, तो $7$ $3(k - k')$ को विभाजित करता है, और चूँकि $7$ अभाज्य है और $3$ को विभाजित नहीं करता, अतः वह $k - k'$ को विभाजित करता है (यूक्लिड की प्रमेयिका, यहाँ विद्यालय स्तर पर प्रयुक्त और अध्याय 6 में सिद्ध); $\abs{k - k'} \leq 6$ के साथ इससे $k = k'$ आ जाता है। आच्छादकता मुफ़्त में मिलती है — प्रत्येक $c$ के लिए $3k \equiv c$ हल करने की आवश्यकता नहीं, यद्यपि सारणी पुष्टि करती है कि हर मान ठीक एक बार आता है। यह संक्षेप एक परिश्रमी घोड़ा है: वह मापांकी गुणन की उत्क्रमणीयता सिद्ध करता है (अध्याय 6), विल्सन की प्रमेय में युग्मन को शक्ति देता है, और रैखिक बीजगणित में “परिमित विमीय समष्टि का अंतःरूपांतरण एकैकी है यदि और केवल यदि वह आच्छादक है” के रूप में लौटता है (अध्याय 19)।

2.2 गणना के नियम

प्रतिज्ञप्ति 2.8 (योग और गुणन नियम)

मान लीजिए $E, F$ परिमित समुच्चय हैं।

यदि $E \cap F = \emptyset$ , तो $\abs{E \cup F} = \abs{E} + \abs{F}$ ; और अधिक व्यापक रूप से, $E$ के टुकड़ों $E_1, \dots, E_k$ में विभाजन के लिए $\abs{E} = \sum_i \abs{E_i}$ ।
सामान्य स्थिति में $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap F}$ ।
$\abs{E \times F} = \abs{E} \times \abs{F}$ .
$E$ से $F$ में जाने वाले सभी प्रतिचित्रणों का समुच्चय $F^E$ $\abs{F^E} = \abs{F}^{\abs{E}}$ को संतुष्ट करता है।
$\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

उपपत्ति. (1) गणनाओं को जोड़ दीजिए: यदि बिना पुनरावृत्ति के $E = \{x_1, \dots, x_m\}$ और $F = \{y_1, \dots, y_n\}$ , तो $x_1, \dots, x_m, y_1, \dots, y_n$ $E \cup F$ की बिना पुनरावृत्ति गणना कर देता है (असंयुक्तता से)। आगमन इसे $k$ टुकड़ों तक बढ़ा देता है।

(2) $E \cup F$ $E$ और $F \setminus E$ का असंयुक्त सम्मिलन है, तथा $F$ $F \cap E$ और $F \setminus E$ का असंयुक्त सम्मिलन है; अतः $\abs{E \cup F} = \abs{E} + \abs{F \setminus E} = \abs{E} + \abs{F} - \abs{E \cap F}$ ।

(3) $E \times F$ $x \in E$ पर, समुच्चयों $\{x\} \times F$ का असंयुक्त सम्मिलन है, जिनमें से प्रत्येक का गणनांक $\abs{F}$ है; (1) लगाइए।

(4) $E = \{x_1, \dots, x_m\}$ से $F$ में प्रतिचित्रण ठीक $m$ -उपक्रम $(f(x_1), \dots, f(x_m)) \in F^m$ का चयन है; यह अनुरूपता एक एकैकी आच्छादन है, और (3) तथा आगमन से $\abs{F^m} = \abs{F}^m$ ।

(5) $E$ के उपसमुच्चय प्रतिचित्रणों $E \to \{0, 1\}$ के साथ एकैकी आच्छादन में हैं ( $A$ को उसके सूचक फलन पर भेजिए); (4) लगाइए। ∎

उदाहरण 2.9 (पूरक द्वारा गणना)

$4$ अंकों वाले कितने पिन कोड (अंक $0$ – $9$ , क्रम महत्त्व रखता है, पुनरावृत्ति की अनुमति है) में कम से कम एक अंक दोहराया जाता है? उन्हें सीधे गिनने का अर्थ है “ठीक एक जोड़ा, दो जोड़े, एक तिकड़ी, एक चौकड़ी” — पाँच अतिव्यापी विन्यासों को साधना। इसके बदले पूरक गिनिए: सभी कोड $10^4 = 10\,000$ हैं (गुणन नियम), और चार भिन्न अंकों वाले कोड $10 \times 9 \times 8 \times 7 = 5\,040$ ( $4$ -विन्यास), अतः उत्तर है

10^4 - 10 \cdot 9 \cdot 8 \cdot 7 = 10\,000 - 5\,040 = 4\,960 .

लगभग आधे पिन कोडों में कोई अंक दोहराया जाता है। सार: जब भी गणना “कम से कम” या “सभी नहीं” के रूप में कही गई हो, पहले पूरक आज़माइए — योग नियम की गारंटी है कि $\abs{A} = \abs{E} - \abs{\overline A}$ , और पूरक प्रायः एक ही स्वच्छ विन्यास होता है।

उदाहरण 2.10 (जालक पथ)

जालक के कोने $(0,0)$ से कोने $(4, 3)$ तक के लघुतम पथ गिनिए, जहाँ हर बार केवल एक कदम दाएँ (R) या एक कदम ऊपर (U) चला जा सकता है। ऐसा प्रत्येक पथ ठीक $7$ कदम लेता है, जिनमें $4$ R और $3$ U हैं; विलोमतः, अक्षरों R, U का चार R वाला $7$ लंबाई का कोई भी शब्द ठीक एक पथ का वर्णन करता है। अतः पथ R के स्थानों के चयनों के साथ एकैकी आच्छादन में हैं:

\binom{7}{4} = 35 .

सार कूटन में है: जैसे ही हर पथ को एक शब्द में, अर्थात् स्थानों के उपसमुच्चय में, अनूदित किया गया, गणना तुच्छ हो गई — इस सूत्रवाक्य का एक और उदाहरण कि सही गणना छिपा हुआ एकैकी आच्छादन है (विधि 2.19)।

(0,0) से (4,3) तक के 74 = 35 लघुतम पथों में से एक: दिखाया गया पथ शब्द RURRURU का कूटन करता है, अर्थात् सात कदमों में अक्षर R के लिए स्थानों \1,3,4,6\ का चयन। — $(0,0)$ से $(4,3)$ तक के $\binom74 = 35$ लघुतम पथों में से एक: दिखाया गया पथ शब्द $\mathrm{RURRURU}$ का कूटन करता है, अर्थात् सात कदमों में अक्षर R के लिए स्थानों $\{1,3,4,6\}$ का चयन।

2.3 सूचियाँ, क्रमचय, उपसमुच्चय

परिभाषा 2.11 (विन्यास, क्रमचय, संचय)

मान लीजिए $E$ एक समुच्चय है, जहाँ $\abs{E} = n$ , और $0 \leq k \leq n$ ।

$E$ का $k$ -विन्यास $E$ के अवयवों का एकैकी $k$ -उपक्रम है (बिना पुनरावृत्ति का क्रमित चयन);
$E$ का क्रमचय $E$ से स्वयं उसी पर एकैकी आच्छादन है — समतुल्य रूप से, एक $n$ -विन्यास;
$k$ -संचय $E$ का $k$ अवयवों वाला उपसमुच्चय है (बिना पुनरावृत्ति का अक्रमित चयन)। उनकी संख्या $\binom{n}{k}$ लिखी जाती है, जिसे “ $n$ में से $k$ ” पढ़ते हैं।

प्रमेय 2.12 (तीनों गणनाएँ)

$n = \abs{E}$ और $0 \leq k \leq n$ के साथ:

$E$ के $k$ -विन्यासों की संख्या $n (n-1) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ है;
$E$ के क्रमचयों की संख्या $n!$ है;
$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

उपपत्ति. (1) पहला निर्देशांक चुनिए ( $n$ तरीके), फिर दूसरा ( $n - 1$ शेष चयन), …, फिर $k$ -वाँ ( $n - k + 1$ चयन)। औपचारिक रूप से $k$ पर आगमन कीजिए। $k = 1$ के लिए $n$ एक-पद वाले एकैकी उपक्रम हैं। गणना को $k - 1$ के लिए मान लीजिए। प्रत्येक $k$ -विन्यास $(x_1, \dots, x_k)$ ठीक एक $(k-1)$ -विन्यास — उसके काटे हुए रूप $(x_1, \dots, x_{k-1})$ — से, $\{x_1, \dots, x_{k-1}\}$ के बाहर एक अंतिम निर्देशांक जोड़कर प्राप्त होता है, जिसके लिए ठीक $n - (k - 1)$ मान उपलब्ध हैं। इस प्रकार $k$ -विन्यास, कटाई के द्वारा, $(k-1)$ -विन्यासों से सूचीबद्ध, $n - k + 1$ आकार वाले वर्गों में विभाजित हो जाते हैं, और योग नियम देता है

\frac{n!}{(n-k+1)!}\;(n - k + 1) = \frac{n!}{(n-k)!} .

(2) $k = n$ के साथ (1) ही है।

(3) प्रत्येक $k$ -उपसमुच्चय $k!$ भिन्न $k$ -विन्यासों में क्रमित होता है, और प्रत्येक $k$ -विन्यास ठीक एक उपसमुच्चय से उत्पन्न होता है: अतः $\frac{n!}{(n-k)!} = \binom nk \cdot k!$ । ∎

उदाहरण 2.13 (गोल मेज़: सममिति से भाग देना)

$n$ अतिथि गोल मेज़ के चारों ओर कितने प्रकार से बैठ सकते हैं, जबकि दो बैठकें तब समान मानी जाती हैं जब हर अतिथि के बाएँ और दाएँ वही पड़ोसी हों — अर्थात् घूर्णन तक? प्रत्येक वृत्तीय बैठक ठीक $n$ रैखिक बैठकों के अनुरूप है (वृत्त को $n$ स्थानों में से किसी पर काटिए), अतः $n!$ रैखिक क्रम $n$ के समूहों में सिमट जाते हैं:

\frac{n!}{n} = (n-1)! \quad\text{वृत्तीय बैठकें।}

समतुल्य रूप से: एक विशिष्ट अतिथि को कहीं भी बिठा दीजिए (जिससे घूर्णन की स्वतंत्रता समाप्त हो जाए), फिर शेष $n - 1$ अतिथियों को दक्षिणावर्त क्रम में रखिए। $n = 6$ के लिए: $120$ मेज़ें। दोनों हल अधिगणना के दो मानक उपाय दिखाते हैं: पुनरावृत्तियों की ठीक संख्या से भाग दीजिए, या एक वस्तु को कील ठोंककर सममिति भंग कर दीजिए। दोनों के लिए आवश्यक है कि पुनरावृत्ति-समूह का आकार हर विन्यास के लिए एक ही हो — यही ऊपर $\binom nk = \frac{n!}{k!\,(n-k)!}$ के सूत्र की उपपत्ति ने भी प्रयोग किया था, जहाँ $n$ के स्थान पर $k!$ था।

उदाहरण 2.14 (एक प्रतिबंध जोड़ना)

गोल मेज़ को आगे बढ़ाते हैं: $n \geq 3$ अतिथियों की $(n-1)!$ मेज़ों में कितनी दो दिए हुए अतिथियों $A$ और $B$ को अलग बिठाती हैं (सटा हुआ नहीं)? पूरक गिनिए। वे मेज़ें जिनमें $A$ और $B$ साथ बैठते हैं: उन्हें एक ही खंड में चिपका दीजिए — मेज़ के चारों ओर $n - 1$ वस्तुएँ, अर्थात् $(n-2)!$ वृत्तीय विन्यास — फिर युग्म को उसके खंड के भीतर क्रमित कीजिए ( $2$ तरीके): $2\,(n-2)!$ सटी हुई मेज़ें। अतः

(n-1)! - 2\,(n-2)! = (n-2)!\,\bigl((n - 1) - 2\bigr) = (n-3)\,(n-2)!

मेज़ें उन्हें अलग रखती हैं। जाँच: $n = 3$ से $0$ मिलता है (त्रिभुज के चारों ओर हर कोई हर किसी को छूता है) और $n = 4$ से $2$ , जिसे हाथ से आसानी से सूचीबद्ध किया जा सकता है। चिपकाने की युक्ति — बाध्य खंड को एक वस्तु मानिए, फिर उसके भीतरी विन्यास गिनिए — सटान-प्रतिबंधों का, रैखिक हो या वृत्तीय, मानक उपाय है।

प्रतिज्ञप्ति 2.15 (मूल सर्वसमिकाएँ)

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

\binom{n}{k} = \binom{n}{n-k}, \qquad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad (1 \leq k \leq n-1), \qquad \sum_{k=0}^{n} \binom{n}{k} = 2^n .

उपपत्ति. पहली सर्वसमिका: $A \mapsto E \setminus A$ $k$ -उपसमुच्चयों और $(n-k)$ -उपसमुच्चयों के बीच एकैकी आच्छादन है। पास्कल का नियम: एक अवयव $a \in E$ नियत कीजिए; $k$ -उपसमुच्चय उनमें बँट जाते हैं जो $a$ को समेटते हैं (शेष $k - 1$ चुनिए: $\binom{n-1}{k-1}$ ) और जो $a$ से बचते हैं ( $\binom{n-1}{k}$ )। तीसरी सर्वसमिका: दोनों पक्ष $E$ के सभी उपसमुच्चय गिनते हैं, बाईं ओर आकार के अनुसार बाँटकर (प्रतिज्ञप्ति 2.8 (1) और (5))। ∎

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

किसी क्रमविनिमेय वलय (मान लीजिए $\R$ या $\C$ ) के सभी $a, b$ और $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)$ का वितरण नियम से प्रसार करने पर, प्रत्येक गुणनखंड में $a$ या $b$ के हर चयन के लिए एक पद मिलता है: पद $a^k b^{n-k}$ उतनी बार आता है जितने प्रकार से $n$ गुणनखंडों में से $k$ $a$ का योगदान करने के लिए चुने जा सकते हैं — अर्थात् $\binom nk$ बार। (वैकल्पिक रूप से: पास्कल के नियम का प्रयोग करते हुए $n$ पर आगमन कीजिए।) ∎

उदाहरण 2.17

दो चिरपरिचित विशेषीकरण: $a = b = 1$ से $\sum_k \binom nk = 2^n$ मिलता है; $a = -1$ , $b = 1$ से $n \geq 1$ के लिए $\sum_{k} (-1)^k \binom nk = 0$ मिलता है: किसी अरिक्त समुच्चय के उपसमुच्चयों में ठीक आधे सम गणनांक वाले हैं।

उदाहरण 2.18 (एक सर्वसमिका, दो उपपत्तियाँ)

द्विपद प्रमेय का विशेषीकरण $a = 2$ , $b = 1$ यह कहता है

\sum_{k=0}^{n} \binom nk\,2^k = 3^n .

यही सर्वसमिका बिना किसी बीजगणित के भी मिलती है। दायाँ पक्ष वर्णमाला $\{0, 1, 2\}$ पर $n$ लंबाई के शब्द गिनता है (गुणन नियम)। प्रत्येक शब्द को अशून्य अक्षर वाले स्थानों के समुच्चय $K$ के अनुसार वर्गीकृत कीजिए: $\abs K = k$ वाला $K$ चुनने में $\binom nk$ लगता है, फिर $K$ का प्रत्येक स्थान स्वतंत्र रूप से $1$ या $2$ धारण करता है: $2^k$ तरीके। $k$ पर योग नियम बायाँ पक्ष दे देता है। सहमति के आनंद से आगे, दोनों उपपत्तियों के गुण भिन्न हैं: बीजीय उपपत्ति $a$ के किसी भी मान तक सामान्यीकृत होती है, जबकि संयोजनात्मक उपपत्ति सूत्र को समझाती है और ऐसे प्रतिबंधों के अनुकूल ढल जाती है (मान लीजिए अंतिम स्थान पर अक्षर $2$ निषिद्ध हो) जिन्हें कोई प्रतिस्थापन नहीं पकड़ पाता। दोनों तकनीकों को सक्रिय रखना ही वह व्यावहारिक कौशल है जिसका अभ्यास यह अध्याय कराता है।

विधि 2.19 (कौन-सी गणना लागू होती है?)

संगणना से पहले चयन के विषय में दो प्रश्नों के उत्तर दीजिए: क्या क्रम महत्त्व रखता है, और क्या पुनरावृत्ति की अनुमति है?

	क्रम महत्त्व रखता है	क्रम महत्त्व नहीं रखता
पुनरावृत्ति नहीं	$\dfrac{n!}{(n-k)!}$	$\dbinom{n}{k}$
[6pt] पुनरावृत्ति की अनुमति	$n^k$	(अभ्यास 2.10)

फिर ऐसा एकैकी आच्छादन या विभाजन खोजिए जो समस्या को इन आदर्श गणनाओं तक ले आए; सही गणना छिपा हुआ एकैकी आच्छादन है।

टिप्पणी 2.20 (गणना में सामान्य भूलें)

असंयुक्त न होने वाली स्थितियों को जोड़ना। योग नियम के लिए विभाजन चाहिए; यदि कोई विन्यास एक साथ दो स्थितियों को संतुष्ट कर सकता है, तो वह दो बार गिना जाता है — उपाय है समावेशन–अपवर्जन (प्रमेय 2.24) या और सूक्ष्म स्थिति-विभाजन।
क्रमित बनाम अक्रमित। “दो लोगों की समिति” चुनना $\binom n2$ है, $n(n-1)$ नहीं: संगणना से पहले तय कीजिए कि चयन क्रम धारण करता है या नहीं, और यदि क्रमित गणना आसान हो तो अंत में क्रमों की संख्या से भाग दीजिए — पर तभी, जब प्रत्येक अक्रमित वस्तु समान संख्या में क्रमित वस्तुओं से उत्पन्न होती हो।
बहु-चरणीय चयन जो स्वतंत्र नहीं हैं। गुणन नियम के लिए आवश्यक है कि हर चरण पर विकल्पों की संख्या पिछले चयनों से स्वतंत्र हो। “एक कप्तान चुनिए, फिर उससे भिन्न एक उपकप्तान” ठीक है ( $n(n-1)$ ); “ऐसे दो खिलाड़ी चुनिए जिनकी आपस में बनती हो” दो-चरणीय गुणन है ही नहीं।
रचना से ही दुहरी गणना। प्रत्येक वस्तु को दो बार बनाना — उदाहरणार्थ कम से कम एक इक्के वाले हाथ (एक इक्का चुनिए) $\times$ ( $4$ और पत्ते चुनिए) के रूप में गिनना — दो इक्कों वाले हाथों की अधिगणना कर देता है। “कम से कम” प्रायः सदा पूरक की माँग करता है (उदाहरण 2.9)।

उदाहरण 2.21 (ताश जैसी गणना)

$52$ पत्तों की गड्डी में से $5$ पत्तों के हाथों की संख्या $\binom{52}{5} = 2\,598\,960$ है। ठीक एक इक्के वाले हाथ: इक्का चुनिए ( $4$ तरीके), फिर $48$ गैर-इक्कों में से $4$ पत्ते: $4 \binom{48}{4} = 778\,320$ । गुणन नियम इसलिए लागू होता है कि चयन स्वतंत्र चरणों में बँट जाता है।

विधि 2.22 (दुहरी गणना)

दो गणना-व्यंजकों के बीच सर्वसमिका सिद्ध करने के लिए ऐसा एक परिमित समुच्चय खोजिए जिसे दोनों पक्ष गिनते हों — प्रायः युग्मों का समुच्चय — और उसका गणनांक दो भिन्न क्रमों में आँकिए। आदिरूप है हस्तमिलन प्रमेयिका: किसी समारोह में (व्यक्ति, मिलाया गया हाथ) युग्म गिनिए। लोगों पर योग करने से $\sum_p d_p$ मिलता है (प्रत्येक व्यक्ति $p$ के हस्तमिलनों की संख्या); हस्तमिलनों पर योग करने से हस्तमिलनों की संख्या का दुगुना (हर हस्तमिलन में दो व्यक्ति होते हैं)। अतः $\sum_p d_p$ सम है — अर्थात् विषम बार हाथ मिलाने वाले लोगों की संख्या सदा सम होती है, जो बिना किसी सूत्र के प्राप्त एक अतुच्छ निष्कर्ष है। यही इंजन अभ्यास 2.12 को और नीचे दी गई सप्ताहांत समस्या के कई प्रश्नों को चलाता है।

उदाहरण 2.23 (औसत उपसमुच्चय)

$n$ अवयवों वाले समुच्चय $E$ के उपसमुच्चय का औसत गणनांक क्या है, जबकि सभी $2^n$ उपसमुच्चय समसंभाव्य हैं? $a \in A$ वाले युग्मों $(A, a)$ की दुहरी गणना कीजिए: उपसमुच्चयों पर योग करने से $\sum_A \abs A$ मिलता है, जो अभीष्ट कुल है; अवयवों पर योग करने से $n \cdot 2^{n-1}$ मिलता है ( $n$ अवयवों में से प्रत्येक ठीक आधे उपसमुच्चयों में है — $a$ वाले प्रत्येक $A$ को $A \setminus \{a\}$ के साथ युग्मित कीजिए)। अतः

\frac{1}{2^n}\sum_{A \subseteq E} \abs A = \frac{n\,2^{n-1}}{2^n} = \frac n2 :

उपसमुच्चय औसतन आधे भरे होते हैं — जैसा सममिति $A \leftrightarrow \overline A$ (जो आकारों $k$ और $n - k$ को युग्मित करती है) भी बताती है। दो उपपत्तियाँ, एक उत्तर, और दोनों अभ्यास 2.5 की सीधी संगणना $\sum_k k\binom nk$ से बच जाती हैं: सुचयनित युग्मन प्रायः सर्वसमिका की जगह ले लेता है।

2.4 समावेशन–अपवर्जन

प्रमेय 2.24 (समावेशन–अपवर्जन)

परिमित समुच्चयों $A_1, \dots, A_p$ के लिए:

\Bigl|\, \bigcup_{i=1}^{p} A_i \,\Bigr| = \sum_{\emptyset \neq I \subseteq \intint{1}{p}} (-1)^{\abs{I}+1} \Bigl|\, \bigcap_{i \in I} A_i \,\Bigr| .

$p = 3$ के लिए: $\abs{A \cup B \cup C} = \abs A + \abs B + \abs C - \abs{A \cap B} - \abs{A \cap C} - \abs{B \cap C} + \abs{A \cap B \cap C}$ ।

उपपत्ति. सम्मिलन का एक अवयव $x$ नियत कीजिए और दाएँ पक्ष में उसका योगदान गिनिए। मान लीजिए $J = \{i : x \in A_i\}$ , जिसका गणनांक $m \geq 1$ है। अवयव $x$ $\abs{\bigcap_{i \in I} A_i}$ में ठीक तब एक बार गिना जाता है जब $\emptyset \neq I \subseteq J$ , और उसका चिह्न $(-1)^{\abs I + 1}$ होता है; उसका कुल योगदान है

\sum_{k=1}^{m} \binom{m}{k} (-1)^{k+1} = 1 - \sum_{k=0}^{m} \binom mk (-1)^k = 1 - 0 = 1

उदाहरण 2.17 से। अतः सम्मिलन का प्रत्येक अवयव ठीक एक बार गिना जाता है। ∎

उदाहरण 2.25 (सहअभाज्य पूर्णांकों की गणना)

$\intint1{120}$ के कितने पूर्णांक $120 = 2^3 \times 3 \times 5$ के सहअभाज्य हैं? कोई पूर्णांक $120$ के साथ गुणनखंड ठीक तब साझा करता है जब वह $2$ , $3$ या $5$ से विभाज्य हो, अतः $A_2 \cup A_3 \cup A_5$ का पूरक गिनिए, जहाँ $A_d$ $d$ के गुणजों को इकट्ठा करता है। $\intint1{120}$ के भीतर, जब भी $d$ $120$ को विभाजित करता है, $d$ के गुणज $120/d$ हैं — किसी फ़र्श फलन की आवश्यकता नहीं — और $A_2 \cap A_3 = A_6$ , इत्यादि। समावेशन–अपवर्जन:

\abs{A_2 \cup A_3 \cup A_5} = 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88 ,

अतः $120 - 88 = 32$ पूर्णांक $120$ के सहअभाज्य हैं। संगणना को गुणनफल के रूप में पुनर्समूहित करना शिक्षाप्रद है:

120 - 88 = 120\Bigl(1 - \frac12\Bigr)\Bigl(1 - \frac13\Bigr)\Bigl(1 - \frac15\Bigr) = 120 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 32 :

तीनों कोष्ठकों का प्रसार करने पर ठीक समावेशन–अपवर्जन के आठ चिह्नित पद मिलते हैं, $\{2, 3, 5\}$ के प्रत्येक उपसमुच्चय के लिए एक। यह गुणनफल-रूप ऑयलर का टोशंट फलन परिभाषित करता है, जिसकी अंकगणितीय भूमिका अध्याय 6 की सर्वांगसमताओं के साथ प्रकट होती है और स्नातक वर्ष 2 के खंड में विकसित की गई है।

उदाहरण 2.26 (व्यत्यय)

व्यत्यय ऐसा क्रमचय है जिसका कोई अचल बिंदु न हो। मान लीजिए $A_i$ $i$ को अचल रखने वाले $\intint{1}{n}$ के क्रमचयों का समुच्चय है; तब $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ , और समावेशन–अपवर्जन कम से कम एक अचल बिंदु वाले क्रमचय गिन देता है; व्यत्ययों की संख्या है

D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .

चूँकि $\sum (-1)^k / k! \to \eu^{-1}$ (अध्याय 17 देखिए), $n$ जो भी हो, सभी क्रमचयों में लगभग $37\%$ व्यत्यय होते हैं।

टिप्पणी 2.27 (यह अध्याय कहाँ काम आता है)

द्विपद गुणांक इस अध्याय की सबसे अधिक पुनःप्रयुक्त वस्तुएँ हैं: वे अध्याय 8 में द्विपद प्रमेय ( $(X + a)^n$ का प्रसार), अध्याय 14 में गुणनफल के $n$ -वें अवकलज का लाइब्निज़ सूत्र, और अध्याय 16 में टेलर प्रसारों के गुणांक चलाते हैं। क्रमचय अध्याय 7 में एक समूह के रूप में लौटते हैं — व्युत्क्रमण गिनकर बनाए गए चिह्न के साथ — और वही चिह्न अध्याय 22 में सारणिक परिभाषित करता है। समावेशन–अपवर्जन और गणना के नियम विविक्त प्रायिकता की परिमित रीढ़ हैं, जिसे स्नातक वर्ष 2 के खंड में विकसित किया गया है; उदाहरण 2.26 की व्यत्यय संख्याओं का गहन अध्ययन नीचे दी गई सप्ताहांत समस्या में है।

2.5 अभ्यास

अभ्यास 2.1 ★

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

हल

हल — अभ्यास 2.1.

स्वतंत्र चरण और गुणन नियम: $26^2 \times 10^3 \times 26^2 = 26^4 \times 1000 = 456\,976\,000$ पट्टिकाएँ। चारों अक्षर जोड़ों में भिन्न होने पर अक्षर वाले चरण वर्णमाला का $4$ -विन्यास बनाते हैं: $26 \times 25 \times 24 \times 23 = 358\,800$ तरीके, अतः $358\,800 \times 1000 = 358\,800\,000$ पट्टिकाएँ।

अभ्यास 2.2 ★

शब्द $\mathrm{ORANGE}$ के कितने वर्णविपर्यय (अक्षरों के पुनर्विन्यास, सार्थक हों या न हों) हैं? और $\mathrm{BANANA}$ के?

हल

हल — अभ्यास 2.2.

$\mathrm{ORANGE}$ में $6$ भिन्न अक्षर हैं: $6! = 720$ वर्णविपर्यय। $\mathrm{BANANA}$ में $6$ अक्षर हैं, जिनमें पुनरावृत्ति है ( $3$ a, $2$ n, $1$ b): प्रत्येक वर्णविपर्यय a के स्थानों ( $\binom 63$ चयन), फिर शेष $3$ स्थानों में n के स्थानों ( $\binom 32$ ) से निर्धारित हो जाता है, और b अंतिम स्थान ले लेता है: $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ वर्णविपर्यय (समतुल्य रूप से $6!/(3!\,2!\,1!) = 60$ )।

अभ्यास 2.3 ★

$7$ स्त्रियों और $5$ पुरुषों में से $4$ लोगों की एक समिति चुनी जाती है। कितनी समितियाँ: कुल मिलाकर? ठीक $2$ स्त्रियों वाली? कम से कम एक पुरुष वाली?

हल

हल — अभ्यास 2.3.

कुल: $\binom{12}{4} = 495$ । ठीक $2$ स्त्रियाँ: उन्हें चुनिए ( $\binom 72 = 21$ ) और $2$ पुरुष ( $\binom 52 = 10$ ): $210$ समितियाँ। कम से कम एक पुरुष: “कोई पुरुष नहीं” का पूरक, $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$ ।

अभ्यास 2.4 ★

सिद्ध कीजिए कि $13$ लोगों के किसी भी समूह में दो का जन्म-माह एक ही होता है; और यह कि $\intint{1}{2n}$ में से चुने गए किन्हीं $n + 1$ पूर्णांकों में दो क्रमागत होते हैं। (दोनों बार कबूतरखाना: डिब्बों के नाम बताइए।)

हल

हल — अभ्यास 2.4.

जन्मदिन: डिब्बे $12$ माह हैं; $13$ लोगों को $12$ डिब्बों में रखने पर दो एक ही डिब्बे में आ जाते हैं (उपप्रमेय 2.3)।

क्रमागत पूर्णांक: डिब्बे $n$ युग्म $\{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\}$ हैं, जो $\intint{1}{2n}$ का विभाजन करते हैं। $n + 1$ पूर्णांक चुनने पर दो एक ही युग्म में आ जाते हैं, और युग्म के दोनों अवयव क्रमागत हैं।

अभ्यास 2.5 ★

$\sum_{k=0}^{n} k \binom{n}{k}$ की संगणना कीजिए। संकेत: $(1 + x)^n$ का अवकलन कीजिए, या $k \binom nk = n \binom{n-1}{k-1}$ का प्रयोग कीजिए (उसे सिद्ध कीजिए)।

हल

हल — अभ्यास 2.5.

$1 \leq k \leq n$ के लिए,

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

$j = k - 1$ से योग करके और पुनःसूचीबद्ध करके:

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

प्रतिज्ञप्ति 2.15 से। (वैकल्पिक: $(1+x)^n = \sum_k \binom nk x^k$ का अवकलन कीजिए और $x = 1$ रखिए।)

अभ्यास 2.6 ★★

$\intint{1}{k}$ से $\intint{1}{n}$ में कितने पूर्णतः वर्धमान प्रतिचित्रण हैं? उससे वर्धमान (जो पूर्णतः वर्धमान होना आवश्यक नहीं) प्रतिचित्रणों की संख्या निकालिए। दूसरी गणना के लिए संकेत: $f$ वर्धमान $\mapsto$ $g(i) = f(i) + i - 1$ ।

हल

हल — अभ्यास 2.6.

पूर्णतः वर्धमान प्रतिचित्रण $f \colon \intint{1}{k} \to \intint{1}{n}$ अपने प्रतिबिंब से, जो $\intint{1}{n}$ का $k$ -उपसमुच्चय है, निर्धारित हो जाता है (उपसमुच्चय को बढ़ते क्रम में लिखिए); विलोमतः प्रत्येक $k$ -उपसमुच्चय ठीक एक ऐसा प्रतिचित्रण देता है। अतः $\binom nk$ पूर्णतः वर्धमान प्रतिचित्रण हैं।

यदि $f$ केवल वर्धमान है, तो $g(i) = f(i) + i - 1$ रखिए। तब $g$ पूर्णतः वर्धमान है (क्रमागत प्रांतिकों के बीच $f$ $\geq 0$ बढ़ता है और $i - 1$ $1$ बढ़ता है) और उसके मान $\intint{1}{n + k - 1}$ में हैं; और $f(i) = g(i) - i + 1$ $\intint{1}{n+k-1}$ में जाने वाले किसी भी पूर्णतः वर्धमान $g$ से $f$ वापस दे देता है। यह एकैकी आच्छादन है, अतः $\binom{n + k - 1}{k}$ वर्धमान प्रतिचित्रण हैं।

अभ्यास 2.7 ★★

(वांडरमोंड) $m$ और $n$ आकार के दो खंडों में बँटे समुच्चय के $k$ -उपसमुच्चय गिनकर सिद्ध कीजिए:

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

$\sum_{j=0}^{n} \binom nj^2 = \binom{2n}{n}$ निकालिए।

हल

हल — अभ्यास 2.7.

$m + n$ अवयवों वाले समुच्चय $E$ को खंडों $M$ ( $m$ अवयव) और $N$ ( $n$ अवयव) में बाँटिए। $E$ का कोई $k$ -उपसमुच्चय $M$ के कुछ $j$ अवयव ( $0 \leq j \leq k$ ) और $N$ के $k - j$ अवयव समेटता है; नियत $j$ के लिए ऐसे $\binom mj \binom{n}{k-j}$ उपसमुच्चय हैं, और स्थितियाँ $j = 0, \dots, k$ $k$ -उपसमुच्चयों का विभाजन करती हैं। योग नियम वांडरमोंड सर्वसमिका दे देता है।

$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$ का प्रयोग किया गया।

अभ्यास 2.8 ★★

$\intint{1}{1000}$ के कितने पूर्णांक $2$ या $3$ या $5$ से विभाज्य हैं? (समावेशन–अपवर्जन; $\lfloor 1000/6 \rfloor$ $6$ के गुणज गिनता है, इत्यादि।)

हल

हल — अभ्यास 2.8.

मान लीजिए $A_d$ $\intint{1}{1000}$ में $d$ के गुणज हैं, अतः $\abs{A_d} = \lfloor 1000/d \rfloor$ । $A_2, A_3, A_5$ के साथ समावेशन–अपवर्जन (प्रमेय 2.24), यह देखते हुए कि $A_2 \cap A_3 = A_6$ इत्यादि:

500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 .

अतः $734$ पूर्णांक $2$ , $3$ या $5$ से विभाज्य हैं।

अभ्यास 2.9 ★★

$4$ अवयवों के समुच्चय से $2$ अवयवों के समुच्चय पर आच्छादनों की गणना कीजिए; फिर $3$ अवयवों के समुच्चय पर। संकेत: छूट गए मानों पर समावेशन–अपवर्जन से अनाच्छादक प्रतिचित्रण गिनिए।

हल

हल — अभ्यास 2.9.

$2$ अवयवों पर: सभी $2^4 = 16$ प्रतिचित्रण, केवल $2$ अचर प्रतिचित्रण छोड़कर: $14$ आच्छादन।

$3$ अवयवों पर: छूट गए मानों पर समावेशन–अपवर्जन से, $4$ -समुच्चय से $3$ -समुच्चय में जाने वाले, कम से कम एक मान छोड़ने वाले प्रतिचित्रणों की संख्या $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$ है; कुल प्रतिचित्रण $3^4 = 81$ ; आच्छादन: $81 - 45 = 36$ । (जाँच: $4$ से $3$ अवयवों पर कोई आच्छादन ठीक एक मान को दुहराता है: दुहराया गया मान चुनिए ( $3$ ), उस पर जाने वाला युग्म ( $\binom 42 = 6$ ), और शेष के लिए एक एकैकी आच्छादन ( $2$ ): $3 \times 6 \times 2 = 36$ ।)

अभ्यास 2.10 ★★

(तारे और छड़ें) सिद्ध कीजिए कि $n$ वस्तुओं के, पुनरावृत्ति सहित और क्रम की उपेक्षा करते हुए, $k$ -चयनों की संख्या — समतुल्य रूप से, $x_1 + \dots + x_n = k$ वाले $(x_1, \dots, x_n) \in \N^n$ की संख्या — $\binom{n + k - 1}{k}$ है। संकेत: किसी हल को $k$ तारों और $n - 1$ छड़ों की एक पंक्ति के रूप में कूटित कीजिए।

हल

हल — अभ्यास 2.10.

$\N^n$ में $x_1 + \dots + x_n = k$ का हल $k$ तारों और $n - 1$ छड़ों की एक पंक्ति के रूप में कूटित होता है: $x_1$ तारे लिखिए, एक छड़, $x_2$ तारे, एक छड़, …, और अंत में $x_n$ तारे। यह $k$ तारों और $n - 1$ छड़ों का प्रयोग करने वाले $k + n - 1$ लंबाई के शब्दों पर एकैकी आच्छादन है, और वे शब्द तारों के स्थानों से निर्धारित होते हैं: $\binom{n + k - 1}{k}$ । पुनरावृत्ति सहित चयन समीकरण के हलों के अनुरूप हैं ( $x_i$ = वस्तु $i$ की प्रतियों की संख्या), अतः गणना वही है।

अभ्यास 2.11 ★★★

$D_n$ के लिए उदाहरण 2.26 का सूत्र विस्तार से सिद्ध कीजिए, और उससे $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ निकालिए (इस सर्वसमिका को क्रमचयों का उनके अचल-बिंदु समुच्चय के अनुसार वर्गीकरण करके सीधे भी सिद्ध कीजिए)।

हल

हल — अभ्यास 2.11.

$A_i = \{\sigma : \sigma(i) = i\}$ के साथ, $\bigcap_{i \in I} A_i$ का क्रमचय प्रत्येक $i \in I$ को अचल रखता है और शेष $n - \abs I$ बिंदुओं को स्वतंत्र रूप से क्रमित करता है: $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ । समावेशन–अपवर्जन:

\Bigl|\bigcup_i A_i\Bigr| = \sum_{k=1}^{n} (-1)^{k+1} \binom nk (n-k)! = \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} ,

क्योंकि $k$ आकार के $I$ उपसमुच्चय $\binom nk$ हैं। अतः

D_n = n! - \Bigl|\bigcup_i A_i\Bigr| = n!\Bigl(1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}\Bigr) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .

दूसरी सर्वसमिका के लिए: $\intint{1}{n}$ के क्रमचयों $\sigma$ को उनके अचल-बिंदु समुच्चय $F(\sigma)$ के अनुसार वर्गीकृत कीजिए। नियत $k$ -उपसमुच्चय $F$ के लिए, $F(\sigma) = F$ वाले क्रमचय ठीक पूरक के व्यत्यय हैं: उनकी संख्या $D_{n-k}$ है। प्रत्येक $k$ के लिए $F$ के $\binom nk$ चयनों पर योग करने से: $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$ ।

अभ्यास 2.12 ★★★

$n \in \N^*$ के लिए (उपसमुच्चय, चिह्नित अवयव) युग्मों की दुहरी गणना से सिद्ध कीजिए:

\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1}, \qquad\text{फिर}\qquad \sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .

दूसरी के लिए: चिह्नित अवयवों के युग्म गिनिए, चाहे वे बराबर हों या नहीं।

हल

हल — अभ्यास 2.12.

पहली सर्वसमिका। ऐसे युग्म $(A, a)$ गिनिए जिनमें $A \subseteq E$ ( $\abs E = n$ ) और $a \in A$ । $A$ के आकार के अनुसार: $\sum_k \binom nk k$ युग्म। पहले चिह्नित अवयव चुनने पर: $a$ के लिए $n$ चयन, फिर $A$ पूरा करने के लिए शेष $n - 1$ अवयवों का कोई भी उपसमुच्चय: $n\,2^{n-1}$ युग्म।

दूसरी सर्वसमिका। $a, b \in A$ वाली त्रिकियाँ $(A, a, b)$ गिनिए ( $a = b$ भी संभव है)। आकार के अनुसार: $\sum_k k^2 \binom nk$ । सीधे: या तो $a = b$ ( $n\,2^{n-1}$ त्रिकियाँ, पिछली गणना) या $a \neq b$ ( $n(n-1)$ क्रमित चयन, फिर शेष $n - 2$ अवयवों का कोई भी उपसमुच्चय: $n(n-1)\,2^{n-2}$ )। कुल

n\,2^{n-1} + n(n-1)\,2^{n-2} = n\,2^{n-2}\,(2 + n - 1) = n(n+1)\,2^{n-2} .

2.6 समस्या: व्यत्यय, अथवा ग़लत पते वाले पत्र

समस्या 2.1

कोई सचिव $n$ पते लिखे लिफ़ाफ़ों में $n$ पत्र यादृच्छिक रूप से रखता है: इसकी क्या संभावना है कि किसी को भी सही पत्र न मिले? यह चिरपरिचित प्रश्न (मोंमोर, 1708) उदाहरण 2.26 की व्यत्यय संख्याओं $D_n$ तक ले जाता है। समावेशन–अपवर्जन का सूत्र तो केवल पहली चाल है: यह समस्या $D_n$ की संगणना करने वाली पुनरावृत्तियाँ, सूत्र की दो और स्वतंत्र उपपत्तियाँ, यह चौंकाने वाली प्रमेय कि $D_n$ $n!/\eu$ के निकटतम पूर्णांक है, यादृच्छिक क्रमचय के अचल बिंदुओं का पूरा बंटन, और अनुक्रम $(D_n)$ का कुतूहलजनक अंकगणित विकसित करती है। आगे सर्वत्र $D_n$ $\intint1n$ के व्यत्ययों (अचल-बिंदु रहित क्रमचयों) की संख्या है, और परिपाटी $D_0 = 1$ है (रिक्त क्रमचय का कोई अचल बिंदु नहीं है)।

भाग I — छोटी स्थितियाँ और अचल-बिंदु जनगणना।

$D_1, D_2, D_3$ की सीधे संगणना कीजिए, और $D_4$ की संगणना $\{1, 2, 3, 4\}$ के व्यत्ययों को $\sigma(1)$ के मान के अनुसार समूहबद्ध करके सूचीबद्ध करते हुए कीजिए। (आपको $D_4 = 9$ मिलना चाहिए।)
$0 \leq k \leq n$ के लिए दिखाइए कि $\intint1n$ के ठीक $k$ अचल बिंदुओं वाले क्रमचयों की संख्या $P_k(n)$ $\binom nk D_{n-k}$ है।
$n = 4$ के लिए जनगणना सत्यापित कीजिए: $P_0(4), \dots, P_4(4)$ की संगणना कीजिए और जाँचिए कि उनका योग $4! = 24$ है। चार पत्रों के लिए क्या अधिक संभावित है: कोई मेल नहीं, या ठीक एक मेल?
$\sigma(i) = i$ वाले युग्मों $(\sigma, i)$ की दुहरी गणना (विधि 2.22) से दिखाइए कि

$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$

अर्थात् $n \geq 1$ जो भी हो, यादृच्छिक क्रमचय में औसतन ठीक एक अचल बिंदु होता है।

भाग II — दो पुनरावृत्तियाँ और सूत्र की दो नई उपपत्तियाँ।

$n \geq 1$ के लिए संयोजनात्मक रूप से सिद्ध कीजिए:

$D_{n+1} = n\,(D_n + D_{n-1}) .$

( $\intint1{n+1}$ के व्यत्ययों $\sigma$ को पहले $j = \sigma(n+1)$ के अनुसार, फिर इस आधार पर वर्गीकृत कीजिए कि $\sigma(j) = n + 1$ है या नहीं; $\sigma(j) \neq n+1$ की स्थिति में $n + 1$ के पूर्वप्रतिबिंब की दिशा $j$ की ओर मोड़कर $\intint1n$ के व्यत्ययों के साथ एकैकी आच्छादन बनाइए।) पुनरावृत्ति को $D_6$ तक संख्यात्मक रूप से जाँचिए।
$u_n = D_n - n D_{n-1}$ रखकर प्रश्न 5 से $u_{n+1} = -u_n$ निकालिए, और दूसरी पुनरावृत्ति पर पहुँचिए:

$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$
प्रश्न 6 से आगमन द्वारा उदाहरण 2.26 का सूत्र सिद्ध कीजिए,

$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$

— ऐसी उपपत्ति जो समावेशन–अपवर्जन से पूर्णतः स्वतंत्र है।
(द्विपद प्रतिलोमन) मान लीजिए $(a_n)$ और $(b_n)$ ऐसे दो अनुक्रम हैं कि सभी $n$ के लिए $a_n = \sum_{k=0}^n \binom nk b_k$ । सिद्ध कीजिए कि

$b_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k \qquad (n \in \N).$

(पहले त्रिपद पुनर्लेखन $\binom nk \binom kj = \binom nj \binom{n-j}{k-j}$ स्थापित कीजिए, फिर उदाहरण 2.17 के एकांतरित पंक्ति-योग का प्रयोग कीजिए।)
अभ्यास 2.11 की सर्वसमिका $n! = \sum_k \binom nk D_{n-k}$ पर प्रश्न 8 लगाकर $D_n$ के सूत्र की तीसरी उपपत्ति प्राप्त कीजिए।

भाग III — $n!/\eu$ का निकटतम पूर्णांक। इस भाग के लिए यह मान लीजिए — सिद्धांत अध्याय 17 में खड़ा किया गया है — कि $\eu^{-1} = \lim_{n \to \infty} s_n$ , जहाँ $s_n = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ , और प्रत्येक $n$ के लिए कठोर एकांतरित-श्रेणी परिबंध $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ है।

दिखाइए कि सभी $n \in \N$ के लिए $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ ।
मुख्य प्रमेय निकालिए: प्रत्येक $n \geq 1$ के लिए $D_n$ $n!/\eu$ का निकटतम पूर्णांक है। तर्क को $n \geq 1$ की आवश्यकता क्यों है?
त्रुटि का चिह्न निर्धारित कीजिए: दिखाइए कि $D_n > n!/\eu$ ठीक तब जब $n$ सम हो। (एकांतरित श्रेणी का पहला उपेक्षित पद ढूँढ़िए।)
प्रश्न 5 की पुनरावृत्ति से $D_7$ से $D_{10}$ तक की संगणना कीजिए, फिर $D_{10}$ को $10!/\eu$ के सामने जाँचिए ( $10! = 3\,628\,800$ , $\eu \approx 2.718281828$ )।
(टोपी-वापसी प्रायिकता) मान लीजिए $p_n = D_n/n!$ वह प्रायिकता है कि समरूप यादृच्छिक क्रमचय व्यत्यय है। दिखाइए $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ और $p_6$ की पाँच दशमलव स्थानों तक संगणना कीजिए। टिप्पणी कीजिए: मोंमोर के प्रश्न का उत्तर $n$ से मूलतः स्वतंत्र क्यों है — वह भी दर्जन भर पत्रों पर ही?

भाग IV — अचल बिंदुओं का बंटन।

$k \in \N$ नियत कीजिए। दिखाइए कि $\intint1n$ के ठीक $k$ अचल बिंदुओं वाले क्रमचयों का अनुपात यह संतुष्ट करता है

$\frac{P_k(n)}{n!} = \frac{s_{n-k}}{k!} \;\xrightarrow[n \to \infty]{}\; \frac{\eu^{-1}}{k!} .$

(ये सीमांत मान, जिनका योग $1$ है, प्राचल $1$ का प्वासों बंटन बनाते हैं, जो स्नातक वर्ष 2 के खंड के प्रायिकता पाठ्यक्रम की एक केंद्रीय वस्तु है।)
ऐसी त्रिकियों $(\sigma, i, j)$ की दुहरी गणना से, जिनमें $i \neq j$ दोनों $\sigma$ द्वारा अचल रखे जाते हैं, दिखाइए कि $n \geq 2$ के लिए $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\, (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ । प्रश्न 4 के साथ मिलाकर: $\abs{\mathrm{Fix}}^2$ का औसत $2$ है, अतः अचल बिंदुओं की संख्या का “फैलाव” (प्रसरण) $1$ के बराबर है — फिर $n$ से स्वतंत्र, और फिर प्वासों नियम के अनुरूप।
$n = 4, 5, 6$ के लिए कम से कम एक अचल बिंदु वाले क्रमचयों का अनुपात संगणित कीजिए (भिन्न के रूप में और चार दशमलव स्थानों तक), और $1 - \eu^{-1} \approx 0.6321$ से तुलना कीजिए।
सीधे — बिना किसी सीमा के — दिखाइए कि $s_{n+2} - s_n = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , और उससे निकालिए कि प्रश्न 14 की प्रायिकताएँ $p_n = s_n$ दोलन करती हैं: $p_0 > p_2 > p_4 > \dots$ और $p_1 < p_3 < p_5 < \dots$ , जहाँ सम (क्रमशः विषम) मान उभयनिष्ठ सीमा $\eu^{-1}$ की ओर घटते (क्रमशः बढ़ते) हैं।
(गुप्त उपहार) $n$ लोगों में से हर एक टोपी से एक नाम निकालता है; यदि किसी को अपना ही नाम निकल आए, तो पूरा निष्कर्षण नए सिरे से दोहराया जाता है। इस मानक तथ्य का प्रयोग करते हुए कि प्रायिकता $p$ की घटना में औसतन $1/p$ प्रयास लगते हैं, आवश्यक पूर्ण निष्कर्षणों की औसत संख्या का आकलन कीजिए, और निष्कर्ष निकालिए कि यह प्रक्रिया औसतन लगभग $\eu \approx 2.72$ निष्कर्षणों की पड़ती है, और वह भी $n$ से मूलतः स्वतंत्र रूप से।

भाग V — $D_n$ का अंकगणित, और एक संश्लेषण।

प्रश्न 5 को परिष्कृत कीजिए: दिखाइए कि नियत $j \in \intint2n$ के लिए $\sigma(1) = j$ वाले $\intint1n$ के व्यत्ययों की संख्या ठीक $D_{n-1} + D_{n-2}$ है, और वह $j$ से स्वतंत्र है। उससे निकालिए कि प्रत्येक $n \geq 2$ के लिए $n - 1$ $D_n$ को विभाजित करता है।
सिद्ध कीजिए कि $D_n$ विषम है यदि और केवल यदि $n$ सम हो। (प्रश्न 6 की पुनरावृत्ति में $2$ के सापेक्ष काम कीजिए।)
सिद्ध कीजिए कि $n \geq 1$ के लिए $D_n \equiv (-1)^n \pmod n$ , और सर्वांगसमता को $D_{10}$ के अंतिम अंक पर जाँचिए।
प्रश्न 6 से दिखाइए कि $n \geq 3$ के लिए $\dfrac{D_n}{D_{n-1}} = n + \dfrac{(-1)^n}{D_{n-1}}$ , अतः क्रमागत व्यत्यय संख्याओं का अनुपात लगभग ठीक $n$ है; एक वाक्य में समझाइए कि यह $D_n \approx n!/\eu$ के अनुरूप क्यों है।
इस समस्या में ठीक कहाँ प्रयोग हुआ: (क) गुणन और योग नियम; (ख) दुहरी गणना; (ग) द्विपद प्रमेय; (घ) स्वीकृत एकांतरित-श्रेणी परिबंध? प्रत्येक के लिए एक वाक्य।
संश्लेषण। $D_n$ के सूत्र की अब तीन उपपत्तियाँ हैं (समावेशन–अपवर्जन, पुनरावृत्ति के साथ आगमन, द्विपद प्रतिलोमन)। एक छोटे अनुच्छेद में तुलना कीजिए कि प्रत्येक उपपत्ति क्या समझाती है: कौन-सी सबसे तेज़ संगणना करती है, कौन-सी अन्य अचल-बिंदु गणनाओं तक सामान्यीकृत होती है, और कौन-सी यह प्रकट करती है कि लिफ़ाफ़ों की समस्या में $\eu$ क्यों आ जाता है।

हल

हल — समस्या 2.1.

1. $D_1 = 0$ (एकमात्र क्रमचय $1$ को अचल रखता है), $D_2 = 1$ (अदला-बदली), $D_3 = 2$ (एक-पंक्ति संकेतन में: $231$ और $312$ )। $n = 4$ के लिए $\sigma(1)$ के अनुसार समूहबद्ध कीजिए: $\sigma(1) = 2$ के साथ व्यत्यय $2143$ , $2341$ , $2413$ हैं; $\sigma(1) = 3$ के साथ: $3142$ , $3412$ , $3421$ ; $\sigma(1) = 4$ के साथ: $4123$ , $4312$ , $4321$ । हर समूह में तीन: $D_4 = 9$ ।

2. ठीक $k$ अचल बिंदुओं वाला क्रमचय अपने अचल-बिंदु समुच्चय $F$ के चयन ( $\binom nk$ तरीके) तथा पूरक पर अपने प्रतिबंधन से निर्धारित होता है, और वह प्रतिबंधन $n - k$ बिंदुओं का ऐसा क्रमचय होना चाहिए जिसका कोई अचल बिंदु न हो ( $D_{n-k}$ तरीके)। दोनों चयन स्वतंत्र हैं और अनुरूपता एकैकी आच्छादक है: $P_k(n) = \binom nk D_{n-k}$ ।

3. $P_0(4) = D_4 = 9$ ; $P_1(4) = \binom41 D_3 = 4 \times 2 = 8$ ; $P_2(4) = \binom42 D_2 = 6$ ; $P_3(4) = \binom43 D_1 = 0$ (तीन अचल बिंदु चौथे को बाध्य कर देते हैं); $P_4(4) = 1$ । योग: $9 + 8 + 6 + 0 + 1 = 24 = 4!$ । कोई मेल नहीं ( $9$ स्थितियाँ) ठीक एक मेल ( $8$ स्थितियाँ) से — थोड़े ही अंतर से — आगे है।

4. $\sigma(i) = i$ वाले युग्म $(\sigma, i)$ गिनिए। नियत $i$ के लिए $i$ को अचल रखने वाले क्रमचय शेष $n - 1$ बिंदुओं के क्रमचय हैं: उनकी संख्या $(n-1)!$ है। अतः युग्मों की संख्या $n \cdot (n-1)! = n!$ है, और यही संख्या $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$ भी है। क्रमचयों की संख्या $n!$ से भाग देने पर: अचल बिंदुओं की औसत संख्या प्रत्येक $n \geq 1$ के लिए ठीक $1$ है।

5. मान लीजिए $\sigma$ $\intint1{n+1}$ का व्यत्यय है और $j = \sigma(n+1) \in \intint1n$ : $n$ संभव मान। स्थिति $\sigma(j) = n+1$ : बिंदु $j$ और $n+1$ अदला-बदली कर लेते हैं, और शेष $n - 1$ बिंदुओं पर $\sigma$ का प्रतिबंधन उनका कोई भी व्यत्यय है: $D_{n-1}$ संभावनाएँ। स्थिति $\sigma(j) \neq n+1$ : मान लीजिए $i_0 = \sigma^{-1}(n+1)$ ; यहाँ $i_0 \neq j$ और $i_0 \leq n$ । $\intint1n$ पर $\tau$ इस प्रकार परिभाषित कीजिए: $i \neq i_0$ के लिए $\tau(i) = \sigma(i)$ और $\tau(i_0) = j$ । तब $\tau$ $\intint1n$ का क्रमचय है (मान $n+1$ के स्थान पर छूटा हुआ मान $j$ आ गया है), और वह व्यत्यय है: $\tau(i_0) = j \neq i_0$ , तथा अन्यत्र $\tau(i) = \sigma(i) \neq i$ । विलोमतः, $\intint1n$ के व्यत्यय $\tau$ और मान $j$ से $\sigma(n+1) = j$ , $\sigma(\tau^{-1}(j)) = n+1$ रखकर तथा अन्यत्र $\sigma = \tau$ रखकर $\sigma$ वापस मिल जाता है: यह एकैकी आच्छादन है, जो $D_n$ संभावनाएँ देता है। $j$ पर योग करने से: $D_{n+1} = n(D_n + D_{n-1})$ । संख्यात्मक रूप से: $D_5 = 4(9 + 2) = 44$ , $D_6 = 5(44 + 9) = 265$ ।

6. प्रश्न 5 से $D_{n+1} = nD_n + nD_{n-1}$ , अतः

u_{n+1} = D_{n+1} - (n+1)D_n = nD_n + nD_{n-1} - (n+1)D_n = -(D_n - nD_{n-1}) = -u_n .

चूँकि $u_1 = D_1 - 1 \cdot D_0 = -1$ , आगमन से $u_n = (-1)^n$ मिलता है, अर्थात् $n \geq 1$ के लिए $D_n = nD_{n-1} + (-1)^n$ ।

7. $n$ पर आगमन। आधार: $D_0 = 1 = 0!\,s_0$ । पद: $D_{n-1} = (n-1)!\,s_{n-1}$ मानने पर,

D_n = nD_{n-1} + (-1)^n = n!\,s_{n-1} + (-1)^n = n!\Bigl(s_{n-1} + \frac{(-1)^n}{n!}\Bigr) = n!\,s_n ,

जो वही सूत्र है। समावेशन–अपवर्जन का प्रयोग कहीं नहीं हुआ: केवल प्रश्न 5 की संयोजनात्मक पुनरावृत्ति का।

8. त्रिपद पुनर्लेखन, क्रमगुणितों से:

\binom nk \binom kj = \frac{n!}{k!\,(n-k)!} \cdot \frac{k!}{j!\,(k-j)!} = \frac{n!}{j!\,(n-j)!} \cdot \frac{(n-j)!}{(k-j)!\,(n-k)!} = \binom nj \binom{n-j}{k-j} .

अब $a_k = \sum_j \binom kj b_j$ प्रतिस्थापित कीजिए और दोनों परिमित योगों की अदला-बदली कीजिए:

\sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k = \sum_{j=0}^{n} b_j \binom nj \sum_{k=j}^{n} (-1)^{n-k} \binom{n-j}{k-j} = \sum_{j=0}^{n} b_j \binom nj \sum_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} .

भीतरी योग $(1 + (-1))^{n-j} = 0^{n-j}$ का प्रसार है (द्विपद प्रमेय, प्रमेय 2.16): वह $j < n$ के लिए लुप्त हो जाता है और $j = n$ के लिए $1$ के बराबर है। केवल $j = n$ बचता है, और दायाँ पक्ष $b_n$ है, जैसा दावा किया गया था।

9. सममिति $\binom nk = \binom n{n-k}$ से अभ्यास 2.11 की सर्वसमिका $n! = \sum_{k=0}^n \binom nk D_k$ के रूप में फिर से लिखी जाती है। $a_n = n!$ और $b_k = D_k$ के साथ प्रश्न 8 लगाइए:

D_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk k! = \sum_{k=0}^{n} (-1)^{n-k} \frac{n!}{(n-k)!} = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!} ,

$j = n - k$ से पुनःसूचीबद्ध करने पर: वही सूत्र तीसरी बार।

10. $D_n = n!\,s_n$ (प्रश्न 7), अतः

\Bigl| D_n - \frac{n!}{\eu} \Bigr| = n!\,\abs{s_n - \eu^{-1}} < \frac{n!}{(n+1)!} = \frac1{n+1} .

11. $n \geq 1$ के लिए $\frac1{n+1} \leq \frac12$ , और प्रश्न 10 की असमिका कठोर है: $D_n$ $n!/\eu$ से $< \frac12$ दूरी पर है, अतः वही अद्वितीय निकटतम पूर्णांक है। $n = 0$ के लिए परिबंध केवल $< 1$ दूरी देता है, और सचमुच दावा वहाँ विफल हो जाता है: $0!/\eu \approx 0.368$ का निकटतम पूर्णांक $0$ है, जबकि $D_0 = 1$ ।

12. $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ कठोरतः घटते पदों वाली एकांतरित श्रेणी है, अतः उसका चिह्न उसके पहले पद $(-1)^{n+1}/(n+1)!$ का चिह्न है। अतः $s_n - \eu^{-1}$ का चिह्न $(-1)^n$ का चिह्न है: $n$ सम होने पर $s_n > \eu^{-1}$ और $D_n = n!\,s_n > n!/\eu$ ; $n$ विषम होने पर $D_n < n!/\eu$ ।

13. $D_7 = 6(265 + 44) = 6 \times 309 = 1854$ ; $D_8 = 7(1854 + 265) = 7 \times 2119 = 14\,833$ ; $D_9 = 8(14\,833 + 1854) = 8 \times 16\,687 = 133\,496$ ; $D_{10} = 9(133\,496 + 14\,833) = 9 \times 148\,329 = 1\,334\,961$ । जाँच: $10!/\eu = 3\,628\,800 / 2.718281828 \approx 1\,334\,960.92$ , जिसका निकटतम पूर्णांक $1\,334\,961$ है — और $D_{10} > 10!/\eu$ , जैसा प्रश्न 12 सम $n$ के लिए बताता है।

14. $\abs{p_n - \eu^{-1}} = \abs{s_n - \eu^{-1}} < \frac1{(n+1)!}$ । $n = 6$ के लिए: $p_6 = 265/720 = 0.36806$ (पाँच दशमलव), जबकि $\eu^{-1} = 0.36788$ ; अंतर $1/7! = 1/5040 < 2 \times 10^{-4}$ से कम है। परिबंध $1/(n+1)!$ इतनी तेज़ी से ढहता है कि दर्जन भर पत्रों पर ही प्रायिकता अनेक दशमलव स्थानों तक स्थिर हो जाती है: “लगभग $36.8\%$ ” वाला उत्तर हर व्यावहारिक प्रयोजन के लिए $n$ से स्वतंत्र है — यही इस समस्या का प्रसिद्ध विस्मय है।

15. प्रश्न 2 और $D_m = m!\,s_m$ से:

\frac{P_k(n)}{n!} = \frac{\binom nk D_{n-k}}{n!} = \frac{D_{n-k}}{k!\,(n-k)!} = \frac{s_{n-k}}{k!} \;\longrightarrow\; \frac{\eu^{-1}}{k!}

जब $k$ नियत रखते हुए $n \to \infty$ , क्योंकि $s_{n-k} \to \eu^{-1}$ । सीमांत मान $\eu^{-1}/k!$ ( $k \in \N$ ) प्राचल $1$ के प्वासों बंटन के भार हैं।

16. $i \neq j$ , $\sigma(i) = i$ , $\sigma(j) = j$ वाली त्रिकियाँ $(\sigma, i, j)$ गिनिए। पहले क्रमित युग्म चुनने पर: $n(n-1)$ तरीके; $i$ और $j$ दोनों को अचल रखने वाले क्रमचय शेष $n - 2$ बिंदुओं के क्रमचय हैं: उनकी संख्या $(n-2)!$ है। कुल: $n(n-1)(n-2)! = n!$ । इसके बदले पहले $\sigma$ पर योग करने से प्रत्येक $\sigma$ के लिए भिन्न अचल बिंदुओं के क्रमित युग्म गिने जाते हैं: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$ । अतः वही सर्वसमिका मिलती है; $n!$ से भाग देने पर $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ का औसत $1$ है, अतः $\abs{\mathrm{Fix}}^2$ का औसत $1 + 1 = 2$ है और प्रसरण $2 - 1^2 = 1$ है।

17. अनुपात $1 - p_n$ : $n = 4$ के लिए $1 - \frac 9{24} = \frac{15}{24} = 0.6250$ ; $n = 5$ के लिए $1 - \frac{44}{120} = \frac{76}{120} = 0.6333$ ; $n = 6$ के लिए $1 - \frac{265}{720} = \frac{455}{720} = 0.6319$ । सभी $1 - \eu^{-1} \approx 0.6321$ के एक प्रतिशत के भीतर, उसके चारों ओर दोलन करते हुए।

18. सीधे:

s_{n+2} - s_n = \frac{(-1)^{n+1}}{(n+1)!} + \frac{(-1)^{n+2}}{(n+2)!} = (-1)^{n+1}\Bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\Bigr),

और कोष्ठक $> 0$ है। $n$ सम होने पर अंतर ऋणात्मक है: $s_{n+2} < s_n$ , अतः $p_0 > p_2 > p_4 > \dots$ ; $n$ विषम होने पर वह धनात्मक है: $p_1 < p_3 < p_5 < \dots$ । प्रश्न 12 (सम मान $\eu^{-1}$ से ऊपर, विषम नीचे) और प्रश्न 14 ( $\eu^{-1}$ से दूरी $0$ की ओर जाती है) के साथ मिलाकर: दोनों सीढ़ियाँ $\eu^{-1}$ को अपने बीच दबा लेती हैं।

19. एक पूर्ण निष्कर्षण समरूप यादृच्छिक क्रमचय है, जो व्यत्यय होने पर वैध है: प्रायिकता $p_n \approx \eu^{-1}$ । उद्धृत तथ्य से सफलता तक निष्कर्षणों की औसत संख्या $1/p_n$ है, और प्रश्न 14 से $1/p_n \approx \eu$ मिलता है, जिसकी त्रुटि छोटे $n$ पर भी नगण्य है। अतः पुनरारंभ वाला गुप्त उपहार औसतन लगभग $\eu \approx 2.72$ पूर्ण निष्कर्षणों की पड़ती है — चाहे कार्यालय में $6$ लोग हों या $600$ ।

20. $j \geq 2$ नियत कीजिए और मान $\sigma(1) = j$ पर प्रश्न 5 का वर्गीकरण चलाइए। यदि $\sigma(j) = 1$ : शेष $n - 2$ बिंदु कोई भी व्यत्यय धारण करते हैं, $D_{n-2}$ तरीके। यदि $\sigma(j) \neq 1$ : प्रश्न 5 की भाँति ही पूर्वप्रतिबिंब $i_0 = \sigma^{-1}(1)$ की दिशा $j$ की ओर मोड़ दीजिए; यह $n - 1$ बिंदुओं $\{2, \dots, n\}$ के व्यत्ययों के साथ एकैकी आच्छादन है: $D_{n-1}$ तरीके। कुल $D_{n-1} + D_{n-2}$ , जो प्रत्येक $j$ के लिए वही है। $j$ के $n - 1$ मानों पर योग करने से: $D_n = (n-1)(D_{n-1} + D_{n-2})$ , जो गुणनखंड $n - 1$ प्रकट कर देता है: $(n-1) \mid D_n$ ।

21. दावा: $D_n$ विषम है यदि और केवल यदि $n$ सम हो। $D_n = nD_{n-1} + (-1)^n$ , अर्थात् $D_n \equiv nD_{n-1} + 1 \pmod 2$ , का प्रयोग करते हुए आगमन। आधार: $D_1 = 0$ सम है, $n = 1$ विषम: दावा सत्य है। यदि $n$ सम है, तो $nD_{n-1}$ सम है और $D_n \equiv 1$ : विषम, जैसा दावा किया गया। यदि $n$ विषम है, तो $n - 1$ सम है, अतः परिकल्पना से $D_{n-1}$ विषम है, और $D_n \equiv D_{n-1} + 1 \equiv 0$ : सम। आगमन बंद हो जाता है।

22. $D_n = nD_{n-1} + (-1)^n$ को $n$ के सापेक्ष घटाने पर पहला पद समाप्त हो जाता है: $D_n \equiv (-1)^n \pmod n$ । $n = 10$ के लिए: $(-1)^{10} = 1$ , और सचमुच $D_{10} = 1\,334\,961$ का अंतिम अंक $1$ है।

23. $n \geq 3$ के लिए $D_{n-1} \geq 1$ , और प्रश्न 6 की पुनरावृत्ति को $D_{n-1}$ से भाग देने पर $D_n/D_{n-1} = n + (-1)^n/D_{n-1}$ मिलता है, जहाँ $\abs{(-1)^n/D_{n-1}} \leq 1$ है और वह तेज़ी से $0$ की ओर जाता है। संगति: यदि $D_n \approx n!/\eu$ , तो $D_n/D_{n-1} \approx n!/(n-1)! = n$ — अनुपात में गुणनखंड $\eu$ कट जाता है, और पुनरावृत्ति उसकी $1/D_{n-1}$ यथार्थता तक पुष्टि कर देती है।

24. (क) गुणन और योग नियम हर गणना के मूल में हैं: प्रश्न 2 और 5 क्रमचयों के समुच्चयों को स्वतंत्र चरणों में विभाजित करते हैं। (ख) दुहरी गणना ने $D_n$ के लिए कोई सूत्र लिए बिना ही अचल बिंदुओं की संख्या का माध्य (प्रश्न 4) और प्रसरण (प्रश्न 16) दे दिया। (ग) द्विपद प्रमेय ने वह एकांतरित भीतरी योग $(1-1)^{n-j}$ आँका जिससे द्विपद प्रतिलोमन काम करता है (प्रश्न 8)। (घ) एकांतरित-श्रेणी परिबंध ने यथार्थ किंतु अपारदर्शी योग $n!\,s_n$ को “ $n!/\eu$ का निकटतम पूर्णांक” जैसे पारदर्शी कथन में बदल दिया (प्रश्न 10–14)।

25. समावेशन–अपवर्जन (उदाहरण 2.26 और अभ्यास 2.11) वैचारिक उपपत्ति है: वह एकांतरित योग को अधिगणना के सुधारों के रूप में समझाती है, और “बुरे” समुच्चयों के किसी भी परिवार से बचने वाले अवयवों की गणना तक अक्षरशः सामान्यीकृत हो जाती है। पुनरावृत्ति वाला रास्ता (प्रश्न 5–7) सबसे तेज़ संगणना करता है — रैखिक समय, यथार्थ पूर्णांक अंकगणित, कोई क्रमगुणित नहीं — और भाग V के अंकगणितीय तथ्यों का स्रोत है। द्विपद प्रतिलोमन (प्रश्न 8–9) सूत्र को एक व्यापक रूपांतर के भीतर रख देता है, जो वहाँ-वहाँ फिर प्रकट होगा जहाँ सर्वसमिकाओं के दो त्रिभुजीय निकाय आमने-सामने आते हैं। और $\eu$ का प्रकट होना स्वयं सूत्र से सबसे अच्छा समझ में आता है: व्यत्ययों का अनुपात $\eu^{-1}$ की श्रेणी का आंशिक योग $s_n$ है, अतः मोंमोर के लिफ़ाफ़े, ऑयलर के संकेतन से तीन दशक पहले ही, संख्या $\eu$ की संगणना कर रहे थे।