جایگشت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
ن برچسب‌ها: حذف حجم زیادی از مطالب منبع‌دار ویرایشگر دیداری ویرایش همراه ویرایش از وبگاه همراه |
جز ویرایش 103.28.133.99 (بحث) به آخرین تغییری که HujiBot انجام داده بود واگردانده شد برچسب: واگردانی |
||
خط ۱:
[[پرونده:Permutations RGB.svg|بندانگشتی|Each of the six rows is a different permutation of three distinct balls|200px]]
'''جایگشت''' {{انگلیسی|Permutation}} در قلمرو [[ترکیبیات]]ی آن به معنی مرتب‌سازی یا تغییر ترتیب اعضای یک [[مجموعه (ریاضی)|مجموعه]] می‌باشد. ممکن است این چیدمان خطی یا غیر خطی (مثلاً دور یک دایره که در این حالت جایگشت دوری نامیده می‌شود) صورت گیرد. اعضای مجموعه نیز می‌توانند هر چیزی باشند مثلاً شی یا عدد یا حرف و همچنین می‌توانند تکراری باشند یا متمایز. در هر مورد، مهم، تعداد طرق چیدن این اعضا است.
== تعریف ==
جایگشت (خطی): هر ترتیب dfsd (خطی) قرار گرفتن n شی در کنار هم را یک جایگشت می‌نامند.
در مسایل ترکیبیاتی اکثراً تعداد جایگشت‌ها مد نظر است.
== محاسبه ==
فرض کنید می‌خواهیم n [[دانش آموز]] (به عنوان اشیا ''متمایز'') را در یک صف قرار دهیم:
<center>
[[پرونده:PermutatiionQueue.jpg]]
</center>
در جایگاه اول ممکن است هر یک از n دانش آموز بایستند پس برای مکان اول (ابتدای صف) n حالت مختلف وجود دارد. در جایگاه دوم n-۱ دانش آموز باقی‌مانده (به جز دانش آموزی که در جایگاه اول صف ایستاده) می‌توانند قرار بگیرند پس تا اینجا به (n*(n-۱ حالت مختلف توانستیم دو مکان اول را با دو دانش‌آموز پر کنیم. به همین ترتیب برای جایگاه سوم:
{{چپ‌چین}}
<math>n\times(n-1)\times(n-2)</math>
{{پایان چپ‌چین}}
حالت و برای i امین جایگاه به تعداد: {{چپ‌چین}} <math> n\times(n-1)\times(n-2)\times\dots\times(n-i+1) </math>
{{پایان چپ‌چین}}
حالت داریم.
با همین روند تمام n جایگاه را به:
{{چپ‌چین}}
<math>n\times(n-1)\times(n-2)\times\dots\times2\times1</math>
{{پایان چپ‌چین}}
طریق می‌توان با n دانش آموز پر کرد؛ که همان تعداد روش‌های ایستادن n دانش آموز در یک صف می‌باشد. حاصل ضرب فوق را «جایگشت n شی
متمایز» می‌نامند و آن را با نماد <math>n!</math> (خوانده می‌شود n فاکتوریل) نشان می‌دهند.
== جایگشت r تایی (تبدیل) ==
گاه جایگشت تنها r عضو از کل n عضو مجموعه مد نظر است. در این حالت می‌توان آن را ''تبدیل r از n'' نیز نامید.
=== تعریف ===
اگر مجموعه‌ای از n شی در اختیار داشته باشیم، هر آرایش خطی متشکل از r تا از این اشیا، را یک جایگشت r شی از این n شی می‌نامیم.
=== نماد ===
جایگشت r شی از n شی را با نمادهای <math> \mathbf{P}(n,r) = \mathbf{P}_r^n = {(n)}_r </math> نمایش می‌دهند.
=== محاسبه ===
درست مانند طریقه محاسبه جایگشت‌های n تایی (مربوط به کل مجموعه n تایی) که در بالا انجام گرفت عمل می‌کنیم، با این تفاوت که در اینجا تنها r جایگاه برای قرار گرفتن اشیا موجود است. پس تنها تا مرحله r ام پیش می‌رویم یعنی فقط r شی از n شی را در r مکان داده شده قرار می‌دهیم که با توجه به اثبات فوق، مقدار این جایگشت برابر خواهد بود با:
{{چپ‌چین}}
<math>P_r^n = n\times(n-1)\times\dots\times(n-r+1) = n\times(n-1)\times\dots\times(n-r+1)\times{\frac{(n-r)\times(n-r-1)\times\dots\times2\times1}{(n-r)\times(n-r-1)\times\dots\times2\times1}} = \frac{n!}{(n-r)!} </math>
<math>{P_r^n} = \frac{n!}{(n-r)!} </math>
{{پایان چپ‌چین}}
همان‌طور که مشاهده می‌شود داریم:
{{چپ‌چین}}
<math>{P_n^n} = \frac{n!}{0!} = n! </math>
{{پایان چپ‌چین}}
که همان جایگشت n تایی می‌باشد که با جواب حاصل از انتخاب تمامی n عضو مجوعه n تایی و چیدن آنها در یک ردیف یعنی تبدیل n از n یکی است، که طبق تعاریف ذکر شده این امر واضح است.
{{عملیات دوتایی}}
== منابع ==
{{پانویس}}
* {{یادکرد|کتاب= ترکیبیات|نویسنده= عباس ثروتی، سعید نعمتی| ناشر= انتشارات خوشخوان| شابک=964-8601-36-4|چاپ=اول بهار 1384}}
* {{یادکرد|کتاب= ترکیبیات|نویسنده= علی رضا علیپور| ناشر= انتشارات فاطمی| شابک=964-318-342-4|چاپ=اول 1382}}
[[رده:ترکیبیات]]
| |||