موضوع مقاله: چند جمله‌ای رخی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # چند جمله‌ای رخی | مقدمه: در ترکیبییات ریاضیات، چند جمله ای رخی، یک چند جمله ای تولیدی از تعداد حالت‌های قرار دادن تعدادی رخ بر روی صفحه ای است شبیه یک صفحه شطرنجی می‌باشد؛ یعنی هیچ دو رخی در یک ردیف یا ستون نباشند. | ## بخش 1: چند جمله‌ای رخی | تخته زیر مجموعه خانه‌های (مربع‌های ۱ در ۱) یک صفحه شطرنجی مستطیل شکل با m ردیف و n ستون است که بتوان روی آنها یک رخ قرار داد. تخته یک صفحه شطرنج معمولی است اگر همه خانه‌ها مجاز باشند و m = n = ۸ و یک صفحه شطرنج با اندازه دلخواه است اگر همه خانه‌ها مجاز باشد و m = n. ضریب xk در چند جمله ای رخی RB(x) تعداد راه‌هایی است که k رخ، به طوری که هیچ‌یک از آنها به دیگری حمله نکند، می‌توانند در خانه‌های مجموعه B مرتب شوند. اگر صفحه در هنگام ثابت ماندن خانه‌ها چرخانده شود یا منعکس شود، ترتیب متفاوت نخواهد بود. اگر ردیف‌ها عوض شوند یا ستون‌ها عوض شوند، چند جمله ای به همان صورت باقی می‌ماند. با اینکه این نام از شطرنج آمده‌است، انگیزه مطالعه چند جمله ای‌های رخی ارتباط آنها با شمارش جایگشت‌ها (یا جایگشت‌های جزئی) با موقعیت‌های محدود است. صفحه B که زیر مجموعه ای از صفحه شطرنجی n × n است، مربوط به جایگشت n شیء، که ممکن است ما آن را نسبت دهیم به اعداد ۱، ۲، …، n را، به طوری که عدد aj در موقعیت Jام جایگشت باید شماره ستون یک خانه مجاز در ردیف j از B باشد. توجه به جایگذاری رخ از ترکیبیات خالص و کاربردی، نظریه گروه، نظریه اعداد و فیزیک آماری منشأ می‌گیرد. ارزش چند جمله ای‌های رخی از کاربرد رویکرد تابع مولد ناشی می‌شود و همچنین از این واقعیت که ریشه‌های چند جمله ای رخی یک صفحه اطلاعات ارزشمندی در مورد ضرایب آن، یعنی تعداد حالت‌های چیدن k رخ غیر حمله ای، ارائه می‌دهند. تعریف چند جمله ای رخی RB(x) یک صفحه B ،تابع مولد برای تعداد آرایش‌های زخ‌های غیر حمله ای است: که r k تعداد روشهای قرار دادن k رخ غیرتهاجمی روی صفحه ای با m ردیف و n ستون است. صفحه‌های کامل چند چند جمله ای رخی اول در صفحه‌های مربعی n × n (با Rn = RB) به این شکل است: این بدان معنی است که در صفحهٔ ۱×۱، ۱ رخ را می‌توان به ۱ طریق چیدمان کرد، و صفر رخ را نیز می‌توان به ۱ طریق مرتب کرد (صفحه خالی). در صفحه کامل۲×۲، ۲ رخ را می‌توان به ۲ روش (روی قطرها) ترتیب داد، ۱ رخ را می‌توان به ۴ روش مرتب کرد و صفر رخ را می‌توان به ۱ طریق مرتب کرد. چند جمله ای رخ در یک صفحه شطرنج مستطیلی ارتباط نزدیکی به تعمیم لاگر چند جمله ای LNα(x) با اتحاد زیر دارد. چند جمله ای‌های تطبیقی چند جمله ای رخ حالت خاصی از یک نوع از چند جمله ای تطبیق است که تابع مولد تعداد تطابق k-یالی در یک گراف می‌باشد. چند جمله ای رخی یک صفحه دلخواه B به طوری که B ⊆ B m, n متناظر به گراف دو بخشی با رئوس چپ v 1، v 2، …، v m و رئوس راست w 1، w 2، …، w n است و یال viwj وجود دارد اگر و تنها اگر خانه (i ,j) متعلق به B باشد؛ بنابراین، نظزیه چند جمله ای‌های رخی، به تعبیری، در نظریه چند جمله ای‌های تطبیقی موجود است. ما یک نکته مهم را در مورد ضرایب rk استنباط می‌کنیم، که یادآوری می‌کنیم با توجه به تعداد حالت‌های قرارگیری‌های k رخ غیر تهاجمی در B: این اعداد تک‌مُدی هستند، یعنی تا کرانی افزایش می‌یابند و سپس کاهش می‌یابند. در مورد صفرهای یک چند جمله ای منطبق (متفاوت از آنچه مربوط به چند جمله ای رخی است، اما معادل آن با تغییر متغیرها) بدست می‌آید، که به این معنی است که تمام صفرهای چند جمله ای رخی اعداد حقیقی منفی هستند. اتصال به ماتریس دائمی برای صفحات مربعی n×n ناقص، (به عنوان مثال رخ‌ها در برخی از زیرمجموعه‌های دلخواه خانه‌های صفحه مجاز نیست) محاسبه تعداد راه‌های قرار دادن n رخ در صفحه برابر است با محاسبه ثابت ماتریس باینری (۰و ۱). سؤالی که مطرح می‌شود این است: "به چند حالت می‌توان هشت رخ را روی صفحه شطرنج ۸ × ۸ قرار داد تا هیچ یک از آنها دیگری را تهدید نکد؟" پاسخ این است: "بدیهی است که در هر ردیف و هر ستون باید یک رخ وجود داشته باشد. با شروع از ردیف پایین، مشخص است که اولین رخ را می‌توان روی هر یک از هشت خانه مختلف قرار داد (شکل ۱). سپس شش خانه برای انتخاب ردیف سوم، پنج خانه برای ردیف چهارم و غیره وجود دارد؛ بنابراین تعداد راه‌های مختلف باید ۸ × ۷ × ۶ × ۵ × ۴ × ۳ × ۲ × ۱ = ۴۰٬۳۲۰ باشد. بیایید هر رخ را با یک عدد متناسب با موقعیتش، برابر با شماره ردیف آن، تطبیق دهیم و همچنین یک نام متناسب با نام ستون آن به آن اختصاص دهیم؛ بنابراین، رخ a1 دارای موقعیت ۱ و نام "a" می‌باشد؛ همچنین رخ b2 دارای موقعیت ۲ و نام "b" می‌باشد و غیره. سپس اجازه دهید رخ‌ها را با توجه به موقعیت آنها به یک لیست مرتب (دنباله) ترتیب دهیم. قرار دادن هر رخ بر روی ستون دیگری نیاز به جابجایی رخی که تا آن زمان آن ستون دوم را اشغال کرده بود، به ستون اول تخلیه شده‌است. | ## بخش 2: چند جمله‌ای رخی | به عنوان مثال، اگر رخ a1 به ستون "b" منتقل شود، رخ b2 باید به ستون "a" منتقل شود، و اکنون آنها رخ b1 و رخ a2 می‌شوند. در ترکیبیات، این عملیات را جایگشت می‌نامند و دنباله‌هایی که در نتیجه جایگشت بدست می‌آیند، جایگشت‌های دنباله داده شده هستند. برای ارزیابی تأثیر محدودیت تحمیل شده «رخ‌ها نباید همدیگر را تهدید کنند»، مسئله را بدون چنین محدودیتی در نظر بگیرید. این تعداد کل ترکیب ۸ رخ در ۶۴ خانه خواهد بود: بنابراین، محدودیت «رخ نباید همدیگر را تهدید کنند» تعداد کل موقعیت‌های مجاز را از ترکیب به جایگشت‌ها کاهش می‌دهد که ضریب حدوداً برابر ۱۰۹٬۷۷۶ است. تعدادی از مسائل از حوزه‌های مختلف فعالیت‌های انسانی را می‌توان با دادن «فرمول رخی» به مشکل رخ ساده کرد. به عنوان مثال: یک شرکت باید n کارمند در n شغل مختلف استخدام کند و هر شغل باید فقط توسط یک کارمند انجام شود. بیایید ما کارمندان را در ردیف‌های یک صفحه شطرنج n×n قرار دهیم، و مشاغل را روی ستون‌ها. اگر کارمند i به شغل j منصوب شود، یک رخ در خانه ای قرار می‌گیرد که بر روی ردیف i و ستون j باشد. از آنجا که هر شغل فقط توسط یک کارمند انجام می‌شود و هر کارمند فقط به یک شغل منصوب می‌شود، در نتیجه آرایش n رخ روی تخته، کلیه ستون‌ها و ردیف‌ها فقط شامل یک رخ خواهند بود، یعنی رخ‌ها همدیگر را تهدید نمی‌کنند. چند جمله ای رخی به عنوان تعمیم مسئله رخی مسئله کلاسیک رخ‌ها درجا به ما مقدار r 8 را می‌دهد. بیایید این مسئله را با در نظر گرفتن یک صفحه m × n، یعنی یک صفحه شطرنجی با m ردیف و n ستون تعمیم دهیم. مسئله به این صورت است: از چند طریق می‌توان k رخ را را بر روی صفحه m × n به گونه ای مرتب کرد که یکدیگر را تهدید نکنند؟ واضح است که برای آنکه مسئله قابل حل باشد، k باید کمتر یا مساوی مینیمم m و n باشد. در غیر این صورت نمی‌توان از قرار دادن یک جفت رخ در ردیف یا ستون یکسان جلوگیری کرد. از آنجا که تعداد ردیف‌ها m است، k باید از بین آنها انتخاب شود، می‌توان این انتخاب را در روش انجام داد. به همین ترتیب، مجموعه k ستون‌هایی که می‌توان رخ‌ها را در آن قرار داد، انتخاب می‌شود به روش. با توجه به قانون ضرب، از آنجا که انتخاب ستون‌ها به انتخاب ردیف‌ها بستگی ندارد حالت برای انتخاب خانه‌هایی که رخ‌ها در آن چیده شوند وجود دارد. با این حال، کار هنوز به پایان نرسیده‌است زیرا این k ردیف و k ستون در k 2 خانه تلاقی دارند. با حذف ردیف‌ها و ستون‌های بلااستفاده و چسباندن ردیف‌ها و ستون‌های باقیمانده با هم، یک صفحه جدید از k ردیف و k ستون بدست می‌آید. قبلاً نشان داده شده بود که در چنین صفحه ای می توان k رخ را به !k حالت آرایش داد (به طوری که همدیگر را تهدید نکنند). به عنوان یک مثال، ۳ رخ را در یک صفحه شطرنج معمولی (۸ × ۸) به حالت می‌توان قرار داد. برای k = m = n، فرمول فوق !rk = n را نتیجه می‌دهد که متناظر با نتیجه به دست آمده برای مسئله کلاسیک رخ می‌باشد. حال چند جمله ای رخی با ضرایب صریح به شکل زیر است: اگر محدودیت «رخ‌ها نباید همدیگر را تهدید کنند» حذف شود، باید انتخاب هر k خانه از m×n خانه را محاسبه کرد. اگر k رخ‌ها به طریقی با یکدیگر متفاوت باشند، به عنوان مثال، آنها دارای برچسب یا شماره گذاری شده باشند، عدد بدست آمده تاکنون را باید در !k ضرب کرد، که !k تعداد جایگشت‌های k رخ است. | ## بخش 3: چند جمله‌ای رخی | آرایش‌های متقارن به عنوان یک عارضه دیگر برای مسئله رخ، اجازه دهید ما نه تنها رخ‌ها همدیگر را تهدید نکنند بلکه به‌طور متقارن روی صفحه قرار بگیرند را نیز لازم بدانیم. بیایید Gn تعداد روش‌هایی که n رخ روی صفحه ای با n ردیف و n ستون قرار می‌گیرند، تعیین کنیم. با توجه به شرایط تقارن، قرارگیری این رخ محل قرارگیری یک رخ را که روی آخرین ستون قرار دارد مشخص می‌کند - باید به‌طور قرینه با اولین رخ در حول مرکز صفحه چیده شود. اجازه دهید اولین و آخرین ستون‌ها و ردیف‌هایی که توسط رخ‌ها اشغال شده‌اند را حذف کنیم (از آنجا که تعداد ردیف‌ها زوج است، رخ‌های حذف شده نمی‌توانند در ردیف یکسان قرار گیرند). واضح است که برای هر چیدمان متقارن رخ‌های روی صفحه جدید متناظر به یک چیدمان متقارن رخ‌ها روی صفحه اصلی است؛ بنابراین، G 2n = 2nG 2 n-2 (ضریب 2n در این عبارت از این امکان به‌وجود می‌آید که اولین رخ هر یک از 2n خانه موجود در ستون اول را اشغال کند). با تکرار فرمول فوق می‌توان به حالت صفحه ۲×۲ رسید، که روی آن ۲ ترتیب متقارن (روی قطرها) وجود دارد. برای صفحه شطرنج معمول (8 × ۸)، G 8 = 24×۴ = 16×۲۴ = ۳۸۴ آرایش متقارن حول مرکز از ۸ رخ وجود دارد. برای تخته‌های با اندازه فرد (حاوی 2n+۱ ردیف و 2n+۱ ستون) همیشه یک خانه وجود دارد که خانه متقارن ندارد - این خانه مرکزی تخته است. حال با حذف ستون و ردیف مرکزی، یک آرایش متقارن 2n رخ بر روی صفحه 2n×2n بدست می‌آید. مسئله کمی پیچیده‌تر این است که تعداد آرایش‌های غیرتهاجمی را پیدا کنید که با چرخش ۹۰ درجه صفحه تغییر نمی‌کنند. در این حالت، رخی که روی ستون اول است می‌تواند هر مربع روی این ستون را اشغال کند، به غیر از خانه‌های گوشه ای (یک رخ نمی‌تواند در یک خانه گوشه ای باشد زیرا بعد از چرخش ۹۰ درجه، ۲ رخ وجود دارند که همدیگر را تهدید می‌کنند). ۳ رخ دیگر نیز وجود دارد که با آن رخ مطابقت دارد و آنها به ترتیب روی آخرین ردیف، آخرین ستون و ردیف اول قرار می‌گیرند (با چرخش ۹۰ درجه، ۱۸۰ درجه و ۲۷۰ درجه از اولین صخره بدست می‌آیند). با حذف ستون‌ها و ردیف‌های این رخ‌ها، چیدمان رخی برای یک صفحه (4n-۴)×(4n-۴) با تقارن مورد نیاز بدست می‌آید؛ بنابراین، رابطه بازگشتی زیر بدست می‌آید: R4n = (4n -2) R4n-4، که Rn تعداد آرایش‌ها روی صفحه n×n است. با تکرار، نتیجه می‌شود که R4n = 2n(2n−1 2n−۳)...۱ تعداد آرایش‌ها برای یک صفحهٔ (4n+1)×(4n+۱) برابر با آرایش‌ها برای صفحه 4n×4n می‌باشد؛ زیرا در صفحهٔ (4n+1)×(4n+۱)، یک رخ لزوماً باید در مرکز قرار گیرد و بنابراین می‌توان ردیف و ستون مرکزی را حذف کرد؛ بنابراین R4n+1 = R4n برای صفحه شطرنج معمولی (n = ۲)، R8 = 4×3×۱ = ۱۲ آرایش ممکن با تقارن چرخشی وجود دارد. در حالت ثانوی، این رخ در خانه رخی گنجانده شده‌است که با چرخاندن ۹۰ درجه صفحه بدست می‌آید؛ بنابراین، تعداد کل رخ‌ها باید 4n باشد (وقتی خانه مرکزی روی صفحه وجود ندارد) یا 4n+۱ باشد. تعداد چیدمان n رخ غیر تهاجمی متقارن نسبت به یکی از قطرها (برای تعیین قطر، قطر مربوط به a1-h8 در صفحه شطرنج) در صفحه n×n با شماره تلفن‌های مشخص می‌شود که با بازگشتی Qn = Qn−1 + (n−1)Qn−2 تعریف می‌شود. توجه داشته باشید که رخ موجود در ستون اول یا در خانه گوشه پایین قرار دارد یا در یک خانه دیگر قرار دارد. در حالت اول، حذف ستون اول و ردیف اول منجر به آرایش متقارن n-1 رخ بر روی یک صفحه (n−1)×(n−۱) می‌شود. در حالت دوم، برای رخ اصلی، یک رخ دیگر وجود دارد، متقارن با اولین رخ در حول قطر انتخاب شده. حذف ستون‌ها و ردیف‌های این رخ‌ها منجر به آرایش متقارن n رخ بر روی یک صفحه (n−2)×(n−۲) می‌شود. از آنجا که تعداد حالت‌های آرایش باقیمانده Qn−2 می‌باشد و خانه رخ اصلی را می‌توان به n-1 حالت انخاب کرد، در کل برای حالت دوم (n−1)Qn−2 روش آرایش وجود دارد. دقیقاً به همین ترتیب، می‌توان نشان داد که تعداد آرایش‌های n رخ در صفحه n×n، به گونه ای که آنها همدیگر را تهدید نکنند و متقارن با هر دو مورب باشند، توسط معادلات بازگشتی B2n = 2B2n−2 + (2n−2)B2n−4 and B2n+1 = B2n بدست می‌آیند. آرایش‌هایی که با کلاس‌های تقارن شمرده می‌شوند خالتی دیگر از تعمیم این است که در آن آرایش‌های رخی که با تقارن صفحه از یکدیگر به دست می‌آیند، یک بار حساب شوند. | ## جمع‌بندی | به عنوان مثال، اگر چرخش ۹۰ درجه ای صفحه به عنوان تقارن مجاز باشد، پس هر آرایشی که با چرخش ۹۰، ۱۸۰ یا ۲۷۰ درجه بدست آید، «همان» الگوی اصلی در نظر گرفته می‌شود، حتی اگر این آرایش‌ها در مسئله اولیه که صفحه ثابت است جداگانه شمارش شده باشند.