تاریخچه ی:
جایگشت های دوری
تفاوت با نگارش: 1
| | ||V{maketoc}|| | | ||V{maketoc}|| |
| - | ||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| |
+ | ||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| |
| | ^@#16: | | ^@#16: |
| | !جایگشت‌های دوری | | !جایگشت‌های دوری |
| | !!مثال | | !!مثال |
| | به چند طریق 6 نفر می‌توانند دور یک میز دایره‌ای بنشینند؟ (دقت کنید که در آرایشی که با دوران هم دیگر به دست آیند را یکسان حساب می‌کنیم، به عنوان مثال اگر 6 نفر را، با{TEX()} { A, B, C, D, E, F } {TEX} نشان دهیم؛ آرایش شکل الف با آرایش شکل ب یکسان است ولی با آرایش شکل ج یکسان نیست) | | به چند طریق 6 نفر می‌توانند دور یک میز دایره‌ای بنشینند؟ (دقت کنید که در آرایشی که با دوران هم دیگر به دست آیند را یکسان حساب می‌کنیم، به عنوان مثال اگر 6 نفر را، با{TEX()} { A, B, C, D, E, F } {TEX} نشان دهیم؛ آرایش شکل الف با آرایش شکل ب یکسان است ولی با آرایش شکل ج یکسان نیست) |
| | ::{picture=img/daneshnameh_up/9/95/com0014a.jpg}:: | | ::{picture=img/daneshnameh_up/9/95/com0014a.jpg}:: |
| | __حل __ | | __حل __ |
| | __ روش اول.__ در حال مسائلی که شرایطی را گذاشته‌اند سعی می‌کنیم، این شرایط را به نحوی برطرف کنیم تا به مسائل ساده‌ای که می‌توانیم حل کنیم، تبدیل شوند. به عنوان نمونه در این مثال، شرط مسأله یکسان بودن دوجایگشتی است که با دوران میز به یکدیگر تبدیل می‌شوند. چون میز را می‌توانیم دوران دهیم، پس می‌توان فرض کرد که {TEX()} {A} {TEX}همواره بالای میز می‌نشیند. با ثابت نگه‌داشتن جای {TEX()} {A} {TEX}، شرط دوران از بین می‌رود. حال 5 نفر داریم که می‌خواهیم آنها را در 5 جای خالی بنشانیم و در مثال‌های قبل دیدیم که این کار را به{TEX()} {5!} {TEX} طریق می‌توان انجام داد. | | __ روش اول.__ در حال مسائلی که شرایطی را گذاشته‌اند سعی می‌کنیم، این شرایط را به نحوی برطرف کنیم تا به مسائل ساده‌ای که می‌توانیم حل کنیم، تبدیل شوند. به عنوان نمونه در این مثال، شرط مسأله یکسان بودن دوجایگشتی است که با دوران میز به یکدیگر تبدیل می‌شوند. چون میز را می‌توانیم دوران دهیم، پس می‌توان فرض کرد که {TEX()} {A} {TEX}همواره بالای میز می‌نشیند. با ثابت نگه‌داشتن جای {TEX()} {A} {TEX}، شرط دوران از بین می‌رود. حال 5 نفر داریم که می‌خواهیم آنها را در 5 جای خالی بنشانیم و در مثال‌های قبل دیدیم که این کار را به{TEX()} {5!} {TEX} طریق می‌توان انجام داد. |
| | __روش دوم. __ اگر شرط دوران را در نظر نگیریم، به {TEX()} {6!} {TEX} حالت می‌توان این شش نفر را دور میز نشاند. ولی هر 6 جایگشت خطی معادل یک جایگشت دورانی می‌باشند، به عنوان مثال جایگشت‌های خطی{TEX()} { ABCDEF، BCDEFA، CDEFAB، DEFABC، EFABCD و FABCDE } {TEX} ، همگی یک جایگشت دوری را مشخص می‌کنند. پس جواب مسأله برابر است با {TEX()} {\frac{6!}{6}=5!} {TEX} . | | __روش دوم. __ اگر شرط دوران را در نظر نگیریم، به {TEX()} {6!} {TEX} حالت می‌توان این شش نفر را دور میز نشاند. ولی هر 6 جایگشت خطی معادل یک جایگشت دورانی می‌باشند، به عنوان مثال جایگشت‌های خطی{TEX()} { ABCDEF، BCDEFA، CDEFAB، DEFABC، EFABCD و FABCDE } {TEX} ، همگی یک جایگشت دوری را مشخص می‌کنند. پس جواب مسأله برابر است با {TEX()} {\frac{6!}{6}=5!} {TEX} . |
| | در این مثال، دو روش برای حل مسائل دوراین یادگرفتیم. روش اول از بین بردن شرط دوران با استفاده از ثابت نگه‌داشتن یک نفر و روش دوم تبدیل جایگشت دوری به جایگشت خطی. در ایده‌ی اول فردی که جای آن را ثابت نگه‌داشتیم هر یک از افراد می‌توانست باشد و انتخاب این فرد به عهدة ما می‌باشد. | | در این مثال، دو روش برای حل مسائل دوراین یادگرفتیم. روش اول از بین بردن شرط دوران با استفاده از ثابت نگه‌داشتن یک نفر و روش دوم تبدیل جایگشت دوری به جایگشت خطی. در ایده‌ی اول فردی که جای آن را ثابت نگه‌داشتیم هر یک از افراد می‌توانست باشد و انتخاب این فرد به عهدة ما می‌باشد. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | به چند طریق می‌توان از بین 5 نفر، 3 نفر را دور یک میز دایره‌ای نشاند؟ | | به چند طریق می‌توان از بین 5 نفر، 3 نفر را دور یک میز دایره‌ای نشاند؟ |
| | __حل.__ | | __حل.__ |
| | از ایدة دوم استفاده می‌کنیم. اگر دوران را در نظر نگیریم، به {TEX()} {P_3^5} {TEX} طریق می‌توان سه نفر از بین پنج نفر را دور میز نشاند. ولی به دلیل دوران، هر حالت سه بار شمرده شده است، پس جواب برابر با {TEX()} {\frac{P_3^5}{3}=20} {TEX} می‌باشد. | | از ایدة دوم استفاده می‌کنیم. اگر دوران را در نظر نگیریم، به {TEX()} {P_3^5} {TEX} طریق می‌توان سه نفر از بین پنج نفر را دور میز نشاند. ولی به دلیل دوران، هر حالت سه بار شمرده شده است، پس جواب برابر با {TEX()} {\frac{P_3^5}{3}=20} {TEX} می‌باشد. |
| | --- | | --- |
| | !نکته | | !نکته |
| | به طریق مشابه می‌توان ثابت کرد که از بین{TEX()} { n } {TEX} نفر، {TEX()} { k } {TEX} نفر {TEX()} {k\le n} {TEX} را به {TEX()} {\frac{P_k^n}{k}} {TEX} طریق می‌توان دور یک میز نشاند. | | به طریق مشابه می‌توان ثابت کرد که از بین{TEX()} { n } {TEX} نفر، {TEX()} { k } {TEX} نفر {TEX()} {k\le n} {TEX} را به {TEX()} {\frac{P_k^n}{k}} {TEX} طریق می‌توان دور یک میز نشاند. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | به چند طریق 7 نفر را می‌توان دور یک میز دایره‌ای 10 نفره، (میزی که 10 صندلی دارد) نشاند؟ | | به چند طریق 7 نفر را می‌توان دور یک میز دایره‌ای 10 نفره، (میزی که 10 صندلی دارد) نشاند؟ |
| | __حل. __ | | __حل. __ |
| | __راه حل اول__. اگر این 7 نفر را با {TEX()} {A_1,A_2,\cdots ,A_7} {TEX} و صندلی‌ها را با {TEX()} {B_1,B_2,\cdots ,B_{10}} {TEX} نشان دهیم، می‌توان فرض کرد که {TEX()} {A_1} {TEX} روی صندلی {TEX()} {B_1} {TEX} نشسته است. (زیرا در غیر این صورت می‌توانیم با چرخاندن میز صندلی فرد {TEX()} {A_1} {TEX} را به صندلی {TEX()} {B_1} {TEX} تبدیل کنیم.) حال با نشستن {TEX()} {A_1} {TEX} شرط دوران از بین رفته است و حالا 6 نفر دیگر داریم که باید روی 9 صندلی خالی بنشینند. در قسمت‌های قبل یاد گرفتیم که این افراد به {TEX()} {P_6^9} {TEX} طریق می‌توانند این کار را انجام دهند. پس جواب برابر است با {TEX()} {P_6^9} {TEX}. | | __راه حل اول__. اگر این 7 نفر را با {TEX()} {A_1,A_2,\cdots ,A_7} {TEX} و صندلی‌ها را با {TEX()} {B_1,B_2,\cdots ,B_{10}} {TEX} نشان دهیم، می‌توان فرض کرد که {TEX()} {A_1} {TEX} روی صندلی {TEX()} {B_1} {TEX} نشسته است. (زیرا در غیر این صورت می‌توانیم با چرخاندن میز صندلی فرد {TEX()} {A_1} {TEX} را به صندلی {TEX()} {B_1} {TEX} تبدیل کنیم.) حال با نشستن {TEX()} {A_1} {TEX} شرط دوران از بین رفته است و حالا 6 نفر دیگر داریم که باید روی 9 صندلی خالی بنشینند. در قسمت‌های قبل یاد گرفتیم که این افراد به {TEX()} {P_6^9} {TEX} طریق می‌توانند این کار را انجام دهند. پس جواب برابر است با {TEX()} {P_6^9} {TEX}. |
| | راه حل دوم. اگر دوران را در نظر نگیریم به {TEX()} {P_7^{10}} {TEX} طریق می‌توانیم این 7 نفر را دور میز بنشانیم و چون هر حالت را 10 بار شمرده‌ایم (زیرا با دوران می‌توانیم از هر حالت، 10 حالت بسازیم)، بنابراین جواب برابر است با: {TEX()} {\frac{P_7^{10}}{10}} {TEX} . | | راه حل دوم. اگر دوران را در نظر نگیریم به {TEX()} {P_7^{10}} {TEX} طریق می‌توانیم این 7 نفر را دور میز بنشانیم و چون هر حالت را 10 بار شمرده‌ایم (زیرا با دوران می‌توانیم از هر حالت، 10 حالت بسازیم)، بنابراین جواب برابر است با: {TEX()} {\frac{P_7^{10}}{10}} {TEX} . |
| | --- | | --- |
| | !نکته | | !نکته |
| | به طریق مشابه می‌توان ثابت کرد اگر بخواهیم{TEX()} { n } {TEX} نفر را دور یک میزگرد {TEX()} { m } {TEX} نفره {TEX()} {m\ge n} {TEX}، بنشانیم؛ به {TEX()} {\frac{P_n^m}{m}=P_{n-1}^{m-1}} {TEX} طریق می‌توانیم این کار را بکنیم. | | به طریق مشابه می‌توان ثابت کرد اگر بخواهیم{TEX()} { n } {TEX} نفر را دور یک میزگرد {TEX()} { m } {TEX} نفره {TEX()} {m\ge n} {TEX}، بنشانیم؛ به {TEX()} {\frac{P_n^m}{m}=P_{n-1}^{m-1}} {TEX} طریق می‌توانیم این کار را بکنیم. |
| | !!مثال | | !!مثال |
| | به چند طریق می‌توان با پنج‌مهرة به رنگ‌های قرمز، سفید، سبز، آبی و زرد یک گردن‌بند ساخت؟ | | به چند طریق می‌توان با پنج‌مهرة به رنگ‌های قرمز، سفید، سبز، آبی و زرد یک گردن‌بند ساخت؟ |
| | __حل__ | | __حل__ |
| | در ساخت گردن‌بند اگر نمی‌توانستیم آن را برگردانیم، جواب برابر با !4 بود. ولی دو جایگشت {TEX()} { RWGBY , RYBGW } {TEX} یک گردن‌بند را می‌سازند. (از برگرداندن یکدیگر به دست می‌آیند.) به طور مشابه چون هر حالت را دو بار شمرده‌ایم؛ جواب مسأله برابر است با {TEX()} {\frac{4!}{2}} {TEX} . | | در ساخت گردن‌بند اگر نمی‌توانستیم آن را برگردانیم، جواب برابر با !4 بود. ولی دو جایگشت {TEX()} { RWGBY , RYBGW } {TEX} یک گردن‌بند را می‌سازند. (از برگرداندن یکدیگر به دست می‌آیند.) به طور مشابه چون هر حالت را دو بار شمرده‌ایم؛ جواب مسأله برابر است با {TEX()} {\frac{4!}{2}} {TEX} . |
| | --- | | --- |
| | !نکته | | !نکته |
| | به طور مشابه با {TEX()} {n\ge 3} {TEX} مهرة مختلف، {TEX()} {\frac{(n-1)!}{2}} {TEX} گردن‌بند متفاوت می‌توان ساخت. | | به طور مشابه با {TEX()} {n\ge 3} {TEX} مهرة مختلف، {TEX()} {\frac{(n-1)!}{2}} {TEX} گردن‌بند متفاوت می‌توان ساخت. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | به چند طریق 9 ریاضی‌دان و 7 فیزیک‌دان می‌توانند دوریک میز گرد بنشینند، به طوری که | | به چند طریق 9 ریاضی‌دان و 7 فیزیک‌دان می‌توانند دوریک میز گرد بنشینند، به طوری که |
| | __الف.__هیچ شرطی وجود نداشته باشد. | | __الف.__هیچ شرطی وجود نداشته باشد. |
| | __ب.__فیزیک‌دان {TEX()} {P_1} {TEX}کنار ریاضی‌دان {TEX()} {M_1} {TEX}ننشسته باشد. | | __ب.__فیزیک‌دان {TEX()} {P_1} {TEX}کنار ریاضی‌دان {TEX()} {M_1} {TEX}ننشسته باشد. |
| | __ج.__هیچ دو فیزیک‌دانی کنار یکدیگر ننشینند. | | __ج.__هیچ دو فیزیک‌دانی کنار یکدیگر ننشینند. |
| | __د.__همة فیزیک‌دان‌ها کنار یکدیگر نشسته باشند. | | __د.__همة فیزیک‌دان‌ها کنار یکدیگر نشسته باشند. |
| | --- | | --- |
| | __حل.__ | | __حل.__ |
| | __الف.__-چون{TEX()} {9+7=16} {TEX} نفر داریم؛ جواب برابر است با{TEX()} {15!} {TEX}. | | __الف.__-چون{TEX()} {9+7=16} {TEX} نفر داریم؛ جواب برابر است با{TEX()} {15!} {TEX}. |
| | __ب.__ راه حل اول. ابتدا با نگه‌داشتن جای ریاضی‌دان {TEX()} {M_1} {TEX}شرط دوران را از بین می‌بریم. حال برای از بین بردن شرط کنار هم ننشستن {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}، فیزیک‌دان {TEX()} {P_1} {TEX}را می‌نشانیم. فیزیک‌دان {TEX()} {P_1} {TEX}نمی‌تواند روی صندلی که ریاضی‌دان {TEX()} {M_1} {TEX}نشسته و دو صندلی مجاور آن بنشیند، بنابراین فیزیک‌دان {TEX()} {P_1} {TEX}به{TEX()} {16-3=13} {TEX}طریق می‌تواند بنشیند. حال 14 نفر دیگر به{TEX()} {14!} {TEX}طریق می‌توانند روی صندلی‌های باقی مانده بنشینند. پس طبق اصل ضرب جواب برابر است با{TEX()} {13\times 14!} {TEX} | | __ب.__ راه حل اول. ابتدا با نگه‌داشتن جای ریاضی‌دان {TEX()} {M_1} {TEX}شرط دوران را از بین می‌بریم. حال برای از بین بردن شرط کنار هم ننشستن {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}، فیزیک‌دان {TEX()} {P_1} {TEX}را می‌نشانیم. فیزیک‌دان {TEX()} {P_1} {TEX}نمی‌تواند روی صندلی که ریاضی‌دان {TEX()} {M_1} {TEX}نشسته و دو صندلی مجاور آن بنشیند، بنابراین فیزیک‌دان {TEX()} {P_1} {TEX}به{TEX()} {16-3=13} {TEX}طریق می‌تواند بنشیند. حال 14 نفر دیگر به{TEX()} {14!} {TEX}طریق می‌توانند روی صندلی‌های باقی مانده بنشینند. پس طبق اصل ضرب جواب برابر است با{TEX()} {13\times 14!} {TEX} |
| | دقت کنید در حل مسائلی که برای افراد یا اشیاء تعیین کرده‌اند، اول سعی کنید تا وضعیت آن افراد یا اشیاء را مشخص کنید تا شرط مسأله از بین برود تا بتوانید باقی مسأله را به راحتی حل کنید. به عنوان مثال، در این مثال ابتدا ریاضی‌دان {TEX()} {M_1} {TEX}و فیزیک‌دان {TEX()} {P_1} {TEX}را نشاندیم تا شرط کنار هم ننشستن {TEX()} {P_1} {TEX}و {TEX()} {M_1} {TEX}برطرف شود. | | دقت کنید در حل مسائلی که برای افراد یا اشیاء تعیین کرده‌اند، اول سعی کنید تا وضعیت آن افراد یا اشیاء را مشخص کنید تا شرط مسأله از بین برود تا بتوانید باقی مسأله را به راحتی حل کنید. به عنوان مثال، در این مثال ابتدا ریاضی‌دان {TEX()} {M_1} {TEX}و فیزیک‌دان {TEX()} {P_1} {TEX}را نشاندیم تا شرط کنار هم ننشستن {TEX()} {P_1} {TEX}و {TEX()} {M_1} {TEX}برطرف شود. |
| | راه حل دوم (استفاده از اصل متمم). در این روش تعداد حالات مطلوب را از تفریق تعداد حالات نامطلوب از تعداد کل حالات به دست می‌آوریم. این روش حالت خاصی از اصل شمول و عدم شمول است که در فصل‌های آتی بررسی خواهد شد. | | راه حل دوم (استفاده از اصل متمم). در این روش تعداد حالات مطلوب را از تفریق تعداد حالات نامطلوب از تعداد کل حالات به دست می‌آوریم. این روش حالت خاصی از اصل شمول و عدم شمول است که در فصل‌های آتی بررسی خواهد شد. |
| | اگر شرط کنار هم ننشستن، {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}وجود نداشت به{TEX()} {15!} {TEX} طریق این 16 نفر می‌توانستند دور میز بنشینند. اما ببینیم تعداد حالات نامطلوب چند تاست؟ حالاتی که {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}کنار هم نشسته باشند، نامطلوب است. برای شمردن تعداد این حالات {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}را یک فرد واحد مثل {TEX()} {A} {TEX}در نظر بگیرید؛ | | اگر شرط کنار هم ننشستن، {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}وجود نداشت به{TEX()} {15!} {TEX} طریق این 16 نفر می‌توانستند دور میز بنشینند. اما ببینیم تعداد حالات نامطلوب چند تاست؟ حالاتی که {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}کنار هم نشسته باشند، نامطلوب است. برای شمردن تعداد این حالات {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}را یک فرد واحد مثل {TEX()} {A} {TEX}در نظر بگیرید؛ |
| | حال 15 نفر داریم که آنها را به {TEX()} {14!} {TEX} طریق می‌توان دور میز نشاند ولی خود {TEX()} {A} {TEX}دو حالت دارد ({TEX()} {P_1} {TEX}سمت راست {TEX()} {M_1} {TEX}یا سمت چپ {TEX()} {M_1} {TEX}باشد.) بنابراین طبق اصل ضرب در{TEX()} {2\times 14!} {TEX}حالت، {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}مجاور یکدیگرند. بنابراین تعداد حالات مطلوب برابر است با: {TEX()} {15!-2\times 14!=13\times 14!} {TEX} | | حال 15 نفر داریم که آنها را به {TEX()} {14!} {TEX} طریق می‌توان دور میز نشاند ولی خود {TEX()} {A} {TEX}دو حالت دارد ({TEX()} {P_1} {TEX}سمت راست {TEX()} {M_1} {TEX}یا سمت چپ {TEX()} {M_1} {TEX}باشد.) بنابراین طبق اصل ضرب در{TEX()} {2\times 14!} {TEX}حالت، {TEX()} {M_1} {TEX}و {TEX()} {P_1} {TEX}مجاور یکدیگرند. بنابراین تعداد حالات مطلوب برابر است با: {TEX()} {15!-2\times 14!=13\times 14!} {TEX} |
| | __ج.__ ابتدا ریاضی‌دان‌ها را دور میز می‌نشانیم، به {TEX()} {8!} {TEX} طریق می‌توان این کار را انجام داد. حال بین ریاضی‌دان‌ها 9 جا وجود دارد که باید فیزیک‌دان‌ها در 7 جا از آنها بنشینند. پس فیزیک‌دان‌ها هم به {TEX()} {P_4^9} {TEX} طریق می‌توانند بنشینند. پس طبق اصل ضرب جواب مسأله برابر است با {TEX()} {8!\times P_7^9} {TEX} . | | __ج.__ ابتدا ریاضی‌دان‌ها را دور میز می‌نشانیم، به {TEX()} {8!} {TEX} طریق می‌توان این کار را انجام داد. حال بین ریاضی‌دان‌ها 9 جا وجود دارد که باید فیزیک‌دان‌ها در 7 جا از آنها بنشینند. پس فیزیک‌دان‌ها هم به {TEX()} {P_4^9} {TEX} طریق می‌توانند بنشینند. پس طبق اصل ضرب جواب مسأله برابر است با {TEX()} {8!\times P_7^9} {TEX} . |
| | __د.__ تمام فیزیک‌دان‌ها را یک نفر مثلاً {TEX()} {P} {TEX}، در نظر می‌گیریم. حالا 9 ریاضی‌دان و {TEX()} {P} {TEX}، مثل 10 نفر هستند و آنها را به{TEX()} {9!} {TEX} حالت می‌توانیم دور میز بنشانیم ولی خود فیزیک‌دان‌ها می‌توانند به{TEX()} {7!} {TEX}حالت کنار یکدیگر بنشینند. بنابراین جواب برابر است با: {TEX()} {7!\times 9!} {TEX} . | | __د.__ تمام فیزیک‌دان‌ها را یک نفر مثلاً {TEX()} {P} {TEX}، در نظر می‌گیریم. حالا 9 ریاضی‌دان و {TEX()} {P} {TEX}، مثل 10 نفر هستند و آنها را به{TEX()} {9!} {TEX} حالت می‌توانیم دور میز بنشانیم ولی خود فیزیک‌دان‌ها می‌توانند به{TEX()} {7!} {TEX}حالت کنار یکدیگر بنشینند. بنابراین جواب برابر است با: {TEX()} {7!\times 9!} {TEX} . |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | به چند طریق می‌توان {TEX()} {n} {TEX}زوج را دور یک میز گرد نشاند به طوری که: | | به چند طریق می‌توان {TEX()} {n} {TEX}زوج را دور یک میز گرد نشاند به طوری که: |
| | __الف.__مردها و زن‌ها یک در میان بنشینند. | | __الف.__مردها و زن‌ها یک در میان بنشینند. |
| | __ب.__مردها و زن‌ها یک در میان بنشینند و هر زنی نیز کنار همسر خود نشسته باشد. | | __ب.__مردها و زن‌ها یک در میان بنشینند و هر زنی نیز کنار همسر خود نشسته باشد. |
| | __حل. __ | | __حل. __ |
| | __الف.__ ابتدا مردها را به{TEX()} { (n – 1)!} {TEX} طریق دور میز می‌نشانیم. سپس بین هر دو مرد، یک زن می‌نشانیم که این کار به{TEX()} { n! } {TEX}طریق امکان دارد. پس طبق اصل ضرب، جواب مسأله برابر است با{TEX()} { n!(n – 1)! } {TEX}. | | __الف.__ ابتدا مردها را به{TEX()} { (n – 1)!} {TEX} طریق دور میز می‌نشانیم. سپس بین هر دو مرد، یک زن می‌نشانیم که این کار به{TEX()} { n! } {TEX}طریق امکان دارد. پس طبق اصل ضرب، جواب مسأله برابر است با{TEX()} { n!(n – 1)! } {TEX}. |
| | __ب.__ابتدا مردها را به{TEX()} { (n – 1)!} {TEX} طریق دور میز می‌نشانیم. حال برای نشستن همسر هر مرد، دو طریق وجود دارد. (سمت چپ یا سمت راست شوهر خود بنشینند). پس به {TEX()} {2^n} {TEX}طریق هم می‌توان زن‌ها را دور میز نشاند. در نتیجه جواب نهایی برابر است با {TEX()} {(n-1)!\times 2^n} {TEX} . | | __ب.__ابتدا مردها را به{TEX()} { (n – 1)!} {TEX} طریق دور میز می‌نشانیم. حال برای نشستن همسر هر مرد، دو طریق وجود دارد. (سمت چپ یا سمت راست شوهر خود بنشینند). پس به {TEX()} {2^n} {TEX}طریق هم می‌توان زن‌ها را دور میز نشاند. در نتیجه جواب نهایی برابر است با {TEX()} {(n-1)!\times 2^n} {TEX} . |
| | --- | | --- |
| | ! پیوند های خارجی | | ! پیوند های خارجی |
| | [http://Olympiad.roshd.ir/computer/content/pdf/0021.pdf] | | [http://Olympiad.roshd.ir/computer/content/pdf/0021.pdf] |
| | #@^ | | #@^ |
