تاریخچه ی:
جایگشت ها و جایگشت های با تکرار
||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__||
^@#16:
!جایگشتها و جایگشتهای با تکرار
!جایگشت (تبدیل)
جایگشتها که به آنها تبدیل یا ترتیب هم میگوییم به طور کلی آرایشبندیهای مرتب از اشیاء هستند، دقت کنید که در آنها ترتیب اشیاء مهم میباشد.
به طور مثال به چند طریق میتوان باسه حرف{TEX()} { c,b,a } {TEX} کلمات سه حرفی بدون حروف تکراری نوشت؟
از آنجا که در این کلمات، کلمه{TEX()} { abc } {TEX} با کلمه{TEX()} { acb } {TEX} تفاوت دارد یعنی ترتیب حروف (جای {TEX()} {c,b} {TEX}) اهمیت دارد پس سئوال به تعداد جایگشتهای سهتایی این حروف میپردازد. که بنابر اصل ضرب ، {TEX()} {3\times 2\times 1} {TEX} طریق میباشد.
---
!!مثال
10 نفر با شمارههای 1 تا 10 در جلسهای شرکت کردهاند. به چند طریق میتوان از میان آنها یک نفر رئیس جلسه، یک نفر منشی جلسه و یک نفر معاون جلسه انتخاب کرد.به شرطی که هر نفر حداکثر یک پست داشته باشد.
حل. دقت کنید که این سئوال متناظر با تعداد جایگشتهای 3تایی اعداد 1 تا 10 میباشد
::{picture=img/daneshnameh_up/1/13/com0013a.jpg}::
برای انتخاب رئیس جلسه 10 حالت داریم و پس از انتخاب فرد {TEX()} { i } {TEX} برای رئیس جلسه این فرد دیگر نمیتواند منشی جلسه باشد پس برای انتخاب منشی جلسه 9 حالت داریم و اگر منشی جلسه را{TEX()} { j } {TEX} بنامیم برای انتخاب معاون، میدانیم{TEX()} { i } {TEX} و{TEX()} { j } {TEX} نمیتوانند معاون هم باشند پس 8 نفر دیگر میماند و 8 حالت داریم پس بنابر اصل ضرب{TEX()} {10\times 9\times 8} {TEX}حالت داریم. که این تعداد را میتوان به صورت زیر هم نشان داد:
@@{TEX()} {10\times 9\times 8=\frac{10!}{(10-3)!}} {TEX}@@
در حالت کلی جواب هر یک از مسایل زیر که میخواهیم از بین{TEX()} { n } {TEX} شیء متمایز،{TEX()} { k } {TEX} شیئ را انتخاب کنیم و ترتیب اشیاء مهم است را با {TEX()} {P_k^n} {TEX} نشان میدهند و میخوانند «تبدیل {TEX()} {k} {TEX} از {TEX()} {n} {TEX}».
«با حروف{TEX()} { \{a_1 , a_2 ,\cdots , a_n\} } {TEX}چند کلمهی{TEX()} { k } {TEX} حرفی با حروف متمایز می توان ساخت؟»
«در یک مسابقه دوی ماراتن با n شرکت کننده، به چند طریق رتبههای 1 تا{TEX()} { k } {TEX} مشخص میشوند؟»
با استدلالی شبیه استدلال مثال بالا، میتوانید ثابت کنید:
@@{TEX()} {P_k^n=n(n-1)(n-2)\cdots (n-k+1)} {TEX}@@
با توجه به تعریف فاکتوریل و تبدیل داریم:
@@{TEX()} {P_k^n=n(n-1)(n-2)\cdots (n-k+1)\times\frac{(n-k)(n-k-1)\times\cdots\times 2\times 1}{(n-k)(n-k-1)\times\cdots\times 2\times 1}=\frac{n!}{(n-k)!}} {TEX}@@
---
!!مثال.
الف. با 10 حرف{TEX()} { A، B، C، D، E، F، G، H، I , J } {TEX} چند کلمه 5 حرفی با حروف متمایز میتوان ساخت؟
ب. در چند تا از کلمات قسمت الف، حروف{TEX()} { A، B، C، D، E , F } {TEX} فقط در مکانهای فرد و بقیه حروف در مکانهای زوج استفاده شده است؟
__حل.__
الف.تعداد کلمات 5 حرفی با کلمات متمایز که با 10 حرف میتوان ساخت برابر است با {TEX()} {P_5^{10}} {TEX}.
ب. به {TEX()} {P_3^6} {TEX} طریق حروف مکانهای فرد و به {TEX()} {P_2^4} {TEX} طریق حروف مکانهای زوج را میتوان تعیین کرد، پس جواب مسأله برابر است با : {TEX()} {P_3^6\times P_2^4} {TEX}.
---
!!مثال
9 کتاب ((ریاضی)) و 4 کتاب فیزیک را به چند طریق میتوان در یک قفسه به طوری که:
الف.هیچ شرطی وجود نداشته باشد.
ب. کتابهای ((فیزیک)) کنار هم باشند. (بین هیچ دو کتاب فیزیک، کتاب ریاضی نباشد.)
ج. هیچ دو کتاب فیزیکی کنار هم نباشند و کتابهای اول و آخر ریاضی باشند. {TEX()} {P_3^4} {TEX}
د. بین دو کتاب ریاضی {TEX()} { M_1,M_2} {TEX} ، دقیقاً سه کتاب فیزیک باشد و هیچ کتاب ریاضی نباشد.
__حل.__
الف.چون 13 کتاب داریم، پس به{TEX()} {13!} {TEX} طریق میتوان آنها را در قفسه چید.
ب. چون کتابهای فیزیک باید مجاور باشند، کتابهای فیزیک را، یک کتاب مانند {TEX()} { P } {TEX} ، در نظر میگیریم. بنابراین 9 کتاب ریاضی و کتاب {TEX()} { P } {TEX} را به{TEX()} {10!} {TEX}حالت، میتوانیم بچینیم. از طرف دیگر خود کتاب{TEX()} { P } {TEX} میتواند به{TEX()} {4!} {TEX} حالت چیده شود. بنابر اصل ضرب جواب مسأله برابر است با : {TEX()} {10!\times 4!} {TEX}
ج. برای حل این قسمت ابتدا کتابهای ریاضی را در قفسه میچینیم و سپس کتابهای فیزیک را بین کتابهای ریاضی قرار میدهیم. به{TEX()} {9!} {TEX} حالت میتوانیم کتابهای ریاضی را بچینیم، حال چون هر کتاب فیزیک باید بین دو کتاب ریاضی باشد، بنابراین برای چیدن کتابهای فیزیک 8 جای خالی داریم. پس به {TEX()} {P_4^8} {TEX} طریق میتوانیم کتاب های فیزیک را بچینیم و بنابر ((اصل ضرب)) جوابهای نهایی مسأله برابر است با: {TEX()} {9!\times P_4^8} {TEX}.
::{picture=img/daneshnameh_up/9/9f/com0013bb.jpg}::
د. ابتدا سه کتاب فیزیکی را که باید بین کتابهای{TEX()} {M_2,M_1} {TEX} قرار بگیرند، به {TEX()} {P_3^4} {TEX} طریق میچینیم. خود کتب {TEX()} {M_2,M_1} {TEX} هم به دو طریق میتوانند قرار بگیرند. حال چون میخواهیم این سه کتاب فیزیک و کتب ریاضی {TEX()} {M_2,M_1} {TEX} کنار هم قرار بگیرند، آنها را یک کتاب بزرگ مانند {TEX()} {A} {TEX}در نظر میگیریم. حالا 9 کتاب (8 کتاب دیگر و کتاب {TEX()} {A} {TEX}) را به {TEX()} {9!} {TEX} طریق در قفسه میچینیم. ولی خود کتاب {TEX()} {A} {TEX}هم به {TEX()} {2\times P_3^4} {TEX} طریق میتوانست چیده شود. پس جواب مسأله برابر است با: {TEX()} {2\times P_3^4\times 9!} {TEX}.
---
!!مثال
چند عدد فرد با ارقام متمایز بین 3000 و 8000 وجود دارد؟
__حل__.
اعداد مطلوب را به شکل {TEX()} {\overline{abcd}} {TEX} نمایش میدهیم. عدد {TEX()} {a} {TEX}باید از مجموعه{TEX()} {\{3 , 4 , 5 , 6 , 7\}} {TEX} و عدد {TEX()} {d} {TEX}از مجموعه{TEX()} {\{1 , 3 , 5 , 7 , 9\} } {TEX} انتخاب شوند. چون{TEX()} {\{3,4,5,6,7\} \cap \{1,3,5,7,9\} = \{3,5,7\} } {TEX} ، مسأله را به دو قسمت زیر تقسیم میکنیم.
__حالت اول.__
@@ {TEX()} {a\in\{3,5,7\}} {TEX}@@
در این حالت برای انتخاب {TEX()} {a} {TEX}، 3 حالت و برای انتخاب {TEX()} {d} {TEX}نیز 4 حالت ({TEX()} {d} {TEX}را بعد از {TEX()} {a} {TEX}انتخاب میکنیم) و برای انتخاب بقیه رقمها نیز {TEX()} {P_2^{10-2}=P_2^8} {TEX} حالت وجود دارد. پس طبق اصل ضرب تعداد این اعداد برابر است با {TEX()} {3\times 4\times P_2^8=672} {TEX}.
__حالت دوم.__
#@
@#16:
@@ {TEX()} {d\in\{4,6\}} {TEX}@@
در این حالت برای انتخاب {TEX()} {a} {TEX}، 2 حالت و برای انتخاب {TEX()} {d} {TEX}نیز 5 حالت و برای انتخاب بقیه رقمها {TEX()} {P_2^{10-2}=P_2^8} {TEX} طریق وجود دارد. پس طبق اصل ضرب تعداد این اعداد برابر است با {TEX()} {2\times 5\times P_2^8} {TEX}
حال طبق اصل جمع تعداد کل اعداد برابر است با {TEX()} {672+560=1232} {TEX}.
---
!!مثال.
فرض کنید {TEX()} {S} {TEX}، مجموعه اعدادی باشد که با ارقام متمایز از مجموعه {TEX()} {\{1,2,3,4\} } {TEX} ساخته شدهاند.
الف. {TEX()} {S} {TEX}چند عضو دارد؟ {TEX()} {(|S|)} {TEX}
ب.مجموع اعداد عضو{TEX()} { S } {TEX} چقدر است؟ {TEX()} {\sum_{x\in S}x=?} {TEX}
__حل.__
الف.میدانیم تعداد اعداد {TEX()} {i} {TEX}رقمی با ارقام متمایز که با ارقام 1 تا 4 ساخته شدهاند برابر است با: {TEX()} {P_i^4} {TEX}. پس طبق اصل جمع داریم:
@@{TEX()} {|S|=P_1^4+P_2^4+P_3^4+P_4^4=4+12+24+24=64} {TEX}@@
ب. اگر{TEX()} { a } {TEX} مجموع رقمهای یکان، {TEX()} { b } {TEX} مجموع رقمهای دهگان، {TEX()} { c } {TEX} مجموع رقمهای صدگان و {TEX()} { d } {TEX} مجموع رقمهای هزارگان باشد. جواب مسأله برابر است با
@@{TEX()} {1000\times d+100\times c+10\times b+a} {TEX}@@
چون ارقام 1، 2 ، 3 و 4 هیچ تفاوتی با هم ندارند، پس تعداد اعدادی که رقم یکان آنها برابر 1 است برابر تعداد اعدادی است که رقم یکان آنها برابر 2 است و همین طور برای رقم دهگان و … .
تعداد اعضای {TEX()} { S } {TEX} رقم یکان دارند برابر است با {TEX()} {|S|=64} {TEX}. پس {TEX()} {a=\frac{64\times(1+2+3+4)}{4}=160} {TEX}.
تعداد اعضای{TEX()} { S } {TEX} که رقم دهگان دارند برابر است با {TEX()} {P_2^4+P_3^4+P_4^4=60} {TEX} (اعداد دو، سه و چهار رقمی). پس {TEX()} {b=\frac{60\times 10}{4}=150} {TEX}. تعداد اعضای{TEX()} { S } {TEX} که رقم صدگان دارند برابر است با {TEX()} {P_3^4+P_4^4=48} {TEX} (اعداد سه و چهار رقمی). پس {TEX()} {c=\frac{48\times 10}{4}=120} {TEX}. تعداد اعضای {TEX()} {S} {TEX}که رقم هزارگان دارند برابر است با {TEX()} {P_4^4=24} {TEX}. پس {TEX()} {d=\frac{24\times 10}{4}=60} {TEX}.
پس جواب مسأله برابر است با
@@{TEX()} {\sum_{x\in S}=10^3\times 60+10^2\times 120+10\times 150+160=73660} {TEX}@@
راه حل دیگر برای حل این مسأله این است که چون ارقام 1، 2، 3 و 4 با هم فرق دارند پس میتوان فرض کرد که هر یک از ارقام اعداد عضو{TEX()} { S } {TEX} مقدارشان به طور متوسط {TEX()} {\frac{1+2+3+4}{4}=\frac{5}{2}} {TEX} است. پس میتوان فرض کرد جای اعداد یک رقمی {TEX()} {\frac{5}{2}} {TEX} و جای اعداد دو رقمی {TEX()} {\frac{55}{2}} {TEX} و جای اعداد سه رقمی {TEX()} {\frac{555}{2}} {TEX} و جای اعداد چهار رقمی {TEX()} {\frac{5555}{2}} {TEX} قرار داد. پس
@@{TEX()} {\sum_{x\in S}=P_1^4\times\frac{5}{2}+P_2^4\times\frac{55}{2}+P_3^4\times\frac{555}{2}+P_4^4\times\frac{5555}{2}} {TEX}@@
درحل این مسأله از ایده ((تقارن)) استفاده کردیم که یکی از ایدههای اصلی حل مسایل شمارشی است.
---
!!مثال
با حروف کلمه{TEX()} { wall } {TEX} ، چند کلمه 4 حرفی میتوان ساخت؟
__حل.__
اگر دو حرف{TEX()} { l } {TEX} ، از یکدیگر متمایز بودند، جواب برابر با {TEX()} {4!} {TEX}بود؛ ولی دو حرف{TEX()} { l } {TEX} ، یکسان هستند، چه کار کنیم؟
فرض کنید دو حرف{TEX()} { l } {TEX} به صورت {TEX()} {l_2,l_1} {TEX} در نظر بگیریم. در نتیجه جواب برابر با{TEX()} {4!} {TEX}خواهد بود. ولی چون دو حرف{TEX()} {l_2,l_1} {TEX} یکسان هستند، پس هر حالت را دو با شمردهایم. به عنوان مثال آرایشهای{TEX()} {wal_2l_1,wal_1l_2} {TEX} هر دو کلمه{TEX()} { wall } {TEX} را مشخص میکنند. بنابراین جواب برابر است با {TEX()} {\frac{4!}{2}=12} {TEX} .
توجه کنید این ایده که یک کمیت را بشماریم و بعد ببینیم هرحالت را چندبار حساب کردهایم و با تقسیم تعداد حالات شمرده شده بر تعداد دفعاتی که هر حالت را شمردهایم؛ جواب مسأله را به دست آوریم، در حل خیلی از مسائل به ما کمک میکند.
---
!جایگشتهای با تکرار
فرض کنید{TEX()} { n = n_1 + n_2 +\cdots + n_k } {TEX} باشد. در حالت کلی تعداد کلمات {TEX()} { n } {TEX} حرفی را که با{TEX()} { n_1} {TEX} حرف {TEX()} {a_1} {TEX} ،{TEX()} {n_2} {TEX} حرف {TEX()} {a_2} {TEX}، … و {TEX()} {n_k} {TEX}حرف {TEX()} {a_k} {TEX}، میتوان ساخت با نماد {TEX()} {n\choose {n_1,n_2,\cdots ,n_k}} {TEX} نشان میدهیم که این مقدار برابر است با {TEX()} {\frac{n!}{n_1!n_2!\cdots n_k!} {TEX}.
زیرا فرض کنید تمام حروف متمایز باشند، در نتیجه ما{TEX()} {n!} {TEX}کلمه{TEX()} { n } {TEX} حرفی میتوانیم بسازیم، ولی به خاطر یکسان بودن حروف{TEX()} {a_1} {TEX} ، هر کلمه را {TEX()} {n_1!} {TEX}بار، به خاطر یکسان بودن حروف{TEX()} {a_2} {TEX} ، هر کلمه را {TEX()} {n_2!} {TEX}بار، … و به خاطر یکسان بودن حروف {TEX()} {a_k} {TEX}، هر کلمه را {TEX()} {n_k!} {TEX} بار شمردهایم. بنابراین طبق اصل ضرب هر کلمه را {TEX()} {n_1!n_2!\cdots n_k!} {TEX}بار شمردهایم. پس تعداد آرایشهای کلمه مورد نظر برابر است با {TEX()} {\frac{n!}{n_1!n_2!\cdots n_k!}} {TEX}
به عنوان مثال تعداد آرایشهای کلمه{TEX()} { pepper } {TEX} برابر است با {TEX()} {\frac{6!}{3!2!1!}} {TEX} یا تعداد آرایشهای کلمه{TEX()} { massasauga } {TEX} برابر است با {TEX()} {\frac{10!}{1!4!3!1!}} {TEX} .
---
!!مثال
تعداد اعداد سهرقمی بزرگتر از 530 که ارقام متمایزی دارند کدام است؟
الف. 201 ~~white:---------- ~~ب. 240 ~~white:---------- ~~ج. 345 ~~white:----------~~ د. 335~~white:----------~~هـ.. 336
__حل .__
گزینه (د) صحیح است. ابتدا تعداد اعداد بزرگتر یا مساوی 600 را میشماریم و بعد تعداد اعداد بین 530 و 600 را. تعداد اعداد سه رقمی بزرگتر یا مساوی 600 با ارقام متمایز برابر است با{TEX()} {4\times 9\times 8=288} {TEX}. تعداد اعداد سه رقمی بزرگتر یا مساوی با 530 و کوچکتر از 600 برابر است با {TEX()} {1\times 6\times 8=48} {TEX}. پس تعداد اعداد سه رقمی یا مساوی با 530 با ارقام متمایز برابر است با{TEX()} {288+48=336} {TEX}. حال چون عدد 530 نیز شمرده شده است جواب مسأله برابر است با{TEX()} {336-1=335} {TEX} .
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0020.pdf]
---
!همچنین ببینید
*((جایگشت های دوری ))
#@^