रूक बहुपद

	a	b	c	d	e	f	g	h
8	File:Chessboard480.svg d8 black rook a7 black rook h6 black rook c5 black rook f4 black rook b3 black rook e2 black rook g1 black rook								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 के वर्गों में व्यवस्थित किया जा सकता है। रूक इस तरह से व्यवस्थित होते हैं कि एक ही पंक्ति या स्तंभ में रुक्सों की कोई जोड़ी नहीं होती है। इस अर्थ में, व्यवस्था एक स्थिर, अचल बोर्ड पर रुक्सों की स्थिति है; वर्गों को स्थिर रखते हुए बोर्ड को घुमाने या प्रतिबिंबित करने पर व्यवस्था अलग नहीं होगी। बहुपद भी वही रहता है यदि रोव्स को आपस में बदल दिया जाता है या कॉलम को आपस में बदल दिया जाता है।

"रूक बहुपद" शब्द जॉन रिओर्डन (गणितज्ञ) द्वारा गढ़ा गया था।शतरंज से नाम की व्युत्पत्ति के बावजूद, रूक बहुपदों का अध्ययन करने के लिए प्रेरणा प्रतिबंधित पदों के साथ गणना क्रम परिवर्तन (या आंशिक क्रमपरिवर्तन) के साथ उनका संबंध है। बोर्ड 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)$).

पूर्ण बोर्ड

आयताकार m × n बोर्डों के लिए B_m,n, हम R_m,n := R_Bm,n लिखते हैंl और यदि m = n, R_{n:=  Rm,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 रुक्स के गैर-हमलावर प्लेसमेंट की संख्या को देखते हुए याद करते हैं: ये संख्याएँ असमान हैं, अर्थात, वे अधिकतम तक बढ़ती हैं और फिर घटती हैं। यह हेइलमैन और लिब के प्रमेय से (एक मानक तर्क द्वारा) अनुसरण करता है एक मेल खाने वाले बहुपद के शून्यों के बारे में (उससे भिन्न जो एक रूक बहुपद से संबंधित है, लेकिन चर के परिवर्तन के तहत इसके बराबर है), जिसका अर्थ है कि एक रूक बहुपद के सभी शून्य ऋणात्मक वास्तविक संख्याएं हैं।

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

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

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

रूक की समस्या

	a	b	c	d	e	f	g	h
8	File:Chessboard480.svg h8 black rook g7 black rook h7 black circle f6 black rook g6 black circle h6 black circle e5 black rook f5 black circle g5 black circle h5 black circle d4 black rook e4 black circle f4 black circle g4 black circle h4 black circle c3 black rook d3 black circle e3 black circle f3 black circle g3 black circle h3 black circle b2 black rook c2 black circle d2 black circle e2 black circle f2 black circle g2 black circle h2 black circle a1 black rook b1 black circle c1 black circle d1 black circle e1 black circle f1 black circle g1 black circle h1 black circle								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.

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

एक ही परिणाम थोड़े अलग तरीके से प्राप्त किया जा सकता है। अगर हम प्रत्येक रूक को उसके रैंक की संख्या के अनुरूप एक स्थितीय संख्या दें, और उसे एक नाम दें जो उसकी फ़ाइल के नाम से मेल खाता हो। इस प्रकार, रूक 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 का कारक है।

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

अगर हम का