چندجمله‌ای رخی

در ترکیبییات ریاضیات، چند جمله‌ای رخی، یک چند جمله‌ای تولیدی از تعداد حالت‌های قرار دادن تعدادی رخ بر روی صفحه‌ای شبیه یک صفحه شطرنجی است؛ یعنی هیچ دو رخی در یک ردیف یا ستون نباشند. تختهٔ زیر مجموعه خانه‌های (مربع‌های ۱ در ۱) یک صفحه شطرنجی مستطیل‌شکل با m ردیف و n ستون است که بتوان روی آنها یک رخ قرار داد. تخته یک صفحه شطرنج معمولی است اگر همه خانه‌ها مجاز باشند و m = n = ۸ و یک صفحه شطرنج با اندازه دلخواه است اگر همه خانه‌ها مجاز باشد و m = n. ضریب xk در چند جمله‌ای رخی RB(x) تعداد راه‌هایی است که k رخ، به طوری که هیچ‌یک از آنها به دیگری حمله نکند، می‌توانند در خانه‌های مجموعه B مرتب شوند. چیدمان رخ‌ها به گونه‌ای است که هیچ جفت رخی در یک ردیف یا ستون نباشند. از این نظر، یک چیدمان عبارت است از قرارگیری صخره‌ها روی تخته ایستا و غیر متحرک. اگر صفحه در هنگام ثابت ماندن خانه‌ها چرخانده شود یا منعکس شود، ترتیب متفاوت نخواهد بود. اگر ردیف‌ها عوض شوند یا ستون‌ها عوض شوند، چند جمله‌ای به همان صورت باقی می‌ماند.

اصطلاح «چند جمله‌ای رخی» توسط جان ریوردان به‌وجود آمد. با اینکه این نام از شطرنج آمده‌است، انگیزه مطالعه چندجمله‌ای‌های رخی ارتباط آنها با شمارش جایگشت‌ها (یا جایگشت‌های جزئی) با موقعیت‌های محدود است. صفحه B که زیر مجموعه‌ای از صفحه شطرنجی n × n است، مربوط به جایگشت n شیء، که ممکن است ما آن را نسبت دهیم به اعداد ۱، ۲، …، n را، به طوری که عدد aj در موقعیت Jام جایگشت باید شماره ستون یک خانه مجاز در ردیف j از B باشد. مثالهای معروف شامل تعداد روشهای قرار دادن n رخ غیر حمله کننده (در یک ردیف یا ستون نباشند) در:
 یک صفحه n × n کامل، که یک مسئله ترکیبیاتی ابتدایی می‌باشد؛
 همان صفحه ولی خانه‌های قطر این صفحه مجاز نمی‌باشند؛ این مسئلهٔ پریش یا مسئلهٔ کلاه"hat-check problem" می‌باشد (این یک حالت خاصی از problème des rencontres می‌باشد)؛
 همان صفحه ولی خانه‌های قطر و خانه‌های دقیقاً یک خانه بالای آن و خانه پایین چپ صفحه مجاز نمی‌باشند. این یک بخش مهم در راه حل مسئله problème des rencontres می‌باشد.

توجه به جایگذاری رخ از ترکیبیات خالص و کاربردی، نظریه گروه، نظریه اعداد و فیزیک آماری منشأ می‌گیرد. ارزش چندجمله‌ای‌های رخی از کاربرد رویکرد تابع مولد ناشی می‌شود و همچنین از این واقعیت که ریشه‌های چندجمله‌ای رخی یک صفحه اطلاعات ارزشمندی در مورد ضرایب آن، یعنی تعداد حالت‌های چیدن k رخ غیر حمله‌ای، ارائه می‌دهند.

تعریف 
چندجمله‌ای رخی RB(x) یک صفحه B ،تابع مولد برای تعداد آرایش‌های رخ‌های غیر حمله‌ای است:

 

که r k تعداد روشهای قرار دادن k رخ غیرتهاجمی روی صفحه‌ای با m ردیف و n ستون است. تعداد رخ غیرتهاجمی که تخته می‌تواند نگه دارد یک کران بالایی دارد. در واقع، تعداد رخ‌ها از کمینه بین تعداد ردیف‌ها و ستون‌ها در تخته بزرگتر نیست. .

صفحه‌های کامل 
چند چندجمله‌ای رخی اول در صفحه‌های مربعی n × n (با Rn = RB) به این شکل است:

 

این بدان معنی است که در صفحهٔ ۱×۱، ۱ رخ را می‌توان به ۱ طریق چیدمان کرد، و صفر رخ را نیز می‌توان به ۱ طریق مرتب کرد (صفحه خالی). در صفحه کامل۲×۲، ۲ رخ را می‌توان به ۲ روش (روی قطرها) ترتیب داد، ۱ رخ را می‌توان به ۴ روش مرتب کرد و صفر رخ را می‌توان به ۱ طریق مرتب کرد. و غیره برای صفحه‌های بزرگتر.

برای صفحه‌های مستطیلی کامل m×n با نام Bm,n می‌نویسیم Rm,n:=RBm,n. مینیمم m و n را می‌توان به عنوان کران بالایی برای k در نظر گرفت، زیرا واضح است که r k = ۰ اگر k > min(m , n). این نیز در فرمول

Rm, n (x) نشان داده شده‌است.

چندجمله‌ای رخ در یک صفحه شطرنج مستطیلی ارتباط نزدیکی به تعمیم لاگر چندجمله‌ای LNα(x) با اتحاد زیر دارد.

چندجمله‌ای‌های تطبیقی 
چندجمله‌ای رخ حالت خاصی از یک نوع از چندجمله‌ای تطبیق است که تابع مولد تعداد تطابق k-یالی در یک گراف می‌باشد.

چندجمله‌ای رخی Rm, n(x) متناظر به گراف کامل دو بخشی K m , n است. چندجمله‌ای رخی یک صفحه دلخواه 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 رخ در صفحه برابر است با محاسبه ثابت ماتریس باینری (۰و ۱).

صفحه‌های مستطیل شکل کامل

مسائل رخی 
پیشگام چندجمله‌ای رخی، مسئله کلاسیک "معمای ۸ رخ (Eight rooks problem)" توسط HE Dudeney می‌باشد، که در آن او با قرار دادن رخ‌ها روی یکی از قطرهای اصلی نشان می‌دهد که حداکثر تعداد رخ‌های غیرتهاجمی روی یک صفحه شطرنج معمولی ۸ است (شکل ۱). سؤالی که مطرح می‌شود این است: "به چند حالت می‌توان هشت رخ را روی صفحه شطرنج ۸ × ۸ قرار داد تا هیچ یک از آنها دیگری را تهدید نکد؟" پاسخ این است: "بدیهی است که در هر ردیف و هر ستون باید یک رخ وجود داشته باشد. با شروع از ردیف پایین، مشخص است که اولین رخ را می‌توان روی هر یک از هشت خانه مختلف قرار داد (شکل ۱). هر جا که قرار داده شود، هفت خانه برای رخ دوم در ردیف دوم وجود دارد. سپس شش خانه برای انتخاب ردیف سوم، پنج خانه برای ردیف چهارم و غیره وجود دارد؛ بنابراین تعداد راه‌های مختلف باید ۸ × ۷ × ۶ × ۵ × ۴ × ۳ × ۲ × ۱ = ۴۰٬۳۲۰ باشد. (یعنی !۸، که "!" فاکتوریل است).

همین نتیجه را می‌توان با روشی کمی متفاوت بدست آورد. بیایید هر رخ را با یک عدد موقعیتی، متناسب با شماره ردیف آن، تطبیق دهیم و همچنین یک نام متناسب با نام ستون آن به آن اختصاص دهیم؛ بنابراین، رخ a1 دارای موقعیت ۱ و نام "a" می‌باشد؛ همچنین رخ b2 دارای موقعیت ۲ و نام "b" می‌باشد و غیره. سپس اجازه دهید رخ‌ها را با توجه به موقعیت آنها به یک لیست مرتب (دنباله) ترتیب دهیم. نمودار در شکل ۱ سپس به دنبالهٔ (a , b، c , d، e , f، g , h) تبدیل می‌شود. قرار دادن هر رخ بر روی ستون دیگری نیاز به جابجایی رخی که تا آن زمان آن ستون دوم را اشغال کرده بود، به ستون اول تخلیه شده‌است. به عنوان مثال، اگر رخ a1 به ستون "b" منتقل شود، رخ b2 باید به ستون "a" منتقل شود، و اکنون آنها رخ b1 و رخ a2 می‌شوند. دنباله جدید تبدیل خواهد شد (b , a، c , d، e , f، g , h). در ترکیبیات، این عملیات را جایگشت می‌نامند و دنباله‌هایی که در نتیجه جایگشت بدست می‌آیند، جایگشت‌های دنباله داده شده هستند. تعداد کل جایگشت‌ها، حاوی ۸ عنصر از دنباله ۸ عنصر، !۸ است (۸ فاکتوریل).

برای ارزیابی تأثیر محدودیت تحمیل شده «رخ‌ها نباید همدیگر را تهدید کنند»، مسئله را بدون چنین محدودیتی در نظر بگیرید. از چند طریق می‌توان هشت رخ را در صفحه شطرنج ۸ × ۸ قرار داد؟ این تعداد کل ترکیب ۸ رخ در ۶۴ خانه خواهد بود:

 

بنابراین، محدودیت «رخ نباید همدیگر را تهدید کنند» تعداد کل موقعیت‌های مجاز را از ترکیب به جایگشت‌ها کاهش می‌دهد که ضریب حدوداً برابر ۱۰۹٬۷۷۶ است.

تعدادی از مسائل از حوزه‌های مختلف فعالیت‌های انسانی را می‌توان با دادن «فرمول رخی» به مشکل رخ ساده کرد. به عنوان مثال: یک شرکت باید n کارمند در n شغل مختلف استخدام کند و هر شغل باید فقط توسط یک کارمند انجام شود. از چند طریق می‌توان این کار را انجام داد؟

بیایید ما کارمندان را در ردیف‌های یک صفحه شطرنج n×n قرار دهیم، و مشاغل را روی ستون‌ها. اگر کارمند i به شغل j منصوب شود، یک رخ در خانه‌ای قرار می‌گیرد که بر روی ردیف i و ستون j باشد. از آنجا که هر شغل فقط توسط یک کارمند انجام می‌شود و هر کارمند فقط به یک شغل منصوب می‌شود، در نتیجه آرایش n رخ روی تخته، کلیه ستون‌ها و ردیف‌ها فقط شامل یک رخ خواهند بود، یعنی رخ‌ها همدیگر را تهدید نمی‌کنند.

چندجمله‌ای رخی به عنوان تعمیم مسئله رخی 
مسئله کلاسیک رخ‌ها درجا به ما مقدار r 8 را می‌دهد. نتیجه آن این است که می‌توان ۸ رخ غیر تهاجمی را روی صفحه شطرنج ۸ × ۸ به r 8 = ۸! = ۴۰۳۲۰ حالت آرایش داد.

بیایید این مسئله را با در نظر گرفتن یک صفحه m × n، یعنی یک صفحه شطرنجی با m ردیف و n ستون تعمیم دهیم. مسئله به این صورت است: از چند طریق می‌توان k رخ را را بر روی صفحه m × n به گونه‌ای مرتب کرد که یکدیگر را تهدید نکنند؟

واضح است که برای آنکه مسئله قابل حل باشد، k باید کمتر یا مساوی مینیمم m و n باشد. در غیر این صورت نمی‌توان از قرار دادن یک جفت رخ در ردیف یا ستون یکسان جلوگیری کرد. پس فرض کنیم این شرط برقرار باشد. سپس آرایش رخ‌ها را می‌توان در دو مرحله انجام داد. ابتدا مجموعه‌ای از k ردیف را انتخاب کنید که رخ‌ها را در آن قرار دهید. از آنجا که تعداد ردیف‌ها m است، k باید از بین آنها انتخاب شود، می‌توان این انتخاب را در  روش انجام داد. به همین ترتیب، مجموعه k ستون‌هایی که می‌توان رخ‌ها را در آن قرار داد، انتخاب می‌شود به  روش. با توجه به قانون ضرب، از آنجا که انتخاب ستون‌ها به انتخاب ردیف‌ها بستگی ندارد  حالت برای انتخاب خانه‌هایی که رخ‌ها در آن چیده شوند وجود دارد.

با این حال، کار هنوز به پایان نرسیده‌است زیرا این k ردیف و k ستون در k 2 خانه تلاقی دارند. با حذف ردیف‌ها و ستون‌های بلااستفاده و چسباندن ردیف‌ها و ستون‌های باقیمانده با هم، یک صفحه جدید از k ردیف و k ستون بدست می‌آید. قبلاً نشان داده شده بود که در چنین صفحه‌ای می توان k رخ را به !k حالت آرایش داد (به طوری که همدیگر را تهدید نکنند). بنابراین، تعداد حالت‌های آرایش رخ‌های غیر تهاجمی به شکل فرمول زیر بدست می‌آید:

 

به عنوان مثال، ۳ رخ را در یک صفحه شطرنج معمولی (۸ × ۸) به حالت می‌توان قرار داد. برای k = m = n، فرمول فوق !rk = n را می‌دهدکه متناظر با نتیجه به دست آمده برای مسئله کلاسیک رخ است.

چندجمله‌ای رخی با ضرایب صریح اکنون به شکل زیر است:

 

اگر محدودیت «رخ‌ها نباید همدیگر را تهدید کنند» حذف شود، باید انتخاب هر k خانه از m×n خانه را محاسبه کرد. این را می‌توان در موارد زیر انجام داد:

  حالت.

اگر k رخ‌ها به طریقی با یکدیگر متفاوت باشند، به عنوان مثال، آنها دارای برچسب یا شماره گذاری شده باشند، عدد بدست آمده تاکنون را باید در !k ضرب کرد، که !k تعداد جایگشت‌های k رخ است.

آرایش‌های متقارن 
به عنوان یک عارضه دیگر برای مسئله رخ، اجازه دهید ما نه تنها رخ‌ها همدیگر را تهدید نکنند بلکه به‌طور متقارن روی صفحه قرار بگیرند را نیز لازم بدانیم. بسته به نوع تقارن، این معادل چرخش یا انعکاس صفحه است. آرایش‌های متقارن، بسته به شرایط تقارن، منجر به مشکلات زیادی می‌شوند.ساده‌ترین آن ترتیب‌ها زمانی است که رخ‌ها در حول مرکز صفحه متقارن هستند. بیایید Gn تعداد روش‌هایی که n رخ روی صفحه‌ای با n ردیف و n ستون قرار می‌گیرند، تعیین کنیم. اکنون بیایید صفحه را را شامل 2n ردیف و 2n ستون فرض کنیم. یک رخ روی ستون اول می‌تواند روی هر یک از 2n خانه آن ستون قرار گیرد. با توجه به شرایط تقارن، قرارگیری این رخ محل قرارگیری یک رخ را که روی آخرین ستون قرار دارد مشخص می‌کند - باید به‌طور قرینه با اولین رخ در حول مرکز صفحه چیده شود. اجازه دهید اولین و آخرین ستون‌ها و ردیف‌هایی که توسط رخ‌ها اشغال شده‌اند را حذف کنیم (از آنجا که تعداد ردیف‌ها زوج است، رخ‌های حذف شده نمی‌توانند در ردیف یکسان قرار گیرند). این یک صفحه با 2n-۲ ردیف و 2n-۲ ستون می‌سازد. واضح است که برای هر چیدمان متقارن رخ‌های روی صفحه جدید متناظر به یک چیدمان متقارن رخ‌ها روی صفحه اصلی است؛ بنابراین، G 2n = 2nG 2 n-2 (ضریب 2n در این عبارت از این امکان به‌وجود می‌آید که اولین رخ هر یک از 2n خانه موجود در ستون اول را اشغال کند). با تکرار فرمول فوق می‌توان به حالت صفحه ۲×۲ رسید، که روی آن ۲ ترتیب متقارن (روی قطرها) وجود دارد. در نتیجه این تکرار، عبارت نهایی برابر !G2n = 2nn است. برای صفحه شطرنج معمول (8 × ۸)، G 8 = 24×۴ = 16×۲۴ = ۳۸۴ آرایش متقارن حول مرکز از ۸ رخ وجود دارد. یکی از این آرایش‌ها در شکل ۲ نشان داده شده‌است.

برای تخته‌های با اندازه فرد (حاوی 2n+۱ ردیف و 2n+۱ ستون) همیشه یک خانه وجود دارد که خانه متقارن ندارد - این خانه مرکزی تخته است. همیشه باید یک رخ در این خانه قرار داده شود. حال با حذف ستون و ردیف مرکزی، یک آرایش متقارن 2n رخ بر روی صفحه 2n×2n بدست می‌آید. بنابراین، برای چنین صفحه‌ای، یک بار دیگر بدست می‌آید !G2n+1 = G2n = 2nn.

مسئله کمی پیچیده‌تر این است که تعداد آرایش‌های غیرتهاجمی را پیدا کنید که با چرخش ۹۰ درجه صفحه تغییر نمی‌کنند. فرض کنیم صفحه دارای 4n ستون و 4n ردیف باشد و تعداد رخ‌ها نیز 4n است. در این حالت، رخی که روی ستون اول است می‌تواند هر مربع روی این ستون را اشغال کند، به غیر از خانه‌های گوشه‌ای (یک رخ نمی‌تواند در یک خانه گوشه‌ای باشد زیرا بعد از چرخش ۹۰ درجه، ۲ رخ وجود دارند که همدیگر را تهدید می‌کنند). ۳ رخ دیگر نیز وجود دارد که با آن رخ مطابقت دارد و آنها به ترتیب روی آخرین ردیف، آخرین ستون و ردیف اول قرار می‌گیرند (با چرخش ۹۰ درجه، ۱۸۰ درجه و ۲۷۰ درجه از اولین صخره بدست می‌آیند). با حذف ستون‌ها و ردیف‌های این رخ‌ها، چیدمان رخی برای یک صفحه (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+2)×(4n+۲) و (4n+3)×(4n+۳)، تعداد راه حل‌ها صفر است. برای هر رخ دو حالت ممکن است: یا در مرکز قرار دارد یا در مرکز قرار نمی‌گیرد. در حالت ثانوی، این رخ در خانه رخی گنجانده شده‌است که با چرخاندن ۹۰ درجه صفحه بدست می‌آید؛ بنابراین، تعداد کل رخ‌ها باید 4n باشد (وقتی خانه مرکزی روی صفحه وجود ندارد) یا 4n+۱ باشد. این ثابت می‌کند که R4n+2 = R4n+3 = ۰.

تعداد چیدمان n رخ غیر تهاجمی متقارن نسبت به یکی از قطرها (برای تعیین قطر، قطر مربوط به a1-h8 در صفحه شطرنج) در صفحه n×n با شماره تلفن‌های مشخص می‌شود که با بازگشتی Qn = Qn−1 + (n−1)Qn−2 تعریف می‌شود. این بازگشتی از طریق زیر بدست می‌آید. توجه داشته باشید که رخ موجود در ستون اول یا در خانه گوشه پایین قرار دارد یا در یک خانه دیگر قرار دارد. در حالت اول، حذف ستون اول و ردیف اول منجر به آرایش متقارن n-1 رخ بر روی یک صفحه (n−1)×(n−۱) می‌شود. تعداد حالت‌های آرایش باقیمانده Qn−1 می‌باشد. در حالت دوم، برای رخ اصلی، یک رخ دیگر وجود دارد، متقارن با اولین رخ در حول قطر انتخاب شده. حذف ستون‌ها و ردیف‌های این رخ‌ها منجر به آرایش متقارن n رخ بر روی یک صفحه (n−2)×(n−۲) می‌شود. از آنجا که تعداد حالت‌های آرایش باقیمانده Qn−2 می‌باشد و خانه رخ اصلی را می‌توان به n-1 حالت انتخاب کرد، در کل برای حالت دوم (n−1)Qn−2 روش آرایش وجود دارد. که جمع این دو حالت عبارت بازگشتی بالا را نتیجه می‌دهد. تعداد روش‌های آرایش متقارن به قطر از عبارت زیر بدست می‌آید.

 

این عبارت با تقسیم‌بندی همه آرایش‌های رخی در کلاس‌ها بدست می‌آید. در کلاس s آن آرایش‌هایی هستند که s رخ متقارن روی قطر قرار نگیرند. دقیقاً به همین ترتیب، می‌توان نشان داد که تعداد آرایش‌های n رخ در صفحه n×n، به گونه‌ای که آنها همدیگر را تهدید نکنند و متقارن با هر دو مورب باشند، توسط معادلات بازگشتی B2n = 2B2n−2 + (2n−2)B2n−4 and B2n+1 = B2n بدست می‌آیند.

آرایش‌هایی که با کلاس‌های تقارن شمرده می‌شوند 
نوع دیگری از تعمیم این است که در آن آرایش‌های رخی که با تقارن صفحه از یکدیگر به دست می‌آیند، یک بار حساب شوند. به عنوان مثال، اگر چرخش ۹۰ درجه‌ای صفحه به عنوان تقارن مجاز باشد، پس هر آرایشی که با چرخش ۹۰، ۱۸۰ یا ۲۷۰ درجه بدست آید، «همان» الگوی اصلی در نظر گرفته می‌شود، حتی اگر این آرایش‌ها در مسئله اولیه که صفحه ثابت است جداگانه شمارش شده باشند. برای چنین مسائلی، دودنی مشاهده می‌کند: «هنوز که هنوز است معلوم نشده که اگر معکوس‌ها و بازتاب‌ها متفاوت حساب نشوند، چند حالت وجود دارد؛ این مسئله‌ای دشوار است.» این مسئله به شمارش آرایش‌های متقارن از طریق لم برنساید ساده می‌شود.

منابع 

چندجمله‌ای‌های متعامد
جایگشت‌ها
موضوعات فاکتوریل و دوجمله‌ای
مسئله‌های ریاضی شطرنج
چندجمله‌ای‌ها
ترکیبیات شمارشی
تابع مولد