रूक बहुपद: Difference between revisions

Revision as of 14:02, 17 March 2023

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

One possible arrangement of rooks on an 8 × 8 chessboard, where no two pieces share a row or column.

मिश्रित गणित में, एक बदमाश बहुपद एक बिसात की तरह दिखने वाले बोर्ड पर गैर-हमलावर बदमाशों को रखने के तरीकों की संख्या का एक जनक बहुपद है; यानी कोई भी दो हाथी एक ही कतार या कॉलम में नहीं हो सकते।

मिश्रित गणित में, एक रूक बहुपद एक बिसात की तरह दिखने वाले बोर्ड पर गैर-हमलावर किश्ती (शतरंज) को रखने के तरीकों की संख्या का एक जनक बहुपद है; यानी कोई भी दो हाथी एक ही कतार या कॉलम में नहीं हो सकते। बोर्ड एम पंक्तियों और एनकॉलम वाले आयताकार बोर्ड के वर्गों का कोई उपसमुच्चय है; हम इसे उन वर्गों के रूप में सोचते हैं जिनमें किसी को एक हाथी रखने की अनुमति है। यदि सभी वर्गों की अनुमति है तो बोर्ड साधारण शतरंज की बिसात है और एम = एन= 8 और किसी भी आकार की शतरंज की बिसात है यदि सभी वर्गों की अनुमति है और एम = एन। एक्स का गुणांक^k रूक बहुपद R में_B(x) उन तरीकों की संख्या है, जिनमें से कोई भी दूसरे पर हमला नहीं करता है, बी के वर्गों में व्यवस्थित किया जा सकता है। हाथी इस तरह से व्यवस्थित होते हैं कि एक ही पंक्ति या स्तंभ में बदमाशों की कोई जोड़ी नहीं होती है। इस अर्थ में, व्यवस्था एक स्थिर, अचल बोर्ड पर बदमाशों की स्थिति है; वर्गों को स्थिर रखते हुए बोर्ड को घुमाने या प्रतिबिंबित करने पर व्यवस्था अलग नहीं होगी। बहुपद भी वही रहता है यदि पंक्तियों को आपस में बदल दिया जाता है या स्तंभों को आपस में बदल दिया जाता है।

रूक बहुपद शब्द जॉन रिओर्डन (गणितज्ञ) द्वारा गढ़ा गया था।^[1]शतरंज से नाम की व्युत्पत्ति के बावजूद, रूक बहुपदों का अध्ययन करने के लिए प्रेरणा प्रतिबंधित पदों के साथ गणना क्रम परिवर्तन (या आंशिक क्रमपरिवर्तन) के साथ उनका संबंध है। एक बोर्ड B जो कि एन× एन शतरंजबोर्ड का एक उपसमुच्चय है, एनवस्तुओं के क्रमपरिवर्तन से मेल खाता है, जिसे हम संख्या 1, 2, ..., एन मान सकते हैं, जैसे कि संख्या a_j क्रमचय में j-वें स्थान पर B की पंक्ति j में अनुमत वर्ग की स्तंभ संख्या होनी चाहिए। प्रसिद्ध उदाहरणों में एनगैर-हमलावर बदमाशों को रखने के तरीकों की संख्या शामिल है:

एक संपूर्ण एन× एनशतरंज बोर्ड, जो कि एक प्रारंभिक संयोजी समस्या है;
वही बोर्ड जिसके तिरछे वर्ग वर्जित हैं; यह गड़बड़ी या हैट-चेक समस्या है (यह रेनकॉन्ट्रेस नंबरों का एक विशेष मामला है। प्रॉब्लम डेस रेनकॉन्ट्रेस);
वही बोर्ड जिसके विकर्ण पर वर्ग नहीं है और विकर्ण के ठीक ऊपर है (और निचले बाएँ वर्ग के बिना), जो समस्या देस मेनेज के समाधान में आवश्यक है।

रूक प्लेसमेंट में रुचि शुद्ध और एप्लाइड कॉम्बिनेटरिक्स, समूह सिद्धांत, संख्या सिद्धांत और सांख्यिकीय भौतिकी में पैदा होती है। रूक बहुपदों का विशेष मूल्य जनरेटिंग फ़ंक्शन दृष्टिकोण की उपयोगिता से आता है, और इस तथ्य से भी कि बोर्ड के रूक बहुपद के एक फ़ंक्शन का शून्य इसके गुणांकों के बारे में मूल्यवान जानकारी प्रदान करता है, अर्थात, गैर-हमलावर प्लेसमेंट की संख्या k बदमाशों का।

परिभाषा

किश्ती बहुपद आर_B(x) एक बोर्ड B का गैर-हमलावर बदमाशों की व्यवस्था की संख्या के लिए जनरेटिंग फ़ंक्शन है:

R_{B}(x)=\sum _{k=0}^{\min {(m,n)}}r_{k}(B)x^{k},

कहाँ $r_{k}(B)$ बोर्ड B पर k गैर-हमलावर बदमाशों को रखने के तरीकों की संख्या है। बोर्ड पर गैर-हमलावर बदमाशों की अधिकतम संख्या हो सकती है; वास्तव में, बोर्ड में पंक्तियों की संख्या या स्तंभों की संख्या से अधिक हाथी नहीं हो सकते (इसलिए सीमा $\min(m,n)$ ).^[2]

पूरा बोर्ड

आयताकार एम × एनबोर्डों के लिए B_{एम,एन}, हम R लिखते हैं_{एम,एन}:= आर_{B_{एम,एन}</ उप>, और यदि एम = एन, आर_एन:= आर_{एम,एन}.}

वर्ग एन× एनबोर्डों पर पहले कुछ रूक बहुपद हैं:

{\begin{aligned}R_{1}(x)&=x+1\\R_{2}(x)&=2x^{2}+4x+1\\R_{3}(x)&=6x^{3}+18x^{2}+9x+1\\R_{4}(x)&=24x^{4}+96x^{3}+72x^{2}+16x+1.\end{aligned}}

शब्दों में, इसका मतलब यह है कि 1 × 1 बोर्ड पर, 1 हाथी को 1 तरीके से व्यवस्थित किया जा सकता है, और शून्य हाथी को भी 1 तरीके से व्यवस्थित किया जा सकता है (खाली बोर्ड); एक पूर्ण 2 × 2 बोर्ड पर, 2 हाथी 2 तरीकों से (विकर्णों पर) व्यवस्थित किए जा सकते हैं, 1 हाथी 4 तरीकों से व्यवस्थित किए जा सकते हैं, और शून्य हाथी 1 तरीके से व्यवस्थित किए जा सकते हैं; और इसी तरह बड़े बोर्डों के लिए।

एक आयताकार शतरंज की बिसात का किश्ती बहुपद सामान्यीकृत लैगुएरे बहुपद एल से निकटता से संबंधित है_एन^α(x) सर्वसमिका द्वारा

R_{m,n}(x)=n!x^{n}L_{n}^{(m-n)}(-x^{-1}).

मिलान बहुपद

एक रूक बहुपद एक प्रकार के मेल खाने वाले बहुपद का एक विशेष मामला है, जो एक ग्राफ में के-एज मिलान (ग्राफ सिद्धांत) की संख्या का जनरेटिंग फ़ंक्शन है।

रूक बहुपद आर_{एम,एन}(x) पूर्ण द्विदलीय ग्राफ़ K के अनुरूप है_{एम,एन}. सामान्य बोर्ड का रूक बहुपद B ⊆ B_एम,एनबाएं कोने v के साथ द्विदलीय ग्राफ से मेल खाता है₁, में₂, ..., में_एम और दाएँ शीर्ष w₁, में₂, ..., मेंएनऔर एक किनारे वी_iw_j जब भी वर्ग (i, j) की अनुमति दी जाती है, यानी, बी से संबंधित होता है। इस प्रकार, रूक बहुपदों का सिद्धांत, एक अर्थ में, मिलान करने वाले बहुपदों में निहित है।

हम गुणांक r के बारे में एक महत्वपूर्ण तथ्य निकालते हैं_k, जिसे हम B में k rooks के गैर-हमलावर प्लेसमेंट की संख्या को देखते हुए याद करते हैं: ये संख्याएँ असमान हैं, अर्थात, वे अधिकतम तक बढ़ती हैं और फिर घटती हैं। यह हेइलमैन और लिब के प्रमेय से (एक मानक तर्क द्वारा) अनुसरण करता है^[3] एक मेल खाने वाले बहुपद के शून्यों के बारे में (उससे भिन्न जो एक रूक बहुपद से संबंधित है, लेकिन चर के परिवर्तन के तहत इसके बराबर है), जिसका अर्थ है कि एक रूक बहुपद के सभी शून्य ऋणात्मक वास्तविक संख्याएं हैं।

मैट्रिक्स स्थायी से कनेक्शन

अधूरे वर्ग एन× एनबोर्डों के लिए, (अर्थात बोर्ड के वर्गों के कुछ मनमाना उपसमुच्चय पर बदमाशों को खेलने की अनुमति नहीं है) बोर्ड पर एनबदमाशों को रखने के तरीकों की संख्या की गणना 0 के स्थायी (गणित) की गणना करने के बराबर है -1 मैट्रिक्स।

पूरा आयताकार बोर्ड

रूक की समस्या

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Fig. 1. The maximal number of non-attacking rooks on an 8 × 8 chessboard is 8. Rook + dots mark the number of squares on a rank, available to each rook, after placing the rooks on the lower ranks.

किश्ती बहुपद का अग्रदूत महामहिम ड्यूडेनी द्वारा क्लासिक आठ हाथी समस्या है^[4] जिसमें वह दिखाता है कि शतरंज की बिसात पर गैर-हमलावर बदमाशों की अधिकतम संख्या आठ है, उन्हें मुख्य विकर्णों में से एक पर रखकर (चित्र 1)। पूछा गया प्रश्न है: 8 × 8 शतरंज की बिसात पर आठ बदमाशों को कितने तरीकों से रखा जा सकता है ताकि उनमें से कोई भी दूसरे पर हमला न करे? उत्तर है: स्पष्ट रूप से प्रत्येक पंक्ति और प्रत्येक स्तंभ में एक किश्ती होना चाहिए। नीचे की पंक्ति से शुरू करते हुए, यह स्पष्ट है कि पहला हाथी आठ अलग-अलग वर्गों में से किसी एक पर रखा जा सकता है (चित्र 1)। इसे जहां भी रखा गया है, दूसरी पंक्ति में दूसरे हाथी के लिए सात चौकों का विकल्प है। फिर छह वर्ग हैं जिनमें से तीसरी पंक्ति का चयन करना है, पांच चौथी में, और इसी तरह। इसलिए अलग-अलग तरीकों की संख्या 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320 होनी चाहिए (अर्थात, 8!, जहाँ ! भाज्य है)।^[5] एक ही परिणाम थोड़े अलग तरीके से प्राप्त किया जा सकता है। आइए हम प्रत्येक हाथी को उसके रैंक की संख्या के अनुरूप एक स्थितीय संख्या दें, और उसे एक नाम दें जो उसकी फ़ाइल के नाम से मेल खाता हो। इस प्रकार, rook a1 की स्थिति 1 है और एनaएमe a, rook b2 की स्थिति 2 और नाम b है, आदि। फिर आइए हम roooks को उनकी स्थिति के अनुसार एक क्रमित सूची (अनुक्रम) में क्रमबद्ध करें। चित्र 1 पर आरेख फिर अनुक्रम (ए, बी, सी, डी, ई, एफ, जी, एच) में बदल जाएगा। किसी अन्य फ़ाइल पर किसी भी हाथी को रखने से पहले हाथी द्वारा खाली की गई फ़ाइल में दूसरी फ़ाइल पर कब्जा करने वाले हाथी को स्थानांतरित करना शामिल होगा। उदाहरण के लिए, यदि रूक ए1 को बी फाइल में ले जाया जाता है, तो रूक बी2 को एक फाइल में स्थानांतरित किया जाना चाहिए, और अब वे रूक बी1 और रूक ए2 बन जाएंगे। नया अनुक्रम बन जाएगा (बी, ए, सी, डी, ई, एफ, जी, एच)। कॉम्बिनेटरिक्स में, इस ऑपरेशन को क्रमचय कहा जाता है, और क्रमपरिवर्तन के परिणामस्वरूप प्राप्त अनुक्रम दिए गए अनुक्रम के क्रमपरिवर्तन हैं। 8 तत्वों के अनुक्रम से 8 तत्वों वाले क्रमचय की कुल संख्या 8 है! (8 का भाज्य)।

लगाए गए सीमा के प्रभाव का आकलन करने के लिए बदमाशों को एक दूसरे पर हमला नहीं करना चाहिए, इस तरह की सीमा के बिना समस्या पर विचार करें। 8 × 8 शतरंज की बिसात पर आठ हाथी कितने प्रकार से रखे जा सकते हैं? यह 64 चौकों पर 8 बदमाशों के संयोजनों की कुल संख्या होगी:

{64 \choose 8}={\frac {64!}{8!(64-8)!}}=4,426,165,368.

इस प्रकार, सीमावर्ती बदमाशों को एक-दूसरे पर हमला नहीं करना चाहिए, संयोजनों से क्रमपरिवर्तन तक स्वीकार्य पदों की कुल संख्या को कम कर देता है जो लगभग 109,776 का कारक है।

मानव गतिविधि के विभिन्न क्षेत्रों से कई समस्याओं को एक रूक फॉर्मूलेशन देकर रूक समस्या में कम किया जा सकता है। एक उदाहरण के रूप में: एक कंपनी को अलग-अलग नौकरियों पर एनश्रमिकों को नियुक्त करना चाहिए और प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाना चाहिए। यह नियुक्ति कितने तरीकों से की जा सकती है?

आइए हम कार्यकर्ताओं को एन× एनशतरंज की बिसात पर, और नौकरियों को - फाइलों पर रखें। यदि कार्यकर्ता i को जॉब j पर नियुक्त किया जाता है, तो उस वर्ग पर एक हाथी रखा जाता है जहाँ रैंक i फ़ाइल j को पार करता है। चूँकि प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाता है और प्रत्येक कार्यकर्ता को केवल एक ही कार्य के लिए नियुक्त किया जाता है, बोर्ड पर एनबदमाशों की व्यवस्था के परिणामस्वरूप सभी फाइलों और रैंकों में केवल एक बदमाश होगा, यानी बदमाश हमला नहीं करते हैं एक-दूसरे से।

रूक बहुपद रूक समस्या के सामान्यीकरण के रूप में

क्लासिकल रूक्स समस्या तुरंत r का मान देती है₈, किश्ती बहुपद के उच्चतम क्रम पद के सामने गुणांक। दरअसल, इसका परिणाम यह है कि 8 गैर-हमलावर बदमाशों को आर में 8 × 8 शतरंज की बिसात पर व्यवस्थित किया जा सकता है₈ = 8! = 40320 तरीके।

आइए हम एक एम × एन बोर्ड, यानी एम रैंक (पंक्तियों) और एन फाइलों (कॉलम) वाले बोर्ड पर विचार करके इस समस्या को सामान्य करें। समस्या यह हो जाती है: एक एम × एनबोर्ड पर कितने तरीकों से किश्ती को इस तरह से व्यवस्थित किया जा सकता है कि वे एक दूसरे पर हमला न करें?

यह स्पष्ट है कि समस्या को हल करने योग्य होने के लिए, k को संख्याओं एम और एनमें से छोटी संख्या से कम या उसके बराबर होना चाहिए; अन्यथा कोई बदमाशों की एक जोड़ी को रैंक या फाइल पर रखने से बच नहीं सकता है। यह शर्त पूरी हो जाए। फिर किश्ती की व्यवस्था दो चरणों में की जा सकती है। सबसे पहले, k रैंकों का सेट चुनें जिस पर बदमाशों को रखना है। चूंकि रैंकों की संख्या एम है, जिनमें से k को चुना जाना चाहिए, यह चुनाव में किया जा सकता है ${\binom {m}{k}}$ तौर तरीकों। इसी तरह, k फ़ाइलों का सेट जिस पर बदमाशों को रखना है, उसमें चुना जा सकता है ${\binom {n}{k}}$ तौर तरीकों। क्योंकि फ़ाइलों की पसंद रैंकों की पसंद पर निर्भर नहीं करती है, उत्पादों के नियम के अनुसार होते हैं ${\binom {m}{k}}{\binom {n}{k}}$ वर्ग चुनने के तरीके जिस पर किश्ती रखा जाए।

हालाँकि, कार्य अभी तक समाप्त नहीं हुआ है क्योंकि k रैंक और k फ़ाइलें k में प्रतिच्छेद करती हैं² वर्ग। अप्रयुक्त रैंकों और फ़ाइलों को हटाने और शेष रैंकों और फ़ाइलों को एक साथ जोड़कर, एक k रैंक और k फ़ाइलों का एक नया बोर्ड प्राप्त करता है। यह पहले से ही दिखाया गया था कि इस तरह के बोर्ड पर k बदमाशों को k में व्यवस्थित किया जा सकता है! तरीके (ताकि वे एक दूसरे पर हमला न करें)। इसलिए, संभावित गैर-आक्रमणकारी बदमाश व्यवस्थाओं की कुल संख्या है:^[6]

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

उदाहरण के लिए, एक पारंपरिक शतरंज की बिसात (8 × 8) पर 3 हाथी रखे जा सकते हैं $\textstyle {\frac {8!8!}{3!5!5!}}=18,816$ तौर तरीकों। के = एम = एन के लिए, उपरोक्त सूत्र आर देता है_k= एन! जो शास्त्रीय रूक्स समस्या के लिए प्राप्त परिणाम के अनुरूप है।

स्पष्ट गुणांकों वाला किश्ती बहुपद अब है:

R_{m,n}(x)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}k!x^{k}=\sum _{k=0}^{\min(m,n)}{\frac {n!m!}{k!(n-k)!(m-k)!}}x^{k}.

यदि बदमाशों को एक दूसरे पर हमला नहीं करना चाहिए की सीमा को हटा दिया जाता है, तो किसी को एम × एनवर्गों में से किसी भी k वर्ग को चुनना होगा। इसमें किया जा सकता है:

{\binom {mn}{k}}={\frac {(mn)!}{k!(mn-k)!}}

तौर तरीकों।

यदि k k roooks एक दूसरे से किसी तरह से भिन्न हैं, उदाहरण के लिए, उन्हें लेबल या क्रमांकित किया गया है, तो अब तक प्राप्त सभी परिणामों को k!, k rooks के क्रमपरिवर्तन की संख्या से गुणा किया जाना चाहिए।

सममित व्यवस्था

बदमाशों की समस्या की एक और जटिलता के रूप में, हमें आवश्यकता है कि बदमाश न केवल गैर-हमलावर हों बल्कि बोर्ड पर सममित रूप से व्यवस्थित हों। समरूपता के प्रकार के आधार पर, यह बोर्ड को घुमाने या परावर्तित करने के बराबर है। समरूपता की स्थिति के आधार पर सममित व्यवस्था कई समस्याओं का कारण बनती है।^[7]^[8]^[9]^[10]

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Fig. 2. A symmetric arrangement of non-attacking rooks about the centre of an 8 × 8 chessboard. Dots mark the 4 central squares that surround the centre of symmetry.

उन व्यवस्थाओं में सबसे सरल तब होती है जब हाथी बोर्ड के केंद्र के बारे में सममित होते हैं। आइए जी के साथ नामित करें_एनव्यवस्थाओं की संख्या जिसमें एनबदमाशों को एनरैंकों और एनफ़ाइलों वाले बोर्ड पर रखा जाता है। अब हम बोर्ड को 2एनरैंक और 2एनफाइल रखने के लिए बनाते हैं। पहली फ़ाइल पर किश्ती को उस फ़ाइल के किसी भी 2एनवर्ग पर रखा जा सकता है। समरूपता की स्थिति के अनुसार, इस हाथी का स्थान उस हाथी के स्थान को परिभाषित करता है जो अंतिम फ़ाइल पर खड़ा होता है - इसे बोर्ड केंद्र के बारे में पहले हाथी के लिए सममित रूप से व्यवस्थित किया जाना चाहिए। आइए हम पहली और आखिरी फाइलों और रैंकों को हटा दें जो कि बदमाशों के कब्जे में हैं (चूंकि रैंकों की संख्या सम है, हटाए गए बदमाश एक ही रैंक पर खड़े नहीं हो सकते हैं)। यह 2एन−2 फ़ाइलों और 2एन−2 रैंकों का एक बोर्ड देगा। यह स्पष्ट है कि नए बोर्ड पर बदमाशों की प्रत्येक सममित व्यवस्था मूल बोर्ड पर बदमाशों की सममित व्यवस्था से मेल खाती है। इसलिए, जी₂एन= 2एनजी_{2एन − 2} (इस अभिव्यक्ति में कारक 2एनपहली फाइल पर 2एनवर्गों में से किसी पर कब्जा करने के लिए पहली रूक की संभावना से आता है)। उपरोक्त सूत्र को दोहराने से एक 2 × 2 बोर्ड के मामले तक पहुंचता है, जिस पर 2 सममित व्यवस्थाएं (विकर्णों पर) होती हैं। इस पुनरावृत्ति के परिणामस्वरूप, अंतिम अभिव्यक्ति G है₂एन= 2^एनएन! सामान्य शतरंज की बिसात (8 × 8) के लिए, G₈ = 2⁴ × 4! = 16 × 24 = 384 8 हाथी की केंद्रीय सममित व्यवस्था। ऐसी ही एक व्यवस्था चित्र 2 में दिखाई गई है।

विषम-आकार के बोर्डों के लिए (जिसमें 2एन+ 1 रैंक और 2एन+ 1 फ़ाइलें होती हैं) हमेशा एक ऐसा वर्ग होता है जिसका सममित दोहरा नहीं होता है - यह बोर्ड का केंद्रीय वर्ग होता है। इस चौक पर हमेशा एक हाथी रखा होना चाहिए। केंद्रीय फ़ाइल और रैंक को हटाने से, 2एन× 2एनबोर्ड पर 2एनबदमाशों की एक सममित व्यवस्था प्राप्त होती है। इसलिए ऐसे बोर्ड के लिए एक बार फिर जी_{2एन + 1} = जी₂एन= 2^एनएन!.

थोड़ी अधिक जटिल समस्या गैर-आक्रमणकारी व्यवस्थाओं की संख्या का पता लगाना है जो बोर्ड के 90 डिग्री रोटेशन पर नहीं बदलती हैं। बता दें कि बोर्ड में 4एनफाइलें और 4एनरैंक हैं, और बदमाशों की संख्या भी 4एनहै। इस स्थिति में, पहली फ़ाइल पर मौजूद हाथी इस फ़ाइल पर किसी भी वर्ग पर कब्जा कर सकता है, कोने के वर्गों को छोड़कर (एक हाथी कोने के वर्ग पर नहीं हो सकता है क्योंकि 90 डिग्री रोटेशन के बाद 2 हाथी एक दूसरे पर हमला करेंगे)। वहाँ अन्य 3 हाथी हैं जो उस हाथी से मेल खाते हैं और वे क्रमशः अंतिम रैंक, अंतिम फ़ाइल और पहली रैंक पर खड़े होते हैं (वे पहले हाथी से 90°, 180°, और 270° रोटेशन द्वारा प्राप्त किए जाते हैं)। उन बदमाशों की फाइलों और रैंकों को हटाकर, आवश्यक समरूपता के साथ एक (4एन− 4) × (4एन− 4) बोर्ड के लिए किश्ती की व्यवस्था प्राप्त करता है। इस प्रकार, निम्नलिखित पुनरावृत्ति संबंध प्राप्त होता है: R₄एन= (4एन - 2)आर_{4एन − 4}, जहां आर_एनएन× एनबोर्ड के लिए व्यवस्थाओं की संख्या है। पुनरावृत्ति, यह इस प्रकार है कि आर₄एन= 2एन(2एन− 1)(2एन− 3)...1. एक (4एन+ 1) × (4एन+ 1) बोर्ड के लिए व्यवस्थाओं की संख्या वही है जो 4एन× 4एनबोर्ड की है; ऐसा इसलिए है क्योंकि (4एन+ 1) × (4एन+ 1) बोर्ड पर, एक हाथी को आवश्यक रूप से केंद्र में खड़ा होना चाहिए और इस प्रकार केंद्रीय रैंक और फ़ाइल को हटाया जा सकता है। इसलिए आर_{4एन + 1} = आर_4एन. पारंपरिक शतरंज की बिसात (एन= 2) के लिए, R₈ = 4 × 3 × 1 = घूर्णी समरूपता के साथ 12 संभावित व्यवस्थाएँ।

(4एन+ 2) × (4एन+ 2) और (4एन+ 3) × (4एन+ 3) बोर्डों के लिए, समाधान की संख्या शून्य है। प्रत्येक हाथी के लिए दो स्थितियाँ संभव हैं: या तो वह बीच में खड़ा हो या वह बीच में न खड़ा हो। दूसरे मामले में, यह हाथी उस चौकड़ी में शामिल है जो बोर्ड को 90° पर मोड़ने पर वर्गों का आदान-प्रदान करती है। इसलिए, बदमाशों की कुल संख्या या तो 4एनहोनी चाहिए (जब बोर्ड पर कोई केंद्रीय वर्ग न हो) या 4एन+ 1। यह साबित करता है कि R_{4एन + 2} = आर_{4एन + 3} = 0।

एक एन× एनबोर्ड पर विकर्णों में से किसी एक विकर्ण (निर्धारणता के लिए, शतरंज की बिसात पर a1–h8 के संगत विकर्ण) के सममित एनगैर-हमलावर बदमाशों की व्यवस्था की संख्या पुनरावृत्ति Q द्वारा परिभाषित टेलीफोन नंबर (गणित) द्वारा दी गई हैएन= क्यू_{एन − 1} + (एन − 1)क्यू_{एन − 2}. यह पुनरावृत्ति निम्न प्रकार से प्राप्त होती है। ध्यान दें कि पहली फ़ाइल पर किश्ती या तो निचले कोने के वर्ग पर खड़ा होता है या यह दूसरे वर्ग पर खड़ा होता है। पहले मामले में, पहली फ़ाइल और पहली रैंक को हटाने से एक (एन− 1) × (एन− 1) बोर्ड पर सममित व्यवस्था एन− 1 रूक हो जाती है। ऐसी व्यवस्थाओं की संख्या Q है_{एन − 1}. दूसरे मामले में, मूल किश्ती के लिए एक और किश्ती है, जो चुने हुए विकर्ण के बारे में पहले वाले के लिए सममित है। उन बदमाशों की फाइलों और रैंकों को हटाने से एन− 2 हाथी एक (एन− 2) × (एन− 2) बोर्ड पर एक सममित व्यवस्था की ओर जाता है। चूँकि ऐसी व्यवस्थाओं की संख्या Q है_{एन − 2} और हाथी को पहली फ़ाइल के एन− 1 वर्ग पर रखा जा सकता है, वहाँ (एन− 1)Q हैं_{एन − 2} ऐसा करने के तरीके, जो उपरोक्त पुनरावृत्ति को तुरंत देते हैं। विकर्ण-सममित व्यवस्था की संख्या तब अभिव्यक्ति द्वारा दी जाती है:

Q_{n}=1+{\binom {n}{2}}+{\frac {1}{1\times 2}}{\binom {n}{2}}{\binom {n-2}{2}}+{\frac {1}{1\times 2\times 3}}{\binom {n}{2}}{\binom {n-2}{2}}{\binom {n-4}{2}}+\cdots .

यह अभिव्यक्ति वर्गों में सभी किश्ती व्यवस्थाओं को विभाजित करके प्राप्त की जाती है; कक्षा में वे व्यवस्थाएँ हैं जिनमें बदमाशों के जोड़े विकर्ण पर नहीं खड़े होते हैं। ठीक उसी तरह, यह दिखाया जा सकता है कि एक एन× एनबोर्ड पर एन-रूक व्यवस्था की संख्या, जैसे कि वे एक-दूसरे पर हमला नहीं करते हैं और दोनों विकर्णों के सममित होते हैं, पुनरावृत्ति समीकरण B द्वारा दिया जाता है₂एन= पिता_{2एन − 2} + (2एन − 2)बी_{2एन − 4} और बी_{2एन + 1} = बी_2एन.

समरूपता वर्गों द्वारा गिने जाने वाली व्यवस्था

एक अलग प्रकार का सामान्यीकरण वह है जिसमें बोर्ड की समरूपता द्वारा एक दूसरे से प्राप्त होने वाली रूक व्यवस्थाओं को एक के रूप में गिना जाता है। उदाहरण के लिए, यदि बोर्ड को 90 डिग्री घुमाने की एक समरूपता के रूप में अनुमति दी जाती है, तो 90, 180, या 270 डिग्री के रोटेशन द्वारा प्राप्त किसी भी व्यवस्था को मूल पैटर्न के समान माना जाता है, भले ही इन व्यवस्थाओं को अलग से गिना जाता है मूल समस्या जहां बोर्ड तय है। ऐसी समस्याओं के लिए, डुडेनी^[11] अवलोकन करता है: कितने तरीके हैं यदि मात्र उलटाव और प्रतिबिंबों को भिन्न के रूप में नहीं गिना जाता है जो अभी तक निर्धारित नहीं किया गया है; यह एक कठिन समस्या है। बर्नसाइड के लेम्मा के माध्यम से सममित व्यवस्था की गणना करने में समस्या कम हो जाती है।

संदर्भ

↑ John Riordan, Introduction to Combinatorial Analysis, Princeton University Press, 1980 (originally published by John Wiley and Sons, New York; Chapman and Hall, London, 1958) ISBN 978-0-691-02365-6 (reprinted again in 2002, by Dover Publications). See chapters 7 & 8.
↑ Weisstein, Eric W. "Rook Polynomial." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RookPolynomial.html
↑ Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems. Communications in Mathematical Physics, Vol. 25 (1972), pp. 190–232.
↑ Dudeney, Henry E. Amusements In Mathematics. 1917. Nelson. (republished by Plain Label Books: ISBN 1-60303-152-9, also as a collection of newspaper clippings, Dover Publications, 1958; Kessinger Publishing, 2006). The book can be freely downloaded from Project Gutenberg site [1]
↑ Dudeney, Problem 295
↑ Vilenkin, Naum Ya. Combinatorics (Kombinatorika). 1969. Nauka Publishers, Moscow (In Russian).
↑ Vilenkin, Naum Ya. Popular Combinatorics (Populyarnaya kombinatorika). 1975. Nauka Publishers, Moscow (In Russian).
↑ Gik, Evgeny Ya. Mathematics on the Chessboard (Matematika na shakhmatnoy doske). 1976. Nauka Publishers, Moscow (In Russian).
↑ Gik, Evgeny Ya. Chess and Mathematics (Shakhmaty i matematika). 1983. Nauka Publishers, Moscow (In Russian). ISBN 3-87144-987-3 (GVK-Gemeinsamer Verbundkatalog)
↑ Kokhas', Konstantin P. Rook Numbers and Polynomials (Ladeynye chisla i mnogochleny). MCNMO, Moscow, 2003 (in Russian). ISBN 5-94057-114-X www.mccme.ru/free-books/mmmf-lectures/book.26.pdf (GVK-Gemeinsamer Verbundkatalog)
↑ Dudeney, Answer to Problem 295

[1] John Riordan, Introduction to Combinatorial Analysis, Princeton University Press, 1980 (originally published by John Wiley and Sons, New York; Chapman and Hall, London, 1958) ISBN 978-0-691-02365-6 (reprinted again in 2002, by Dover Publications). See chapters 7 & 8.

[2] Weisstein, Eric W. "Rook Polynomial." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RookPolynomial.html

[3] Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems. Communications in Mathematical Physics, Vol. 25 (1972), pp. 190–232.

[4] Dudeney, Henry E. Amusements In Mathematics. 1917. Nelson. (republished by Plain Label Books: ISBN 1-60303-152-9, also as a collection of newspaper clippings, Dover Publications, 1958; Kessinger Publishing, 2006). The book can be freely downloaded from Project Gutenberg site [1]

[5] Dudeney, Problem 295

[6] Vilenkin, Naum Ya. Combinatorics (Kombinatorika). 1969. Nauka Publishers, Moscow (In Russian).

[7] Vilenkin, Naum Ya. Popular Combinatorics (Populyarnaya kombinatorika). 1975. Nauka Publishers, Moscow (In Russian).

[8] Gik, Evgeny Ya. Mathematics on the Chessboard (Matematika na shakhmatnoy doske). 1976. Nauka Publishers, Moscow (In Russian).

[9] Gik, Evgeny Ya. Chess and Mathematics (Shakhmaty i matematika). 1983. Nauka Publishers, Moscow (In Russian). ISBN 3-87144-987-3 (GVK-Gemeinsamer Verbundkatalog)

[10] Kokhas', Konstantin P. Rook Numbers and Polynomials (Ladeynye chisla i mnogochleny). MCNMO, Moscow, 2003 (in Russian). ISBN 5-94057-114-X www.mccme.ru/free-books/mmmf-lectures/book.26.pdf (GVK-Gemeinsamer Verbundkatalog)

[11] Dudeney, Answer to Problem 295

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 13: / Line 13: @@
 }}
-[[ साहचर्य ]] गणित में, एक रूक बहुपद एक [[[[बिसात]]]] की तरह दिखने वाले बोर्ड पर गैर-हमलावर किश्ती (शतरंज) को रखने के तरीकों की संख्या का एक जनक बहुपद है; यानी कोई भी दो हाथी एक ही कतार या कॉलम में नहीं हो सकते। बोर्ड ''m'' पंक्तियों और ''n'' कॉलम वाले आयताकार बोर्ड के वर्गों का कोई उपसमुच्चय है; हम इसे उन वर्गों के रूप में सोचते हैं जिनमें किसी को एक हाथी रखने की अनुमति है। यदि सभी वर्गों की अनुमति है तो बोर्ड साधारण शतरंज की बिसात है और ''m'' = ''n'' = 8 और किसी भी आकार की शतरंज की बिसात है यदि सभी वर्गों की अनुमति है और ''m'' = ''n''। '' एक्स '' का गुणांक<sup>k</sup> रूक बहुपद R में<sub>''B''</sub>(x) उन तरीकों की संख्या है, जिनमें से कोई भी दूसरे पर हमला नहीं करता है, बी के वर्गों में व्यवस्थित किया जा सकता है। हाथी इस तरह से व्यवस्थित होते हैं कि एक ही पंक्ति या स्तंभ में बदमाशों की कोई जोड़ी नहीं होती है। इस अर्थ में, व्यवस्था एक स्थिर, अचल बोर्ड पर बदमाशों की स्थिति है; वर्गों को स्थिर रखते हुए बोर्ड को घुमाने या प्रतिबिंबित करने पर व्यवस्था अलग नहीं होगी। बहुपद भी वही रहता है यदि पंक्तियों को आपस में बदल दिया जाता है या स्तंभों को आपस में बदल दिया जाता है।
+मिश्रित गणित में, एक बदमाश बहुपद एक बिसात की तरह दिखने वाले बोर्ड पर गैर-हमलावर बदमाशों को रखने के तरीकों की संख्या का एक जनक बहुपद है; यानी कोई भी दो हाथी एक ही कतार या कॉलम में नहीं हो सकते।
-रूक बहुपद शब्द जॉन रिओर्डन (गणितज्ञ) द्वारा गढ़ा गया था।<ref>[[John Riordan (mathematician)|John Riordan]],  [https://books.google.com/books?id=zWgIPlds29UC ''Introduction to Combinatorial Analysis''], Princeton University Press, 1980 (originally published by John Wiley and Sons, New York; Chapman and Hall, London, 1958) {{isbn|978-0-691-02365-6}} (reprinted again in 2002, by Dover Publications). See chapters 7 & 8.</ref>
+[[ साहचर्य | मिश्रित]] गणित में, एक रूक बहुपद एक [[बिसात]] की तरह दिखने वाले बोर्ड पर गैर-हमलावर किश्ती (शतरंज) को रखने के तरीकों की संख्या का एक जनक बहुपद है; यानी कोई भी दो हाथी एक ही कतार या कॉलम में नहीं हो सकते। बोर्ड ''एम'' पंक्तियों और एनकॉलम वाले आयताकार बोर्ड के वर्गों का कोई उपसमुच्चय है; हम इसे उन वर्गों के रूप में सोचते हैं जिनमें किसी को एक हाथी रखने की अनुमति है। यदि सभी वर्गों की अनुमति है तो बोर्ड साधारण शतरंज की बिसात है और ''एम'' = एन= 8 और किसी भी आकार की शतरंज की बिसात है यदि सभी वर्गों की अनुमति है और ''एम'' = ''एन''। '' एक्स '' का गुणांक<sup>k</sup> रूक बहुपद R में<sub>''B''</sub>(x) उन तरीकों की संख्या है, जिनमें से कोई भी दूसरे पर हमला नहीं करता है, बी के वर्गों में व्यवस्थित किया जा सकता है। हाथी इस तरह से व्यवस्थित होते हैं कि एक ही पंक्ति या स्तंभ में बदमाशों की कोई जोड़ी नहीं होती है। इस अर्थ में, व्यवस्था एक स्थिर, अचल बोर्ड पर बदमाशों की स्थिति है; वर्गों को स्थिर रखते हुए बोर्ड को घुमाने या प्रतिबिंबित करने पर व्यवस्था अलग नहीं होगी। बहुपद भी वही रहता है यदि पंक्तियों को आपस में बदल दिया जाता है या स्तंभों को आपस में बदल दिया जाता है।
-[[शतरंज]] से नाम की व्युत्पत्ति के बावजूद, रूक बहुपदों का अध्ययन करने के लिए प्रेरणा प्रतिबंधित पदों के साथ गणना क्रम[[परिवर्तन]] (या [[आंशिक क्रमपरिवर्तन]]) के साथ उनका संबंध है। एक बोर्ड B जो कि n × n शतरंजबोर्ड का एक उपसमुच्चय है, n वस्तुओं के क्रमपरिवर्तन से मेल खाता है, जिसे हम संख्या 1, 2, ..., n मान सकते हैं, जैसे कि संख्या a<sub>''j''</sub> क्रमचय में j-वें स्थान पर B की पंक्ति j में अनुमत वर्ग की स्तंभ संख्या होनी चाहिए। प्रसिद्ध उदाहरणों में n गैर-हमलावर बदमाशों को रखने के तरीकों की संख्या शामिल है:
-*एक संपूर्ण n × n शतरंज बोर्ड, जो कि एक प्रारंभिक संयोजी समस्या है;
+रूक बहुपद शब्द जॉन रिओर्डन (गणितज्ञ) द्वारा गढ़ा गया था।<ref>[[John Riordan (mathematician)|John Riordan]],  [https://books.google.com/books?id=zWgIPlds29UC ''Introduction to Combinatorial Analysis''], Princeton University Press, 1980 (originally published by John Wiley and Sons, New York; Chapman and Hall, London, 1958) {{isbn|978-0-691-02365-6}} (reprinted again in 2002, by Dover Publications). See chapters 7 & 8.</ref>[[शतरंज]] से नाम की व्युत्पत्ति के बावजूद, रूक बहुपदों का अध्ययन करने के लिए प्रेरणा प्रतिबंधित पदों के साथ गणना क्रम [[परिवर्तन]] (या [[आंशिक क्रमपरिवर्तन]]) के साथ उनका संबंध है। एक बोर्ड B जो कि एन× एन शतरंजबोर्ड का एक उपसमुच्चय है, एनवस्तुओं के क्रमपरिवर्तन से मेल खाता है, जिसे हम संख्या 1, 2, ..., एन मान सकते हैं, जैसे कि संख्या a<sub>''j''</sub> क्रमचय में j-वें स्थान पर B की पंक्ति j में अनुमत वर्ग की स्तंभ संख्या होनी चाहिए। प्रसिद्ध उदाहरणों में एनगैर-हमलावर बदमाशों को रखने के तरीकों की संख्या शामिल है:
-*वही बोर्ड जिसके तिरछे वर्ग वर्जित हैं; यह [[ गड़बड़ी ]] या हैट-चेक समस्या है (यह रेनकॉन्ट्रेस नंबरों का एक विशेष मामला है। प्रॉब्लम डेस रेनकॉन्ट्रेस);
+*एक संपूर्ण एन× एनशतरंज बोर्ड, जो कि एक प्रारंभिक संयोजी समस्या है;
+*वही बोर्ड जिसके तिरछे वर्ग वर्जित हैं; यह [[ गड़बड़ी |गड़बड़ी]] या हैट-चेक समस्या है (यह रेनकॉन्ट्रेस नंबरों का एक विशेष मामला है। प्रॉब्लम डेस रेनकॉन्ट्रेस);
 *वही बोर्ड जिसके विकर्ण पर वर्ग नहीं है और विकर्ण के ठीक ऊपर है (और निचले बाएँ वर्ग के बिना), जो समस्या देस मेनेज के समाधान में आवश्यक है।
-रूक प्लेसमेंट में रुचि शुद्ध और एप्लाइड कॉम्बिनेटरिक्स, [[समूह सिद्धांत]], [[संख्या सिद्धांत]] और [[ सांख्यिकीय भौतिकी ]] में पैदा होती है। रूक बहुपदों का विशेष मूल्य जनरेटिंग फ़ंक्शन दृष्टिकोण की उपयोगिता से आता है, और इस तथ्य से भी कि बोर्ड के रूक बहुपद के एक फ़ंक्शन का शून्य इसके गुणांकों के बारे में मूल्यवान जानकारी प्रदान करता है, अर्थात, गैर-हमलावर प्लेसमेंट की संख्या k बदमाशों का।
+रूक प्लेसमेंट में रुचि शुद्ध और एप्लाइड कॉम्बिनेटरिक्स, [[समूह सिद्धांत]], [[संख्या सिद्धांत]] और[[ सांख्यिकीय भौतिकी | सांख्यिकीय भौतिकी]] में पैदा होती है। रूक बहुपदों का विशेष मूल्य जनरेटिंग फ़ंक्शन दृष्टिकोण की उपयोगिता से आता है, और इस तथ्य से भी कि बोर्ड के रूक बहुपद के एक फ़ंक्शन का शून्य इसके गुणांकों के बारे में मूल्यवान जानकारी प्रदान करता है, अर्थात, गैर-हमलावर प्लेसमेंट की संख्या k बदमाशों का।
 == परिभाषा ==
@@ Line 32: / Line 33: @@
 === पूरा बोर्ड ===
-आयताकार m × n बोर्डों के लिए B<sub>''m'',''n''</sub>, हम R लिखते हैं<sub>m,n</sub>:= आर<sub>B<sub>''m'',''n''</sub></ उप>, और यदि एम = एन, आर<sub>n</sub>:= आर<sub>''m'',''n''</sub>.
+आयताकार एम × एनबोर्डों के लिए B<sub>''एम'',''एन''</sub>, हम R लिखते हैं<sub>एम,एन</sub>:= आर<sub>B<sub>''एम'',''एन''</sub></ उप>, और यदि एम = एन, आर<sub>एन</sub>:= आर<sub>''एम'',''एन''</sub>.
-वर्ग n × n बोर्डों पर पहले कुछ रूक बहुपद हैं:
+वर्ग एन× एनबोर्डों पर पहले कुछ रूक बहुपद हैं:
 : <math>\begin{align}
@@ Line 44: / Line 45: @@
 शब्दों में, इसका मतलब यह है कि 1 × 1 बोर्ड पर, 1 हाथी को 1 तरीके से व्यवस्थित किया जा सकता है, और शून्य हाथी को भी 1 तरीके से व्यवस्थित किया जा सकता है (खाली बोर्ड); एक पूर्ण 2 × 2 बोर्ड पर, 2 हाथी 2 तरीकों से (विकर्णों पर) व्यवस्थित किए जा सकते हैं, 1 हाथी 4 तरीकों से व्यवस्थित किए जा सकते हैं, और शून्य हाथी 1 तरीके से व्यवस्थित किए जा सकते हैं; और इसी तरह बड़े बोर्डों के लिए।
-एक आयताकार शतरंज की बिसात का किश्ती बहुपद सामान्यीकृत [[लैगुएरे बहुपद]] एल से निकटता से संबंधित है<sub>''n''</sub><sup>α</sup>(x) सर्वसमिका द्वारा
+एक आयताकार शतरंज की बिसात का किश्ती बहुपद सामान्यीकृत [[लैगुएरे बहुपद]] एल से निकटता से संबंधित है<sub>''एन''</sub><sup>α</sup>(x) सर्वसमिका द्वारा
 : <math>R_{m,n}(x)= n! x^n L_n^{(m-n)}(-x^{-1}).</math>
@@ Line 53: / Line 54: @@
 एक रूक बहुपद एक प्रकार के मेल खाने वाले बहुपद का एक विशेष मामला है, जो एक ग्राफ में के-एज [[मिलान (ग्राफ सिद्धांत)]] की संख्या का जनरेटिंग फ़ंक्शन है।
-रूक बहुपद आर<sub>''m'',''n''</sub>(x) [[पूर्ण द्विदलीय ग्राफ]]़ K के अनुरूप है<sub>''m'',''n''</sub>. सामान्य बोर्ड का रूक बहुपद B ⊆ B<sub>''m'',''n''</sub> बाएं कोने v के साथ द्विदलीय ग्राफ से मेल खाता है<sub>1</sub>, में<sub>2</sub>, ..., में<sub>''m''</sub> और दाएँ शीर्ष w<sub>1</sub>, में<sub>2</sub>, ..., में<sub>''n''</sub> और एक किनारे वी<sub>''i''</sub>w<sub>''j''</sub> जब भी वर्ग (i, j) की अनुमति दी जाती है, यानी, बी से संबंधित होता है। इस प्रकार, रूक बहुपदों का सिद्धांत, एक अर्थ में, मिलान करने वाले बहुपदों में निहित है।
+रूक बहुपद आर<sub>''एम'',''एन''</sub>(x) [[पूर्ण द्विदलीय ग्राफ]]़ K के अनुरूप है<sub>''एम'',''एन''</sub>. सामान्य बोर्ड का रूक बहुपद B ⊆ B<sub>''एम'',</sub>एनबाएं कोने v के साथ द्विदलीय ग्राफ से मेल खाता है<sub>1</sub>, में<sub>2</sub>, ..., में<sub>''एम''</sub> और दाएँ शीर्ष w<sub>1</sub>, में<sub>2</sub>, ..., मेंएनऔर एक किनारे वी<sub>''i''</sub>w<sub>''j''</sub> जब भी वर्ग (i, j) की अनुमति दी जाती है, यानी, बी से संबंधित होता है। इस प्रकार, रूक बहुपदों का सिद्धांत, एक अर्थ में, मिलान करने वाले बहुपदों में निहित है।
 हम गुणांक r के बारे में एक महत्वपूर्ण तथ्य निकालते हैं<sub>''k''</sub>, जिसे हम B में k rooks के गैर-हमलावर प्लेसमेंट की संख्या को देखते हुए याद करते हैं: ये संख्याएँ असमान हैं, अर्थात, वे अधिकतम तक बढ़ती हैं और फिर घटती हैं। यह हेइलमैन और लिब के प्रमेय से (एक मानक तर्क द्वारा) अनुसरण करता है<ref>Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems.  ''Communications in Mathematical Physics'', Vol. 25 (1972), pp. 190–232.</ref> एक मेल खाने वाले बहुपद के शून्यों के बारे में (उससे भिन्न जो एक रूक बहुपद से संबंधित है, लेकिन चर के परिवर्तन के तहत इसके बराबर है), जिसका अर्थ है कि एक रूक बहुपद के सभी शून्य ऋणात्मक वास्तविक संख्याएं हैं।
@@ Line 59: / Line 60: @@
 == मैट्रिक्स स्थायी से कनेक्शन ==
-अधूरे वर्ग n × n बोर्डों के लिए, (अर्थात बोर्ड के वर्गों के कुछ मनमाना उपसमुच्चय पर बदमाशों को खेलने की अनुमति नहीं है) बोर्ड पर n बदमाशों को रखने के तरीकों की संख्या की गणना 0 के [[स्थायी (गणित)]] की गणना करने के बराबर है -1 मैट्रिक्स।
+अधूरे वर्ग एन× एनबोर्डों के लिए, (अर्थात बोर्ड के वर्गों के कुछ मनमाना उपसमुच्चय पर बदमाशों को खेलने की अनुमति नहीं है) बोर्ड पर एनबदमाशों को रखने के तरीकों की संख्या की गणना 0 के [[स्थायी (गणित)]] की गणना करने के बराबर है -1 मैट्रिक्स।
 == पूरा आयताकार बोर्ड ==
@@ Line 80: / Line 81: @@
 किश्ती बहुपद का अग्रदूत महामहिम ड्यूडेनी द्वारा क्लासिक आठ हाथी समस्या है<ref>Dudeney, Henry E. Amusements In Mathematics. 1917. Nelson. (republished by Plain Label Books: {{isbn|1-60303-152-9}}, also as a collection of newspaper clippings, Dover Publications, 1958; Kessinger Publishing, 2006). The book can be freely downloaded from [[Project Gutenberg]] site [https://www.gutenberg.org/ebooks/16713]</ref> जिसमें वह दिखाता है कि शतरंज की बिसात पर गैर-हमलावर बदमाशों की अधिकतम संख्या आठ है, उन्हें मुख्य विकर्णों में से एक पर रखकर (चित्र 1)। पूछा गया प्रश्न है: 8 × 8 शतरंज की बिसात पर आठ बदमाशों को कितने तरीकों से रखा जा सकता है ताकि उनमें से कोई भी दूसरे पर हमला न करे? उत्तर है: स्पष्ट रूप से प्रत्येक पंक्ति और प्रत्येक स्तंभ में एक किश्ती होना चाहिए। नीचे की पंक्ति से शुरू करते हुए, यह स्पष्ट है कि पहला हाथी आठ अलग-अलग वर्गों में से किसी एक पर रखा जा सकता है (चित्र 1)। इसे जहां भी रखा गया है, दूसरी पंक्ति में दूसरे हाथी के लिए सात चौकों का विकल्प है। फिर छह वर्ग हैं जिनमें से तीसरी पंक्ति का चयन करना है, पांच चौथी में, और इसी तरह। इसलिए अलग-अलग तरीकों की संख्या 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320 होनी चाहिए (अर्थात, 8<nowiki>!</nowiki>, जहाँ ! भाज्य है)।<ref>Dudeney, Problem 295</ref>
-एक ही परिणाम थोड़े अलग तरीके से प्राप्त किया जा सकता है। आइए हम प्रत्येक हाथी को उसके रैंक की संख्या के अनुरूप एक स्थितीय संख्या दें, और उसे एक नाम दें जो उसकी फ़ाइल के नाम से मेल खाता हो। इस प्रकार, rook a1 की स्थिति 1 है और name a, rook b2 की स्थिति 2 और नाम b है, आदि। फिर आइए हम roooks को उनकी स्थिति के अनुसार एक क्रमित सूची ([[अनुक्रम]]) में क्रमबद्ध करें। चित्र 1 पर आरेख फिर अनुक्रम (ए, बी, सी, डी, ई, एफ, जी, एच) में बदल जाएगा। किसी अन्य फ़ाइल पर किसी भी हाथी को रखने से पहले हाथी द्वारा खाली की गई फ़ाइल में दूसरी फ़ाइल पर कब्जा करने वाले हाथी को स्थानांतरित करना शामिल होगा। उदाहरण के लिए, यदि रूक ए1 को बी फाइल में ले जाया जाता है, तो रूक बी2 को एक फाइल में स्थानांतरित किया जाना चाहिए, और अब वे रूक बी1 और रूक ए2 बन जाएंगे। नया अनुक्रम बन जाएगा (बी, ए, सी, डी, ई, एफ, जी, एच)। कॉम्बिनेटरिक्स में, इस ऑपरेशन को क्रमचय कहा जाता है, और क्रमपरिवर्तन के परिणामस्वरूप प्राप्त अनुक्रम दिए गए अनुक्रम के क्रमपरिवर्तन हैं। 8 तत्वों के अनुक्रम से 8 तत्वों वाले क्रमचय की कुल संख्या 8 है! (8 का भाज्य)।
+एक ही परिणाम थोड़े अलग तरीके से प्राप्त किया जा सकता है। आइए हम प्रत्येक हाथी को उसके रैंक की संख्या के अनुरूप एक स्थितीय संख्या दें, और उसे एक नाम दें जो उसकी फ़ाइल के नाम से मेल खाता हो। इस प्रकार, rook a1 की स्थिति 1 है और एनaएमe a, rook b2 की स्थिति 2 और नाम b है, आदि। फिर आइए हम roooks को उनकी स्थिति के अनुसार एक क्रमित सूची ([[अनुक्रम]]) में क्रमबद्ध करें। चित्र 1 पर आरेख फिर अनुक्रम (ए, बी, सी, डी, ई, एफ, जी, एच) में बदल जाएगा। किसी अन्य फ़ाइल पर किसी भी हाथी को रखने से पहले हाथी द्वारा खाली की गई फ़ाइल में दूसरी फ़ाइल पर कब्जा करने वाले हाथी को स्थानांतरित करना शामिल होगा। उदाहरण के लिए, यदि रूक ए1 को बी फाइल में ले जाया जाता है, तो रूक बी2 को एक फाइल में स्थानांतरित किया जाना चाहिए, और अब वे रूक बी1 और रूक ए2 बन जाएंगे। नया अनुक्रम बन जाएगा (बी, ए, सी, डी, ई, एफ, जी, एच)। कॉम्बिनेटरिक्स में, इस ऑपरेशन को क्रमचय कहा जाता है, और क्रमपरिवर्तन के परिणामस्वरूप प्राप्त अनुक्रम दिए गए अनुक्रम के क्रमपरिवर्तन हैं। 8 तत्वों के अनुक्रम से 8 तत्वों वाले क्रमचय की कुल संख्या 8 है! (8 का भाज्य)।
 लगाए गए सीमा के प्रभाव का आकलन करने के लिए बदमाशों को एक दूसरे पर हमला नहीं करना चाहिए, इस तरह की सीमा के बिना समस्या पर विचार करें। 8 × 8 शतरंज की बिसात पर आठ हाथी कितने प्रकार से रखे जा सकते हैं? यह 64 चौकों पर 8 बदमाशों के [[संयोजन]]ों की कुल संख्या होगी:
@@ Line 87: / Line 88: @@
 इस प्रकार, सीमावर्ती बदमाशों को एक-दूसरे पर हमला नहीं करना चाहिए, संयोजनों से क्रमपरिवर्तन तक स्वीकार्य पदों की कुल संख्या को कम कर देता है जो लगभग 109,776 का कारक है।
-मानव गतिविधि के विभिन्न क्षेत्रों से कई समस्याओं को एक रूक फॉर्मूलेशन देकर रूक समस्या में कम किया जा सकता है। एक उदाहरण के रूप में: एक कंपनी को अलग-अलग नौकरियों पर n श्रमिकों को नियुक्त करना चाहिए और प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाना चाहिए। यह नियुक्ति कितने तरीकों से की जा सकती है?
+मानव गतिविधि के विभिन्न क्षेत्रों से कई समस्याओं को एक रूक फॉर्मूलेशन देकर रूक समस्या में कम किया जा सकता है। एक उदाहरण के रूप में: एक कंपनी को अलग-अलग नौकरियों पर एनश्रमिकों को नियुक्त करना चाहिए और प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाना चाहिए। यह नियुक्ति कितने तरीकों से की जा सकती है?
-आइए हम कार्यकर्ताओं को n × n शतरंज की बिसात पर, और नौकरियों को - फाइलों पर रखें। यदि कार्यकर्ता i को जॉब j पर नियुक्त किया जाता है, तो उस वर्ग पर एक हाथी रखा जाता है जहाँ रैंक i फ़ाइल j को पार करता है। चूँकि प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाता है और प्रत्येक कार्यकर्ता को केवल एक ही कार्य के लिए नियुक्त किया जाता है, बोर्ड पर n बदमाशों की व्यवस्था के परिणामस्वरूप सभी फाइलों और रैंकों में केवल एक बदमाश होगा, यानी बदमाश हमला नहीं करते हैं एक-दूसरे से।
+आइए हम कार्यकर्ताओं को एन× एनशतरंज की बिसात पर, और नौकरियों को - फाइलों पर रखें। यदि कार्यकर्ता i को जॉब j पर नियुक्त किया जाता है, तो उस वर्ग पर एक हाथी रखा जाता है जहाँ रैंक i फ़ाइल j को पार करता है। चूँकि प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाता है और प्रत्येक कार्यकर्ता को केवल एक ही कार्य के लिए नियुक्त किया जाता है, बोर्ड पर एनबदमाशों की व्यवस्था के परिणामस्वरूप सभी फाइलों और रैंकों में केवल एक बदमाश होगा, यानी बदमाश हमला नहीं करते हैं एक-दूसरे से।
 === रूक बहुपद रूक समस्या के सामान्यीकरण के रूप में ===
@@ Line 95: / Line 96: @@
 क्लासिकल रूक्स समस्या तुरंत r का मान देती है<sub>8</sub>, किश्ती बहुपद के उच्चतम क्रम पद के सामने गुणांक। दरअसल, इसका परिणाम यह है कि 8 गैर-हमलावर बदमाशों को आर में 8 × 8 शतरंज की बिसात पर व्यवस्थित किया जा सकता है<sub>8</sub> = 8! = 40320 तरीके।
-आइए हम एक एम × एन बोर्ड, यानी एम रैंक (पंक्तियों) और एन फाइलों (कॉलम) वाले बोर्ड पर विचार करके इस समस्या को सामान्य करें। समस्या यह हो जाती है: एक m × n बोर्ड पर कितने तरीकों से किश्ती को इस तरह से व्यवस्थित किया जा सकता है कि वे एक दूसरे पर हमला न करें?
+आइए हम एक एम × एन बोर्ड, यानी एम रैंक (पंक्तियों) और एन फाइलों (कॉलम) वाले बोर्ड पर विचार करके इस समस्या को सामान्य करें। समस्या यह हो जाती है: एक एम × एनबोर्ड पर कितने तरीकों से किश्ती को इस तरह से व्यवस्थित किया जा सकता है कि वे एक दूसरे पर हमला न करें?
-यह स्पष्ट है कि समस्या को हल करने योग्य होने के लिए, k को संख्याओं m और n में से छोटी संख्या से कम या उसके बराबर होना चाहिए; अन्यथा कोई बदमाशों की एक जोड़ी को रैंक या फाइल पर रखने से बच नहीं सकता है। यह शर्त पूरी हो जाए। फिर किश्ती की व्यवस्था दो चरणों में की जा सकती है। सबसे पहले, k रैंकों का सेट चुनें जिस पर बदमाशों को रखना है। चूंकि रैंकों की संख्या m है, जिनमें से k को चुना जाना चाहिए, यह चुनाव में किया जा सकता है <math>\binom{m}{k}</math> तौर तरीकों। इसी तरह, k फ़ाइलों का सेट जिस पर बदमाशों को रखना है, उसमें चुना जा सकता है <math>\binom{n}{k}</math> तौर तरीकों। क्योंकि फ़ाइलों की पसंद रैंकों की पसंद पर निर्भर नहीं करती है, उत्पादों के नियम के अनुसार होते हैं <math>\binom{m}{k}\binom{n}{k}</math> वर्ग चुनने के तरीके जिस पर किश्ती रखा जाए।
+यह स्पष्ट है कि समस्या को हल करने योग्य होने के लिए, k को संख्याओं एम और एनमें से छोटी संख्या से कम या उसके बराबर होना चाहिए; अन्यथा कोई बदमाशों की एक जोड़ी को रैंक या फाइल पर रखने से बच नहीं सकता है। यह शर्त पूरी हो जाए। फिर किश्ती की व्यवस्था दो चरणों में की जा सकती है। सबसे पहले, k रैंकों का सेट चुनें जिस पर बदमाशों को रखना है। चूंकि रैंकों की संख्या एम है, जिनमें से k को चुना जाना चाहिए, यह चुनाव में किया जा सकता है <math>\binom{m}{k}</math> तौर तरीकों। इसी तरह, k फ़ाइलों का सेट जिस पर बदमाशों को रखना है, उसमें चुना जा सकता है <math>\binom{n}{k}</math> तौर तरीकों। क्योंकि फ़ाइलों की पसंद रैंकों की पसंद पर निर्भर नहीं करती है, उत्पादों के नियम के अनुसार होते हैं <math>\binom{m}{k}\binom{n}{k}</math> वर्ग चुनने के तरीके जिस पर किश्ती रखा जाए।
 हालाँकि, कार्य अभी तक समाप्त नहीं हुआ है क्योंकि k रैंक और k फ़ाइलें k में प्रतिच्छेद करती हैं<sup>2</sup> वर्ग। अप्रयुक्त रैंकों और फ़ाइलों को हटाने और शेष रैंकों और फ़ाइलों को एक साथ जोड़कर, एक k रैंक और k फ़ाइलों का एक नया बोर्ड प्राप्त करता है। यह पहले से ही दिखाया गया था कि इस तरह के बोर्ड पर k बदमाशों को k में व्यवस्थित किया जा सकता है! तरीके (ताकि वे एक दूसरे पर हमला न करें)। इसलिए, संभावित गैर-आक्रमणकारी बदमाश व्यवस्थाओं की कुल संख्या है:<ref>Vilenkin, Naum Ya. Combinatorics (Kombinatorika). 1969. Nauka Publishers, Moscow (In Russian).</ref>
@@ Line 106: / Line 107: @@
 :<math>R_{m,n}(x) = \sum_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} k! x^k = \sum_{k=0}^{\min(m,n)}\frac{n! m!}{k! (n-k)! (m-k)!} x^k.</math>
-यदि बदमाशों को एक दूसरे पर हमला नहीं करना चाहिए की सीमा को हटा दिया जाता है, तो किसी को m × n वर्गों में से किसी भी k वर्ग को चुनना होगा। इसमें किया जा सकता है:
+यदि बदमाशों को एक दूसरे पर हमला नहीं करना चाहिए की सीमा को हटा दिया जाता है, तो किसी को एम × एनवर्गों में से किसी भी k वर्ग को चुनना होगा। इसमें किया जा सकता है:
 :<math>\binom{mn}{k} = \frac{(mn)!}{k! (mn-k)!}</math> तौर तरीकों।
@@ Line 129: / Line 130: @@
 | '''Fig. 2.''' A symmetric arrangement of non-attacking rooks about the centre of an 8 × 8 chessboard. Dots mark the 4 central squares that surround the centre of symmetry.
 }}
-उन व्यवस्थाओं में सबसे सरल तब होती है जब हाथी बोर्ड के केंद्र के बारे में सममित होते हैं। आइए जी के साथ नामित करें<sub>n</sub>व्यवस्थाओं की संख्या जिसमें n बदमाशों को n रैंकों और n फ़ाइलों वाले बोर्ड पर रखा जाता है। अब हम बोर्ड को 2n रैंक और 2n फाइल रखने के लिए बनाते हैं। पहली फ़ाइल पर किश्ती को उस फ़ाइल के किसी भी 2n वर्ग पर रखा जा सकता है। समरूपता की स्थिति के अनुसार, इस हाथी का स्थान उस हाथी के स्थान को परिभाषित करता है जो अंतिम फ़ाइल पर खड़ा होता है - इसे बोर्ड केंद्र के बारे में पहले हाथी के लिए सममित रूप से व्यवस्थित किया जाना चाहिए। आइए हम पहली और आखिरी फाइलों और रैंकों को हटा दें जो कि बदमाशों के कब्जे में हैं (चूंकि रैंकों की संख्या सम है, हटाए गए बदमाश एक ही रैंक पर खड़े नहीं हो सकते हैं)। यह 2n−2 फ़ाइलों और 2n−2 रैंकों का एक बोर्ड देगा। यह स्पष्ट है कि नए बोर्ड पर बदमाशों की प्रत्येक सममित व्यवस्था मूल बोर्ड पर बदमाशों की सममित व्यवस्था से मेल खाती है। इसलिए, जी<sub>2''n''</sub> = 2एनजी<sub>2''n''&nbsp;−&nbsp;2</sub> (इस अभिव्यक्ति में कारक 2n पहली फाइल पर 2n वर्गों में से किसी पर कब्जा करने के लिए पहली रूक की संभावना से आता है)। उपरोक्त सूत्र को दोहराने से एक 2 × 2 बोर्ड के मामले तक पहुंचता है, जिस पर 2 सममित व्यवस्थाएं (विकर्णों पर) होती हैं। इस पुनरावृत्ति के परिणामस्वरूप, अंतिम अभिव्यक्ति G है<sub>2''n''</sub> = 2<sup>एन</sup>एन! सामान्य शतरंज की बिसात (8 × 8) के लिए, G<sub>8</sub> = 2<sup>4</sup> × 4! = 16 × 24 = 384 8 हाथी की केंद्रीय सममित व्यवस्था। ऐसी ही एक व्यवस्था चित्र 2 में दिखाई गई है।
+उन व्यवस्थाओं में सबसे सरल तब होती है जब हाथी बोर्ड के केंद्र के बारे में सममित होते हैं। आइए जी के साथ नामित करें<sub>एन</sub>व्यवस्थाओं की संख्या जिसमें एनबदमाशों को एनरैंकों और एनफ़ाइलों वाले बोर्ड पर रखा जाता है। अब हम बोर्ड को 2एनरैंक और 2एनफाइल रखने के लिए बनाते हैं। पहली फ़ाइल पर किश्ती को उस फ़ाइल के किसी भी 2एनवर्ग पर रखा जा सकता है। समरूपता की स्थिति के अनुसार, इस हाथी का स्थान उस हाथी के स्थान को परिभाषित करता है जो अंतिम फ़ाइल पर खड़ा होता है - इसे बोर्ड केंद्र के बारे में पहले हाथी के लिए सममित रूप से व्यवस्थित किया जाना चाहिए। आइए हम पहली और आखिरी फाइलों और रैंकों को हटा दें जो कि बदमाशों के कब्जे में हैं (चूंकि रैंकों की संख्या सम है, हटाए गए बदमाश एक ही रैंक पर खड़े नहीं हो सकते हैं)। यह 2एन−2 फ़ाइलों और 2एन−2 रैंकों का एक बोर्ड देगा। यह स्पष्ट है कि नए बोर्ड पर बदमाशों की प्रत्येक सममित व्यवस्था मूल बोर्ड पर बदमाशों की सममित व्यवस्था से मेल खाती है। इसलिए, जी<sub>2</sub>एन= 2एनजी<sub>2''एन''&nbsp;−&nbsp;2</sub> (इस अभिव्यक्ति में कारक 2एनपहली फाइल पर 2एनवर्गों में से किसी पर कब्जा करने के लिए पहली रूक की संभावना से आता है)। उपरोक्त सूत्र को दोहराने से एक 2 × 2 बोर्ड के मामले तक पहुंचता है, जिस पर 2 सममित व्यवस्थाएं (विकर्णों पर) होती हैं। इस पुनरावृत्ति के परिणामस्वरूप, अंतिम अभिव्यक्ति G है<sub>2</sub>एन= 2<sup>एन</sup>एन! सामान्य शतरंज की बिसात (8 × 8) के लिए, G<sub>8</sub> = 2<sup>4</sup> × 4! = 16 × 24 = 384 8 हाथी की केंद्रीय सममित व्यवस्था। ऐसी ही एक व्यवस्था चित्र 2 में दिखाई गई है।
-विषम-आकार के बोर्डों के लिए (जिसमें 2n + 1 रैंक और 2n + 1 फ़ाइलें होती हैं) हमेशा एक ऐसा वर्ग होता है जिसका सममित दोहरा नहीं होता है - यह बोर्ड का केंद्रीय वर्ग होता है। इस चौक पर हमेशा एक हाथी रखा होना चाहिए। केंद्रीय फ़ाइल और रैंक को हटाने से, 2n × 2n बोर्ड पर 2n बदमाशों की एक सममित व्यवस्था प्राप्त होती है। इसलिए ऐसे बोर्ड के लिए एक बार फिर जी<sub>2''n''&nbsp;+&nbsp;1</sub> = जी<sub>2''n''</sub> = 2<sup>एन</sup>एन!.
+विषम-आकार के बोर्डों के लिए (जिसमें 2एन+ 1 रैंक और 2एन+ 1 फ़ाइलें होती हैं) हमेशा एक ऐसा वर्ग होता है जिसका सममित दोहरा नहीं होता है - यह बोर्ड का केंद्रीय वर्ग होता है। इस चौक पर हमेशा एक हाथी रखा होना चाहिए। केंद्रीय फ़ाइल और रैंक को हटाने से, 2एन× 2एनबोर्ड पर 2एनबदमाशों की एक सममित व्यवस्था प्राप्त होती है। इसलिए ऐसे बोर्ड के लिए एक बार फिर जी<sub>2''एन''&nbsp;+&nbsp;1</sub> = जी<sub>2</sub>एन= 2<sup>एन</sup>एन!.
-थोड़ी अधिक जटिल समस्या गैर-आक्रमणकारी व्यवस्थाओं की संख्या का पता लगाना है जो बोर्ड के 90 डिग्री रोटेशन पर नहीं बदलती हैं। बता दें कि बोर्ड में 4n फाइलें और 4n रैंक हैं, और बदमाशों की संख्या भी 4n है। इस स्थिति में, पहली फ़ाइल पर मौजूद हाथी इस फ़ाइल पर किसी भी वर्ग पर कब्जा कर सकता है, कोने के वर्गों को छोड़कर (एक हाथी कोने के वर्ग पर नहीं हो सकता है क्योंकि 90 डिग्री रोटेशन के बाद 2 हाथी एक दूसरे पर हमला करेंगे)। वहाँ अन्य 3 हाथी हैं जो उस हाथी से मेल खाते हैं और वे क्रमशः अंतिम रैंक, अंतिम फ़ाइल और पहली रैंक पर खड़े होते हैं (वे पहले हाथी से 90°, 180°, और 270° रोटेशन द्वारा प्राप्त किए जाते हैं)। उन बदमाशों की फाइलों और रैंकों को हटाकर, आवश्यक समरूपता के साथ एक (4n − 4) × (4n − 4) बोर्ड के लिए किश्ती की व्यवस्था प्राप्त करता है। इस प्रकार, निम्नलिखित [[पुनरावृत्ति संबंध]] प्राप्त होता है: R<sub>4''n''</sub> = (4एन - 2)आर<sub>4''n''&nbsp;−&nbsp;4</sub>, जहां आर<sub>n</sub>n × n बोर्ड के लिए व्यवस्थाओं की संख्या है। पुनरावृत्ति, यह इस प्रकार है कि आर<sub>4''n''</sub> = 2n(2n − 1)(2n − 3)...1. एक (4n + 1) × (4n + 1) बोर्ड के लिए व्यवस्थाओं की संख्या वही है जो 4n × 4n बोर्ड की है; ऐसा इसलिए है क्योंकि (4n + 1) × (4n + 1) बोर्ड पर, एक हाथी को आवश्यक रूप से केंद्र में खड़ा होना चाहिए और इस प्रकार केंद्रीय रैंक और फ़ाइल को हटाया जा सकता है। इसलिए आर<sub>4''n''&nbsp;+&nbsp;1</sub> = आर<sub>4''n''</sub>. पारंपरिक शतरंज की बिसात (n = 2) के लिए, R<sub>8</sub> = 4 × 3 × 1 = घूर्णी समरूपता के साथ 12 संभावित व्यवस्थाएँ।
+थोड़ी अधिक जटिल समस्या गैर-आक्रमणकारी व्यवस्थाओं की संख्या का पता लगाना है जो बोर्ड के 90 डिग्री रोटेशन पर नहीं बदलती हैं। बता दें कि बोर्ड में 4एनफाइलें और 4एनरैंक हैं, और बदमाशों की संख्या भी 4एनहै। इस स्थिति में, पहली फ़ाइल पर मौजूद हाथी इस फ़ाइल पर किसी भी वर्ग पर कब्जा कर सकता है, कोने के वर्गों को छोड़कर (एक हाथी कोने के वर्ग पर नहीं हो सकता है क्योंकि 90 डिग्री रोटेशन के बाद 2 हाथी एक दूसरे पर हमला करेंगे)। वहाँ अन्य 3 हाथी हैं जो उस हाथी से मेल खाते हैं और वे क्रमशः अंतिम रैंक, अंतिम फ़ाइल और पहली रैंक पर खड़े होते हैं (वे पहले हाथी से 90°, 180°, और 270° रोटेशन द्वारा प्राप्त किए जाते हैं)। उन बदमाशों की फाइलों और रैंकों को हटाकर, आवश्यक समरूपता के साथ एक (4एन− 4) × (4एन− 4) बोर्ड के लिए किश्ती की व्यवस्था प्राप्त करता है। इस प्रकार, निम्नलिखित [[पुनरावृत्ति संबंध]] प्राप्त होता है: R<sub>4</sub>एन= (4एन - 2)आर<sub>4''एन''&nbsp;−&nbsp;4</sub>, जहां आर<sub>एन</sub>एन× एनबोर्ड के लिए व्यवस्थाओं की संख्या है। पुनरावृत्ति, यह इस प्रकार है कि आर<sub>4</sub>एन= 2एन(2एन− 1)(2एन− 3)...1. एक (4एन+ 1) × (4एन+ 1) बोर्ड के लिए व्यवस्थाओं की संख्या वही है जो 4एन× 4एनबोर्ड की है; ऐसा इसलिए है क्योंकि (4एन+ 1) × (4एन+ 1) बोर्ड पर, एक हाथी को आवश्यक रूप से केंद्र में खड़ा होना चाहिए और इस प्रकार केंद्रीय रैंक और फ़ाइल को हटाया जा सकता है। इसलिए आर<sub>4''एन''&nbsp;+&nbsp;1</sub> = आर<sub>4''एन''</sub>. पारंपरिक शतरंज की बिसात (एन= 2) के लिए, R<sub>8</sub> = 4 × 3 × 1 = घूर्णी समरूपता के साथ 12 संभावित व्यवस्थाएँ।
-(4n + 2) × (4n + 2) और (4n + 3) × (4n + 3) बोर्डों के लिए, समाधान की संख्या शून्य है। प्रत्येक हाथी के लिए दो स्थितियाँ संभव हैं: या तो वह बीच में खड़ा हो या वह बीच में न खड़ा हो। दूसरे मामले में, यह हाथी उस चौकड़ी में शामिल है जो बोर्ड को 90° पर मोड़ने पर वर्गों का आदान-प्रदान करती है। इसलिए, बदमाशों की कुल संख्या या तो 4n होनी चाहिए (जब बोर्ड पर कोई केंद्रीय वर्ग न हो) या 4n + 1। यह साबित करता है कि R<sub>4''n''&nbsp;+&nbsp;2</sub> = आर<sub>4''n''&nbsp;+&nbsp;3</sub> = 0।
+(4एन+ 2) × (4एन+ 2) और (4एन+ 3) × (4एन+ 3) बोर्डों के लिए, समाधान की संख्या शून्य है। प्रत्येक हाथी के लिए दो स्थितियाँ संभव हैं: या तो वह बीच में खड़ा हो या वह बीच में न खड़ा हो। दूसरे मामले में, यह हाथी उस चौकड़ी में शामिल है जो बोर्ड को 90° पर मोड़ने पर वर्गों का आदान-प्रदान करती है। इसलिए, बदमाशों की कुल संख्या या तो 4एनहोनी चाहिए (जब बोर्ड पर कोई केंद्रीय वर्ग न हो) या 4एन+ 1। यह साबित करता है कि R<sub>4''एन''&nbsp;+&nbsp;2</sub> = आर<sub>4''एन''&nbsp;+&nbsp;3</sub> = 0।
-एक n × n बोर्ड पर विकर्णों में से किसी एक विकर्ण (निर्धारणता के लिए, शतरंज की बिसात पर a1–h8 के संगत विकर्ण) के सममित n गैर-हमलावर बदमाशों की व्यवस्था की संख्या पुनरावृत्ति Q द्वारा परिभाषित [[टेलीफोन नंबर (गणित)]] द्वारा दी गई है<sub>''n''</sub> = क्यू<sub>''n''&nbsp;−&nbsp;1</sub> + (एन − 1)क्यू<sub>''n''&nbsp;−&nbsp;2</sub>. यह पुनरावृत्ति निम्न प्रकार से प्राप्त होती है। ध्यान दें कि पहली फ़ाइल पर किश्ती या तो निचले कोने के वर्ग पर खड़ा होता है या यह दूसरे वर्ग पर खड़ा होता है। पहले मामले में, पहली फ़ाइल और पहली रैंक को हटाने से एक (n − 1) × (n − 1) बोर्ड पर सममित व्यवस्था n − 1 रूक हो जाती है। ऐसी व्यवस्थाओं की संख्या Q है<sub>''n''&nbsp;−&nbsp;1</sub>. दूसरे मामले में, मूल किश्ती के लिए एक और किश्ती है, जो चुने हुए विकर्ण के बारे में पहले वाले के लिए सममित है। उन बदमाशों की फाइलों और रैंकों को हटाने से n − 2 हाथी एक (n − 2) × (n − 2) बोर्ड पर एक सममित व्यवस्था की ओर जाता है। चूँकि ऐसी व्यवस्थाओं की संख्या Q है<sub>''n''&nbsp;−&nbsp;2</sub> और हाथी को पहली फ़ाइल के n − 1 वर्ग पर रखा जा सकता है, वहाँ (n − 1)Q हैं<sub>''n''&nbsp;−&nbsp;2</sub> ऐसा करने के तरीके, जो उपरोक्त पुनरावृत्ति को तुरंत देते हैं। विकर्ण-सममित व्यवस्था की संख्या तब अभिव्यक्ति द्वारा दी जाती है:
+एक एन× एनबोर्ड पर विकर्णों में से किसी एक विकर्ण (निर्धारणता के लिए, शतरंज की बिसात पर a1–h8 के संगत विकर्ण) के सममित एनगैर-हमलावर बदमाशों की व्यवस्था की संख्या पुनरावृत्ति Q द्वारा परिभाषित [[टेलीफोन नंबर (गणित)]] द्वारा दी गई हैएन= क्यू<sub>''एन''&nbsp;−&nbsp;1</sub> + (एन − 1)क्यू<sub>''एन''&nbsp;−&nbsp;2</sub>. यह पुनरावृत्ति निम्न प्रकार से प्राप्त होती है। ध्यान दें कि पहली फ़ाइल पर किश्ती या तो निचले कोने के वर्ग पर खड़ा होता है या यह दूसरे वर्ग पर खड़ा होता है। पहले मामले में, पहली फ़ाइल और पहली रैंक को हटाने से एक (एन− 1) × (एन− 1) बोर्ड पर सममित व्यवस्था एन− 1 रूक हो जाती है। ऐसी व्यवस्थाओं की संख्या Q है<sub>''एन''&nbsp;−&nbsp;1</sub>. दूसरे मामले में, मूल किश्ती के लिए एक और किश्ती है, जो चुने हुए विकर्ण के बारे में पहले वाले के लिए सममित है। उन बदमाशों की फाइलों और रैंकों को हटाने से एन− 2 हाथी एक (एन− 2) × (एन− 2) बोर्ड पर एक सममित व्यवस्था की ओर जाता है। चूँकि ऐसी व्यवस्थाओं की संख्या Q है<sub>''एन''&nbsp;−&nbsp;2</sub> और हाथी को पहली फ़ाइल के एन− 1 वर्ग पर रखा जा सकता है, वहाँ (एन− 1)Q हैं<sub>''एन''&nbsp;−&nbsp;2</sub> ऐसा करने के तरीके, जो उपरोक्त पुनरावृत्ति को तुरंत देते हैं। विकर्ण-सममित व्यवस्था की संख्या तब अभिव्यक्ति द्वारा दी जाती है:
 :<math>Q_n = 1 + \binom{n}{2} + \frac{1}{1 \times 2}\binom{n}{2}\binom{n-2}{2} + \frac{1}{1 \times 2 \times 3}\binom{n}{2}\binom{n-2}{2}\binom{n-4}{2} + \cdots.</math>
-यह अभिव्यक्ति वर्गों में सभी किश्ती व्यवस्थाओं को विभाजित करके प्राप्त की जाती है; कक्षा में वे व्यवस्थाएँ हैं जिनमें बदमाशों के जोड़े विकर्ण पर नहीं खड़े होते हैं। ठीक उसी तरह, यह दिखाया जा सकता है कि एक n × n बोर्ड पर n-रूक व्यवस्था की संख्या, जैसे कि वे एक-दूसरे पर हमला नहीं करते हैं और दोनों विकर्णों के सममित होते हैं, पुनरावृत्ति समीकरण B द्वारा दिया जाता है<sub>2''n''</sub> = पिता<sub>2''n''&nbsp;−&nbsp;2</sub> + (2एन − 2)बी<sub>2''n''&nbsp;−&nbsp;4</sub> और बी<sub>2''n''&nbsp;+&nbsp;1</sub> = बी<sub>2''n''</sub>.
+यह अभिव्यक्ति वर्गों में सभी किश्ती व्यवस्थाओं को विभाजित करके प्राप्त की जाती है; कक्षा में वे व्यवस्थाएँ हैं जिनमें बदमाशों के जोड़े विकर्ण पर नहीं खड़े होते हैं। ठीक उसी तरह, यह दिखाया जा सकता है कि एक एन× एनबोर्ड पर एन-रूक व्यवस्था की संख्या, जैसे कि वे एक-दूसरे पर हमला नहीं करते हैं और दोनों विकर्णों के सममित होते हैं, पुनरावृत्ति समीकरण B द्वारा दिया जाता है<sub>2</sub>एन= पिता<sub>2''एन''&nbsp;−&nbsp;2</sub> + (2एन − 2)बी<sub>2''एन''&nbsp;−&nbsp;4</sub> और बी<sub>2''एन''&nbsp;+&nbsp;1</sub> = बी<sub>2''एन''</sub>.
 === समरूपता वर्गों द्वारा गिने जाने वाली व्यवस्था ===

Anonymous

Search

रूक बहुपद: Difference between revisions

Namespaces

More

Page actions

Revision as of 14:02, 17 March 2023

Contents