پرش به محتوا

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

از ویکی‌پدیا، دانشنامهٔ آزاد

در ترکیبییات ریاضیات، چند جمله ای رخی، یک چند جمله ای تولیدی از تعداد حالت‌های قرار دادن تعدادی رخ بر روی صفحه ای است شبیه یک صفحه شطرنجی می‌باشد؛ یعنی هیچ دو رخی در یک ردیف یا ستون نباشند. تخته زیر مجموعه خانه‌های (مربع‌های ۱ در ۱) یک صفحه شطرنجی مستطیل شکل با 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 به طوری که BB m, n متناظر به گراف دو بخشی با رئوس چپ v 1، v 2، …، v m و رئوس راست w 1، w 2، …، w n است و یال viwj وجود دارد اگر و تنها اگر خانه (i ,j) متعلق به B باشد؛ بنابراین، نظزیه چند جمله ای‌های رخی، به تعبیری، در نظریه چند جمله ای‌های تطبیقی موجود است.

ما یک نکته مهم را در مورد ضرایب rk استنباط می‌کنیم، که یادآوری می‌کنیم با توجه به تعداد حالت‌های قرارگیری‌های k رخ غیر تهاجمی در B: این اعداد تک‌مُدی هستند، یعنی تا کرانی افزایش می‌یابند و سپس کاهش می‌یابند. این (با یک استدلال استاندارد) از قضیه هیلمن و لیب[۳] در مورد صفرهای یک چند جمله ای منطبق (متفاوت از آنچه مربوط به چند جمله ای رخی است، اما معادل آن با تغییر متغیرها) بدست می‌آید، که به این معنی است که تمام صفرهای چند جمله ای رخی اعداد حقیقی منفی هستند.

اتصال به ماتریس دائمی

[ویرایش]

برای صفحات مربعی n×n ناقص، (به عنوان مثال رخ‌ها در برخی از زیرمجموعه‌های دلخواه خانه‌های صفحه مجاز نیست) محاسبه تعداد راه‌های قرار دادن n رخ در صفحه برابر است با محاسبه ثابت ماتریس باینری (۰و ۱).

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

[ویرایش]

مسائل رخی

[ویرایش]
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
شکل ۱: تعداد ماکسیمال رخ‌های غیر تهاجمی بر روی یک صفحه شطرنج ۸×۸ برابر ۸ می‌باشد. رخ‌ها و نقطه‌ها نشان می‌دهند تعداد خانه‌های یک ردیف برای هر رخ بعد از قرار دادن رخ‌های ردیف‌های پایین‌تر کدامند.

پیشگام چند جمله ای رخی، مسئله کلاسیک "معمای ۸ رخ (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 رخ است.

آرایش‌های متقارن

[ویرایش]

به عنوان یک عارضه دیگر برای مسئله رخ، اجازه دهید ما نه تنها رخ‌ها همدیگر را تهدید نکنند بلکه به‌طور متقارن روی صفحه قرار بگیرند را نیز لازم بدانیم. بسته به نوع تقارن، این معادل چرخش یا انعکاس صفحه است. آرایش‌های متقارن، بسته به شرایط تقارن، منجر به مشکلات زیادی می‌شوند.[۷][۸][۹][۱۰]

abcdefgh
8
b8 black rook
h7 black rook
e6 black rook
c5 black rook
d5 black circle
e5 black circle
d4 black circle
e4 black circle
f4 black rook
d3 black rook
a2 black rook
g1 black rook
8
77
66
55
44
33
22
11
abcdefgh
شکل ۲: یک آرایش متقارن حول مرکز از رخ‌های غیر تهاجمی در یک صفحه شطرنج معمولی. نقاط چهار خانه مجاور مرکزتقارن را نمایش می‌دهند.

ساده‌ترین آن ترتیب‌ها زمانی است که رخ‌ها در حول مرکز صفحه متقارن هستند. بیایید 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 بدست می‌آیند.

آرایش‌هایی که با کلاس‌های تقارن شمرده می‌شوند

[ویرایش]

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

منابع

[ویرایش]
  1. , Introduction to Combinatorial Analysis, Princeton University Press, 1980 (originally published by John Wiley and Sons, New York; Chapman and Hall, London, 1958) شابک ‎۹۷۸−۰−۶۹۱−۰۲۳۶۵−۶ (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: شابک ‎۱−۶۰۳۰۳−۱۵۲−۹, also as a collection of newspaper clippings, Dover Publications, 1958; Kessinger Publishing, 2006). The book can be freely downloaded from Project Gutenberg site
  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). شابک ‎۳−۸۷۱۴۴−۹۸۷−۳ (GVK-Gemeinsamer Verbundkatalog)
  10. Kokhas', Konstantin P. Rook Numbers and Polynomials (Ladeynye chisla i mnogochleny). MCNMO, Moscow, 2003 (in Russian). شابک ‎۵−۹۴۰۵۷−۱۱۴-X www.mccme.ru/free-books/mmmf-lectures/book.26.pdf (GVK-Gemeinsamer Verbundkatalog)
  11. Dudeney, Answer to Problem 295