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

Latest revision as of 14:40, 29 August 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

8 × 8 शतरंज की बिसात पर बदमाशों की एक संभावित व्यवस्था, जहाँ कोई भी दो टुकड़े एक पंक्ति या स्तंभ साझा नहीं करते हैं।

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

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

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

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

परिभाषा

रुक्सों बहुपद R_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]

पूर्ण बोर्ड

आयताकार m × n बोर्डों के लिए B_m,n, हम R_m,n := R_Bm,n लिखते हैंl और यदि m = n, R_{n:= R_{_m,n.}}

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

{\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 तरीके से व्यवस्थित किए जा सकते हैं; और इसी तरह बड़े बोर्डों के लिए।

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

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

मिलान बहुपद

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

रूक बहुपद R_m_,n(x) पूर्ण द्विदलीय ग्राफ़ K_m,n के अनुरूप हैl सामान्य बोर्ड का रूक बहुपद B ⊆ B_m,n बाएं कोने v_1,v₂......v_m के साथ द्विदलीय ग्राफ से मेल खाता है और दाएँ शीर्ष में w₁, ..., w₂ w_n, में और एक किनारे v_iw_j जब भी वर्ग (i, j) की अनुमति दी जाती है, यानी, B से संबंधित होता है। इस प्रकार, रूक बहुपदों का सिद्धांत, एक अर्थ में, मिलान करने वाले बहुपदों में निहित है।

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

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

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

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

रूक की समस्या

	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]

एक ही परिणाम थोड़े अलग तरीके से प्राप्त किया जा सकता है। अगर हम प्रत्येक रूक को उसके रैंक की संख्या के अनुरूप एक स्थितीय संख्या दें, और उसे एक नाम दें जो उसकी फ़ाइल के नाम से मेल खाता हो। इस प्रकार, रूक a1 की स्थिति 1 है और नाम "a", रूक b2 की स्थिति 2 और नाम "b", आदि। चित्र 1 पर आरेख फिर (अनुक्रम) (a, b, c, d, e, f, g, h) में क्रमबद्ध करें। किसी अन्य फ़ाइल पर किसी भी रूक को रखने से पहले रूक द्वारा खाली की गई फ़ाइल में दूसरी फ़ाइल पर कब्जा करने वाले रूक को स्थानांतरित करना सम्मिलित होगा। उदाहरण के लिए, यदि रूक a1 को "b" फाइल में ले जाया जाता है, तो रूक b2 को "a" फाइल में स्थानांतरित किया जाना चाहिए, और अब वे रूक b1 और रूक a2 बन जाएंगे। नया अनुक्रम बन जाएगा (b, a, c, d, e, f, g, h)। कॉम्बिनेटरिक्स में, इस ऑपरेशन को क्रमचय कहा जाता है, और क्रमपरिवर्तन के परिणामस्वरूप प्राप्त अनुक्रम दिए गए अनुक्रम के क्रमपरिवर्तन हैं। 8 तत्वों के अनुक्रम से 8 तत्वों वाले क्रमचय की कुल संख्या 8 है! (8 का भाज्य)।

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

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

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

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

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

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

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

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

यह स्पष्ट है कि समस्या को हल करने योग्य होने के लिए, k को संख्याओं m और n में से छोटी संख्या से कम या उसके बराबर होना चाहिए; अन्यथा कोई रुक्सों की एक जोड़ी को रैंक या फाइल पर रखने से बच नहीं सकता है। यह शर्त पूरी हो जाए। फिर रुक्सों की व्यवस्था दो चरणों में की जा सकती है। सबसे पहले, 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 = m = n के लिए, उपरोक्त सूत्र आर देता है r_k= n! जो शास्त्रीय रूक्स समस्या के लिए प्राप्त परिणाम के अनुरूप है।

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

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}.

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

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

तरीकों सेl

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

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

रुक्सों की समस्या की एक और जटिलता के रूप में, हमें आवश्यकता है कि रूक न केवल गैर-हमलावर हों बल्कि बोर्ड पर सममित रूप से व्यवस्थित हों। समरूपता के प्रकार के आधार पर, यह बोर्ड को घुमाने या परावर्तित करने के बराबर है। समरूपता की स्थिति के आधार पर सममित व्यवस्था कई समस्याओं का कारण बनती है।^[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

'आकृति। 2. 8 × 8 शतरंज की बिसात के केंद्र के बारे में गैर-हमलावर बदमाशों की एक सममित व्यवस्था। डॉट्स 4 केंद्रीय वर्गों को चिह्नित करते हैं जो समरूपता के केंद्र को घेरते हैं।

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

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

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

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

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

यह अभिव्यक्ति वर्गों में सभी रुक्सों व्यवस्थाओं को विभाजित करके प्राप्त की जाती है; कक्षा में वे व्यवस्थाएँ हैं जिनमें रुक्सों के जोड़े विकर् $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 .$ ण पर नहीं खड़े होते हैं। ठीक उसी तरह, यह दिखाया जा सकता है कि एक n× n बोर्ड पर n-रूक व्यवस्था की संख्या, जैसे कि वे एक-दूसरे पर हमला नहीं करते हैं और दोनों विकर्णों के सममित होते हैं, पुनरावृत्ति समीकरण द्वारा दिया जाता है B_2n = 2B_{2n − 2} + (2n − 2)B_{2n − 4} and B_{2n + 1} = B_2n.

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

एक अलग प्रकार का सामान्यीकरण वह है जिसमें बोर्ड की समरूपता द्वारा एक दूसरे से प्राप्त होने वाली रूक व्यवस्थाओं को एक के रूप में गिना जाता है। उदाहरण के लिए, यदि बोर्ड को 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'' कॉलम वाले आयताकार बोर्ड के वर्गों का कोई उपसमुच्चय हैl हम इसे उन वर्गों के रूप में सोचते हैं जिनमें किसी को एक रूक रखने की अनुमति है। यदि सभी वर्गों की अनुमति है तो बोर्ड साधारण शतरंज की बिसात है और ''m''= ''n''= 8 और किसी भी आकार की शतरंज की बिसात है यदि सभी वर्गों की अनुमति है और ''m'' = ''m'' है।  ''x'' <sup>''k''</sup> का गुणांक रूक बहुपद में R <sub>''B''</sub>(x) उन तरीकों की संख्या है, जिनमें से कोई भी दूसरे पर हमला नहीं करता है, ''B'' के वर्गों में व्यवस्थित किया जा सकता है। रूक इस तरह से व्यवस्थित होते हैं कि एक ही पंक्ति या स्तंभ में रुक्सों की कोई जोड़ी नहीं होती है। इस अर्थ में, व्यवस्था एक स्थिर, अचल बोर्ड पर रुक्सों की स्थिति है; वर्गों को स्थिर रखते हुए बोर्ड को घुमाने या प्रतिबिंबित करने पर व्यवस्था अलग नहीं होगी। बहुपद भी वही रहता है यदि रोव्स को आपस में बदल दिया जाता है या कॉलम को आपस में बदल दिया जाता है।
+[[ साहचर्य |मिश्रित]] गणित में, '''रूक बहुपद''' एक [[बिसात]] की तरह दिखने वाले बोर्ड पर गैर-हमलावर रुक्सों (शतरंज) को रखने के तरीकों की संख्या का एक जनक बहुपद है; यानी कोई भी दो रूक एक ही रोव या कॉलम में नहीं हो सकते। बोर्ड ''m'' रोव और ''n'' कॉलम वाले आयताकार बोर्ड के वर्गों का कोई उपसमुच्चय हैl हम इसे उन वर्गों के रूप में सोचते हैं जिनमें किसी को एक रूक रखने की अनुमति है। यदि सभी वर्गों की अनुमति है तो बोर्ड साधारण शतरंज की बिसात है और ''m''= ''n''= 8 और किसी भी आकार की शतरंज की बिसात है यदि सभी वर्गों की अनुमति है और ''m'' = ''m'' है।  ''x'' <sup>''k''</sup> का गुणांक रूक बहुपद में R <sub>''B''</sub>(x) उन तरीकों की संख्या है, जिनमें से कोई भी दूसरे पर हमला नहीं करता है, ''B'' के वर्गों में व्यवस्थित किया जा सकता है। रूक इस तरह से व्यवस्थित होते हैं कि एक ही पंक्ति या स्तंभ में रुक्सों की कोई जोड़ी नहीं होती है। इस अर्थ में, व्यवस्था एक स्थिर, अचल बोर्ड पर रुक्सों की स्थिति है; वर्गों को स्थिर रखते हुए बोर्ड को घुमाने या प्रतिबिंबित करने पर व्यवस्था अलग नहीं होगी। बहुपद भी वही रहता है यदि रोव्स को आपस में बदल दिया जाता है या कॉलम को आपस में बदल दिया जाता है।
 "'''रूक बहुपद'''" शब्द जॉन रिओर्डन (गणितज्ञ) द्वारा गढ़ा गया था।<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 जो कि n × n शतरंजबोर्ड का एक उपसमुच्चय है, '''''n''''' वस्तुओं के क्रमपरिवर्तन से मेल खाता है, जिसे हम संख्या 1, 2, ..., ''n'' मान सकते हैं, जैसे कि संख्या a<sub>''j''</sub> क्रमचय में j-th स्थान पर B की पंक्ति '''''j''''' में अनुमत वर्ग की स्तंभ संख्या होनी चाहिए। प्रसिद्ध उदाहरणों में  गैर-हमलावर रुक्सों को रखने के तरीकों की संख्या सम्मिलित है:
@@ Line 74: / Line 74: @@
 }}
-रुक्सों बहुपद का अग्रदूत महामहिम ड्यूडेनी द्वारा क्लासिक आठरूक समस्या है<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>
+रुक्सों बहुपद का अग्रदूत महामहिम ड्यूडेनी द्वारा क्लासिक आठ रूक समस्या है<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>
 एक ही परिणाम थोड़े अलग तरीके से प्राप्त किया जा सकता है। अगर हम प्रत्येक रूक को उसके रैंक की संख्या के अनुरूप एक स्थितीय संख्या दें, और उसे एक नाम दें जो उसकी फ़ाइल के नाम से मेल खाता हो। इस प्रकार, रूक a1 की स्थिति 1 है और नाम "a", रूक b2 की स्थिति 2 और नाम "b", आदि। चित्र 1 पर आरेख फिर ([[अनुक्रम]]) (a, b, c, d, e, f, g, h) में क्रमबद्ध करें। किसी अन्य फ़ाइल पर किसी भी रूक को रखने से पहले रूक द्वारा खाली की गई फ़ाइल में दूसरी फ़ाइल पर कब्जा करने वाले रूक को स्थानांतरित करना सम्मिलित होगा। उदाहरण के लिए, यदि रूक a1 को "b" फाइल में ले जाया जाता है, तो रूक b2 को "a" फाइल में स्थानांतरित किया जाना चाहिए, और अब वे रूक b1 और रूक a2 बन जाएंगे। नया अनुक्रम बन जाएगा (b, a, c, d, e, f, g, h)। कॉम्बिनेटरिक्स में, इस ऑपरेशन को क्रमचय कहा जाता है, और क्रमपरिवर्तन के परिणामस्वरूप प्राप्त अनुक्रम दिए गए अनुक्रम के क्रमपरिवर्तन हैं। 8 तत्वों के अनुक्रम से 8 तत्वों वाले क्रमचय की कुल संख्या 8 है! (8 का भाज्य)।
-लगाए गए सीमा के प्रभाव का आकलन करने के लिए रुक्सों को एक दूसरे पर हमला नहीं करना चाहिए, इस तरह की सीमा के बिना समस्या पर विचार करें। 8 × 8 शतरंज की बिसात पर आठरूक कितने प्रकार से रखे जा सकते हैं? यह 64 चौकों पर 8 रुक्सों के [[संयोजन]]ों की कुल संख्या होगी:
+लगाए गए सीमा के प्रभाव का आकलन करने के लिए रुक्सों को एक दूसरे पर हमला नहीं करना चाहिए, इस तरह की सीमा के बिना समस्या पर विचार करें। 8 × 8 शतरंज की बिसात पर आठ रूक कितने प्रकार से रखे जा सकते हैं? यह 64 चौकों पर 8 रुक्सों के [[संयोजन]]ों की कुल संख्या होगी:
 :<math> {64 \choose 8} = \frac{64!}{8!(64-8)!} = 4,426,165,368.</math>
@@ Line 85: / Line 85: @@
 मानव गतिविधि के विभिन्न क्षेत्रों से कई समस्याओं को एक रूक फॉर्मूलेशन देकर रूक समस्या में कम किया जा सकता है। एक उदाहरण के रूप में: एक कंपनी को अलग-अलग नौकरियों पर  श्रमिकों को नियुक्त करना चाहिए और प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाना चाहिए। यह नियुक्ति कितने तरीकों से की जा सकती है?
-अगर हम कार्यकर्ताओं को n× n शतरंज की बिसात पर, और नौकरियों को - फाइलों पर रखें। यदि कार्यकर्ता i को जॉब j पर नियुक्त किया जाता है, तो उस वर्ग पर एकरूक रखा जाता है जहाँ रैंक i फ़ाइल j को पार करता है। चूँकि प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाता है और प्रत्येक कार्यकर्ता को केवल एक ही कार्य के लिए नियुक्त किया जाता है, बोर्ड पर n रुक्सों की व्यवस्था के परिणामस्वरूप सभी फाइलों और रैंकों में केवल एक रूक होगा, यानी रूक हमला नहीं करते हैं एक-दूसरे से।
+अगर हम कार्यकर्ताओं को n× n शतरंज की बिसात पर, और नौकरियों को - फाइलों पर रखें। यदि कार्यकर्ता i को जॉब j पर नियुक्त किया जाता है, तो उस वर्ग पर एक रूक रखा जाता है जहाँ रैंक i फ़ाइल j को पार करता है। चूँकि प्रत्येक कार्य केवल एक कार्यकर्ता द्वारा किया जाता है और प्रत्येक कार्यकर्ता को केवल एक ही कार्य के लिए नियुक्त किया जाता है, बोर्ड पर n रुक्सों की व्यवस्था के परिणामस्वरूप सभी फाइलों और रैंकों में केवल एक रूक होगा, यानी रूक हमला नहीं करते हैं एक-दूसरे से।
 === रूक बहुपद रूक समस्या के सामान्यीकरण के रूप में ===
@@ Line 106: / Line 106: @@
 :<math>\binom{mn}{k} = \frac{(mn)!}{k! (mn-k)!}</math> तरीकों सेl
-यदि k  रूक एक दूसरे से किसी तरह से भिन्न हैं, उदाहरण के लिए, उन्हें लेबल या क्रमांकित किया गया है, तो अब तक प्राप्त सभी परिणामों को k!, k रुक्स के क्रमपरिवर्तन की संख्या से गुणा किया जाना चाहिए।
+यदि k रूक एक दूसरे से किसी तरह से भिन्न हैं, उदाहरण के लिए, उन्हें लेबल या क्रमांकित किया गया है, तो अब तक प्राप्त सभी परिणामों को k!, k रुक्स के क्रमपरिवर्तन की संख्या से गुणा किया जाना चाहिए।
 === सममित व्यवस्था ===
@@ Line 123: / Line 123: @@
 |  |  |  |  |  |  |rd|
 | '''आकृति। 2. ''8 × 8 शतरंज की बिसात के केंद्र के बारे में गैर-हमलावर बदमाशों की एक सममित व्यवस्था। डॉट्स 4 केंद्रीय वर्गों को चिह्नित करते हैं जो समरूपता के केंद्र को घेरते हैं।}}
-उन व्यवस्थाओं में सबसे सरल तब होती है जब रूक बोर्ड के केंद्र के बारे में सममित होते हैं। अगर हम G<sub>n</sub> के साथ नामित करें व्यवस्थाओं की संख्या जिसमें n रुक्सों को n रैंकों और n फ़ाइलों वाले बोर्ड पर रखा जाता है। अब हम बोर्ड को 2n रैंक और 2n फाइल रखने के लिए बनाते हैं। पहली फ़ाइल पर रुक्सों को उस फ़ाइल के किसी भी 2n एर्ग पर रखा जा सकता है। समरूपता की स्थिति के अनुसार, इस रूक का स्थान उस रूक के स्थान को परिभाषित करता है जो अंतिम फ़ाइल पर खड़ा होता है - इसे बोर्ड केंद्र के बारे में पहले रूक के लिए सममित रूप से व्यवस्थित किया जाना चाहिए। अगर हम पहली और आखिरी फाइलों और रैंकों को हटा दें जो कि रुक्सों के कब्जे में हैं (चूंकि रैंकों की संख्या सम है, हटाए गए रूक एक ही रैंक पर खड़े नहीं हो सकते हैं)। यह 2n−2 फ़ाइलों और 2n−2 रैंकों का एक बोर्ड देगा। यह स्पष्ट है कि नए बोर्ड पर रुक्सों की प्रत्येक सममित व्यवस्था मूल बोर्ड पर रुक्सों की सममित व्यवस्था से मेल खाती है। इसलिए, ''G''<sub>2''n''</sub> = 2''nG''<sub>2''n'' − 2</sub> (इस अभिव्यक्ति में कारक 2n पहली फाइल पर 2n वर्गों में से किसी पर कब्जा करने के लिए पहली रूक की संभावना से आता है)। उपरोक्त सूत्र को दोहराने से एक 2 × 2 बोर्ड के मामले तक पहुंचता है, जिस पर 2 सममित व्यवस्थाएं (विकर्णों पर) होती हैं। इस पुनरावृत्ति के परिणामस्वरूप, अंतिम अभिव्यक्ति G<sub>2n</sub>= 2<sup>n</sup>n! सामान्य शतरंज की बिसात (8 × 8) के लिए, G<sub>8</sub> = 2<sup>4</sup> × 4! = 16 × 24 = 384 8रूक की केंद्रीय सममित व्यवस्था है। ऐसी ही एक व्यवस्था चित्र 2 में दिखाई गई है।
+उन व्यवस्थाओं में सबसे सरल तब होती है जब रूक बोर्ड के केंद्र के बारे में सममित होते हैं। अगर हम G<sub>n</sub> के साथ नामित करें व्यवस्थाओं की संख्या जिसमें n रुक्सों को n रैंकों और n फ़ाइलों वाले बोर्ड पर रखा जाता है। अब हम बोर्ड को 2n रैंक और 2n फाइल रखने के लिए बनाते हैं। पहली फ़ाइल पर रुक्सों को उस फ़ाइल के किसी भी 2n एर्ग पर रखा जा सकता है। समरूपता की स्थिति के अनुसार, इस रूक का स्थान उस रूक के स्थान को परिभाषित करता है जो अंतिम फ़ाइल पर खड़ा होता है - इसे बोर्ड केंद्र के बारे में पहले रूक के लिए सममित रूप से व्यवस्थित किया जाना चाहिए। अगर हम पहली और आखिरी फाइलों और रैंकों को हटा दें जो कि रुक्सों के कब्जे में हैं (चूंकि रैंकों की संख्या सम है, हटाए गए रूक एक ही रैंक पर खड़े नहीं हो सकते हैं)। यह 2n−2 फ़ाइलों और 2n−2 रैंकों का एक बोर्ड देगा। यह स्पष्ट है कि नए बोर्ड पर रुक्सों की प्रत्येक सममित व्यवस्था मूल बोर्ड पर रुक्सों की सममित व्यवस्था से मेल खाती है। इसलिए, ''G''<sub>2''n''</sub> = 2''nG''<sub>2''n'' − 2</sub> (इस अभिव्यक्ति में कारक 2n पहली फाइल पर 2n वर्गों में से किसी पर कब्जा करने के लिए पहली रूक की संभावना से आता है)। उपरोक्त सूत्र को दोहराने से एक 2 × 2 बोर्ड के मामले तक पहुंचता है, जिस पर 2 सममित व्यवस्थाएं (विकर्णों पर) होती हैं। इस पुनरावृत्ति के परिणामस्वरूप, अंतिम अभिव्यक्ति G<sub>2n</sub>= 2<sup>n</sup>n! सामान्य शतरंज की बिसात (8 × 8) के लिए, G<sub>8</sub> = 2<sup>4</sup> × 4! = 16 × 24 = 384 8 रूक की केंद्रीय सममित व्यवस्था है। ऐसी ही एक व्यवस्था चित्र 2 में दिखाई गई है।
 विषम-आकार के बोर्डों के लिए (जिसमें 2n+ 1 रैंक और 2n+ 1 फ़ाइलें होती हैं) हमेशा एक ऐसा वर्ग होता है जिसका सममित दोहरा नहीं होता है - यह बोर्ड का केंद्रीय वर्ग होता है। इस चौक पर हमेशा एक रूक रखा होना चाहिए। केंद्रीय फ़ाइल और रैंक को हटाने से, ''2n× 2n'' बोर्ड पर 2n रुक्सों की एक सममित व्यवस्था प्राप्त होती है। इसलिए ऐसे बोर्ड के लिए एक बार फिर ''G''<sub>2''n'' + 1</sub> = ''G''<sub>2''n''</sub> = 2<sup>''n''</sup>''n''!.
-थोड़ी अधिक जटिल समस्या गैर-आक्रमणकारी व्यवस्थाओं की संख्या का पता लगाना है जो बोर्ड के 90 डिग्री रोटेशन पर नहीं बदलती हैं। बता दें कि बोर्ड में 4n फाइलें और 4n रैंक हैं, और रुक्सों की संख्या भी 4n है। इस स्थिति में, पहली फ़ाइल पर मौजूद रूक इस फ़ाइल पर किसी भी वर्ग पर कब्जा कर सकता है, कोने के वर्गों को छोड़कर (एकरूक कोने के वर्ग पर नहीं हो सकता है क्योंकि 90 डिग्री रोटेशन के बाद 2 रूक एक दूसरे पर हमला करेंगे)। वहाँ अन्य 3 रूक हैं जो उसरूक से मेल खाते हैं और वे क्रमशः अंतिम रैंक, अंतिम फ़ाइल और पहली रैंक पर खड़े होते हैं (वे पहले रूक से 90°, 180°, और 270° रोटेशन द्वारा प्राप्त किए जाते हैं)। उन रुक्सों की फाइलों और रैंकों को हटाकर, आवश्यक समरूपता के साथ एक (4n− 4) × (4n− 4) बोर्ड के लिए रुक्सों की व्यवस्था प्राप्त करता है। इस प्रकार, निम्नलिखित [[पुनरावृत्ति संबंध]] प्राप्त होता है: ''R''<sub>4''n''</sub> = (4''n'' − 2)''R''<sub>4''n'' − 4</sub>, जहां  ''R<sub>n</sub>'' बोर्ड के लिए व्यवस्थाओं की संख्या है। पुनरावृत्ति, यह इस प्रकार है कि ''R<sub>n</sub>''= 2''n''(2''n'' − 1)(2''n'' − 3)...1. एक (4n+ 1) × (4n+ 1) बोर्ड के लिए व्यवस्थाओं की संख्या वही है जो 4n× 4n बोर्ड की है; ऐसा इसलिए है क्योंकि (4n+ 1) × (4n+ 1) बोर्ड पर, एक रूक को आवश्यक रूप से केंद्र में खड़ा होना चाहिए और इस प्रकार केंद्रीय रैंक और फ़ाइल को हटाया जा सकता है। इसलिए ''R''<sub>4''n'' + 1</sub> = ''R''<sub>4''n''</sub>. पारंपरिक शतरंज की बिसात (n= 2) के लिए, R<sub>8</sub> = 4 × 3 × 1 = घूर्णी समरूपता के साथ 12 संभावित व्यवस्थाएँ।
+थोड़ी अधिक जटिल समस्या गैर-आक्रमणकारी व्यवस्थाओं की संख्या का पता लगाना है जो बोर्ड के 90 डिग्री रोटेशन पर नहीं बदलती हैं। बता दें कि बोर्ड में 4n फाइलें और 4n रैंक हैं, और रुक्सों की संख्या भी 4n है। इस स्थिति में, पहली फ़ाइल पर उपस्थित रूक इस फ़ाइल पर किसी भी वर्ग पर कब्जा कर सकता है, कोने के वर्गों को छोड़कर (एकरूक कोने के वर्ग पर नहीं हो सकता है क्योंकि 90 डिग्री रोटेशन के बाद 2 रूक एक दूसरे पर हमला करेंगे)। वहाँ अन्य 3 रूक हैं जो उस रूक से मेल खाते हैं और वे क्रमशः अंतिम रैंक, अंतिम फ़ाइल और पहली रैंक पर खड़े होते हैं (वे पहले रूक से 90°, 180°, और 270° रोटेशन द्वारा प्राप्त किए जाते हैं)। उन रुक्सों की फाइलों और रैंकों को हटाकर, आवश्यक समरूपता के साथ एक (4n− 4) × (4n− 4) बोर्ड के लिए रुक्सों की व्यवस्था प्राप्त करता है। इस प्रकार, निम्नलिखित [[पुनरावृत्ति संबंध]] प्राप्त होता है: ''R''<sub>4''n''</sub> = (4''n'' − 2)''R''<sub>4''n'' − 4</sub>, जहां  ''R<sub>n</sub>'' बोर्ड के लिए व्यवस्थाओं की संख्या है। पुनरावृत्ति, यह इस प्रकार है कि ''R<sub>n</sub>''= 2''n''(2''n'' − 1)(2''n'' − 3)...1. एक (4n+ 1) × (4n+ 1) बोर्ड के लिए व्यवस्थाओं की संख्या वही है जो 4n× 4n बोर्ड की है; ऐसा इसलिए है क्योंकि (4n+ 1) × (4n+ 1) बोर्ड पर, एक रूक को आवश्यक रूप से केंद्र में खड़ा होना चाहिए और इस प्रकार केंद्रीय रैंक और फ़ाइल को हटाया जा सकता है। इसलिए ''R''<sub>4''n'' + 1</sub> = ''R''<sub>4''n''</sub>. पारंपरिक शतरंज की बिसात (n= 2) के लिए, R<sub>8</sub> = 4 × 3 × 1 = घूर्णी समरूपता के साथ 12 संभावित व्यवस्थाएँ।
-(4''n'' + 2) × (4''n'' + 2) and (4''n'' + 3) × (4''n'' + 3) बोर्डों के लिए, समाधान की संख्या शून्य है। प्रत्येकरूक के लिए दो स्थितियाँ संभव हैं: या तो वह बीच में खड़ा हो या वह बीच में न खड़ा हो। दूसरे मामले में, यह रूक उस चौकड़ी में सम्मिलित है जो बोर्ड को 90° पर मोड़ने पर वर्गों का आदान-प्रदान करती है। इसलिए, रुक्सों की कुल संख्या या तो 4n होनी चाहिए (जब बोर्ड पर कोई केंद्रीय वर्ग न हो) या 4n+ 1। यह साबित करता है कि ''R''<sub>4''n'' + 2</sub> = ''R''<sub>4''n'' + 3</sub> = 0.
+(4''n'' + 2) × (4''n'' + 2) and (4''n'' + 3) × (4''n'' + 3) बोर्डों के लिए, समाधान की संख्या शून्य है। प्रत्येक रूक के लिए दो स्थितियाँ संभव हैं: या तो वह बीच में खड़ा हो या वह बीच में न खड़ा हो। दूसरे मामले में, यह रूक उस चौकड़ी में सम्मिलित है जो बोर्ड को 90° पर मोड़ने पर वर्गों का आदान-प्रदान करती है। इसलिए, रुक्सों की कुल संख्या या तो 4n होनी चाहिए (जब बोर्ड पर कोई केंद्रीय वर्ग न हो) या 4n+ 1। यह साबित करता है कि ''R''<sub>4''n'' + 2</sub> = ''R''<sub>4''n'' + 3</sub> = 0.
-एक n × n बोर्ड पर विकर्णों में से किसी एक विकर्ण (निर्धारणता के लिए, शतरंज की बिसात पर a1–h8 के संगत विकर्ण) के सममित n गैर-हमलावर रुक्सों की व्यवस्था की संख्या पुनरावृत्ति Q द्वारा परिभाषित [[टेलीफोन नंबर (गणित)]] द्वारा दी गई है ''Q<sub>n</sub>'' = ''Q<sub>n</sub>'' <sub>− 1</sub> + (''n'' − 1)''Q<sub>n</sub>'' <sub>− 2</sub>. यह पुनरावृत्ति निम्न प्रकार से प्राप्त होती है। ध्यान दें कि पहली फ़ाइल पर रुक्सों या तो निचले कोने के वर्ग पर खड़ा होता है या यह दूसरे वर्ग पर खड़ा होता है। पहले मामले में, पहली फ़ाइल और पहली रैंक को हटाने से एक (n− 1) × (n− 1) बोर्ड पर सममित व्यवस्था n− 1 रूक हो जाती है। ऐसी व्यवस्थाओं की संख्या ''Q<sub>n</sub>'' <sub>− 1</sub> है. दूसरे मामले में, मूल रुक्सों के लिए एक और रुक्सों है, जो चुने हुए विकर्ण के बारे में पहले वाले के लिए सममित है। उन रुक्सों की फाइलों और रैंकों को हटाने से n − 2रूक एक (n− 2) × (n− 2) बोर्ड पर एक सममित व्यवस्था की ओर जाता है। चूँकि ऐसी व्यवस्थाओं की संख्या ''Q<sub>n</sub>'' <sub>− 2</sub> है और रूक को पहली फ़ाइल के n− 1 वर्ग पर रखा जा सकता है, वहाँ (n− 1)''Q<sub>n</sub>'' <sub>− 2</sub> हैंl ऐसा करने के तरीके, जो उपरोक्त पुनरावृत्ति को तुरंत देते हैं। विकर्ण-सममित व्यवस्था की संख्या तब अभिव्यक्ति द्वारा दी जाती है:
+एक n × n बोर्ड पर विकर्णों में से किसी एक विकर्ण (निर्धारणता के लिए, शतरंज की बिसात पर a1–h8 के संगत विकर्ण) के सममित n गैर-हमलावर रुक्सों की व्यवस्था की संख्या पुनरावृत्ति Q द्वारा परिभाषित [[टेलीफोन नंबर (गणित)]] द्वारा दी गई है ''Q<sub>n</sub>'' = ''Q<sub>n</sub>'' <sub>− 1</sub> + (''n'' − 1)''Q<sub>n</sub>'' <sub>− 2</sub>. यह पुनरावृत्ति निम्न प्रकार से प्राप्त होती है। ध्यान दें कि पहली फ़ाइल पर रुक्सों या तो निचले कोने के वर्ग पर खड़ा होता है या यह दूसरे वर्ग पर खड़ा होता है। पहले मामले में, पहली फ़ाइल और पहली रैंक को हटाने से एक (n− 1) × (n− 1) बोर्ड पर सममित व्यवस्था n− 1 रूक हो जाती है। ऐसी व्यवस्थाओं की संख्या ''Q<sub>n</sub>'' <sub>− 1</sub> है. दूसरे मामले में, मूल रुक्सों के लिए एक और रुक्सों है, जो चुने हुए विकर्ण के बारे में पहले वाले के लिए सममित है। उन रुक्सों की फाइलों और रैंकों को हटाने से n − 2 रूक एक (n− 2) × (n− 2) बोर्ड पर एक सममित व्यवस्था की ओर जाता है। चूँकि ऐसी व्यवस्थाओं की संख्या ''Q<sub>n</sub>'' <sub>− 2</sub> है और रूक को पहली फ़ाइल के n− 1 वर्ग पर रखा जा सकता है, वहाँ (n− 1)''Q<sub>n</sub>'' <sub>− 2</sub> हैंl ऐसा करने के तरीके, जो उपरोक्त पुनरावृत्ति को तुरंत देते हैं। विकर्ण-सममित व्यवस्था की संख्या तब अभिव्यक्ति द्वारा दी जाती है:
 :
@@ Line 143: / Line 143: @@
 <references />
-{{DEFAULTSORT:Rook Polynomial}}[[Category: कार्यों का निर्माण]] [[Category: गणनात्मक कॉम्बिनेटरिक्स]] [[Category: बहुपदों]] [[Category: गणितीय शतरंज की समस्याएं]] [[Category: क्रमगुणित और द्विपद विषय]] [[Category: क्रमपरिवर्तन]] [[Category: ऑर्थोगोनल बहुपद]]
+{{DEFAULTSORT:Rook Polynomial}}
+[[Category:Created On 03/03/2023|Rook Polynomial]]
+[[Category:Machine Translated Page|Rook Polynomial]]
-[[Category: Machine Translated Page]]
+[[Category:Templates Vigyan Ready|Rook Polynomial]]
-[[Category:Created On 03/03/2023]]
+[[Category:ऑर्थोगोनल बहुपद|Rook Polynomial]]
+[[Category:कार्यों का निर्माण|Rook Polynomial]]
+[[Category:क्रमगुणित और द्विपद विषय|Rook Polynomial]]
+[[Category:क्रमपरिवर्तन|Rook Polynomial]]
+[[Category:गणनात्मक कॉम्बिनेटरिक्स|Rook Polynomial]]
+[[Category:गणितीय शतरंज की समस्याएं|Rook Polynomial]]
+[[Category:बहुपदों|Rook Polynomial]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 14:40, 29 August 2023

Contents