ویکی‌پدیا

جایگشت: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
بدون خلاصۀ ویرایش
برچسب‌ها: ویرایش همراه ویرایش از وبگاه همراه ویرایش پیشرفتهٔ همراه
ابرابزار
خط ۱:
[[پرونده:Permutations RGB.svg|بندانگشتی|در هر کدام از شش ردیف، یک جایگشت متفاوت از سه توپ مشخص شده استشده‌است.|200px]]
 
'''جایگشت''' {{انگلیسی|Permutation}} یا '''ترتیب'''، در قلمرو [[ترکیبیات]]ی آن به معنی مرتّب‌سازی یا تغییر ترتیب اعضای یک [[مجموعه (ریاضی)|مجموعه]] می‌باشد. ممکن است این چیدمان خطی یا غیر خطی (مثلاً دور یک دایره، که در این حالت جایگشت دوری نامیده می‌شود) صورت گیرد. اعضای مجموعه نیز می‌توانند هر چیزی باشند؛ مثلاً شیء یا عدد یا حرف و همچنین می‌توانند تکراری باشند یا متمایز. در هر مورد، مهم، تعداد طرق چیدن این اعضا است.
 
== تعریف ==
جایگشت (خطی): هر ترتیب dfsd (خطی) قرار گرفتن n شی در کنار هم را یک جایگشت می‌نامند.
 
در مسایل ترکیبیاتی اکثراً تعداد جایگشت‌ها مد نظر است.
=== رابطه عمومی جایگشت ===
چنان‌چه بخواهیم از میان n شیء، شمار r شیء را برگزینیم و در آن زیرمجموعه، ترتیب هم مهم باشد؛ شمار جایگشت‌ها چنین بدست می‌آید:
{{چپ‌چین}}
<math>{P_r^n} = \frac{n!}{(n-r)!} </math>
{{پایان چپ‌چین}}
 
== محاسبه ==
فرض کنید می‌خواهیم <math> n </math> [[دانش آموز]] (به عنوان اشیا ''متمایز'') را در یک صف قرار دهیم:
{{وسط‌چین}}
<center>
[[پرونده:PermutatiionQueue.jpg]]
{{پایان}}
</center>
در جایگاه اول ممکن است هر یک از <math> n </math> دانش آموز بایستند پس برای مکان اول (ابتدای صف) <math> n </math> حالت مختلف وجود دارد. در جایگاه دوم <math> n-1 </math> دانش آموز باقی‌مانده (به جز دانش آموزی که در جایگاه اول صف ایستاده) می‌توانند قرار بگیرند پس تا اینجا به <math> n\times(n-1) </math> حالت مختلف توانستیم دو مکان اول را با دو دانش‌آموز پر کنیم. به همین ترتیب برای جایگاه سوم:
{{چپ‌چین}}
سطر ۵۰ ⟵ ۵۵:
که همان جایگشت n تایی می‌باشد که با جواب حاصل از انتخاب تمامی n عضو مجوعه n تایی و چیدن آنها در یک ردیف یعنی تبدیل n از n یکی است، که طبق تعاریف ذکر شده این امر واضح است.
 
== جایگشت هایجایگشت‌های با تکرار ==▼
<br />
گاهی اوقات اشیائی که می خواهیممی‌خواهیم جایگشت دهیم، همگی متمایز نیستند و اشیاء یکسان نیز در بین آنها وجود دارد.▼
 
فرض کنید، می خواهیممی‌خواهیم حروف کلمه HELLO را جایگشت دهیم. در نگاه اول پاسخ مسئله برابر <math>5!</math> است زیرا 5۵ حرف وجود دارد. اما در اینجا ما 2۲ حرف L یکسان داریم و تفاوتی بین آنها قائل نمی شویم.نمی‌شویم؛ بنابراین در <math>5!</math> تعدادی از حالات نامطلوب هستند. با توجه به اینکه 2۲ حرف L متمایز را می توانمی‌توان به <math>2!</math> حالت جایگشت داد نتیجه می گیریممی‌گیریم که در <math>5!</math> هر کلمه <math>2!</math> بار شمرده می شودمی‌شود. برای حذف حالات نامطلوب داریم : <math>\frac{5!}{2!}</math>▼
▲== جایگشت های با تکرار ==
▲گاهی اوقات اشیائی که می خواهیم جایگشت دهیم، همگی متمایز نیستند و اشیاء یکسان نیز در بین آنها وجود دارد.
 
▲فرض کنید، می خواهیم حروف کلمه HELLO را جایگشت دهیم. در نگاه اول پاسخ مسئله برابر <math>5!</math> است زیرا 5 حرف وجود دارد. اما در اینجا ما 2 حرف L یکسان داریم و تفاوتی بین آنها قائل نمی شویم. بنابراین در <math>5!</math> تعدادی از حالات نامطلوب هستند. با توجه به اینکه 2 حرف L متمایز را می توان به <math>2!</math> حالت جایگشت داد نتیجه می گیریم که در <math>5!</math> هر کلمه <math>2!</math> بار شمرده می شود. برای حذف حالات نامطلوب داریم : <math>\frac{5!}{2!}</math>
 
=== چند مثال دیگر ===
* 10۱۰ پرتقال یکسان و 5۵ سیب یکسان در اختیار داریم. می خواهیممی‌خواهیم تمام این 15۱۵ میوه را در یک ردیف پشت سر هم قرار دهیم. به چند طریق این کار قابل انجام است؟▼
 
'''پاسخ:''' با توجه به اینکه تمام پرتقال‌ها و تمام سیب‌ها یکسان هستند، همانند توضیحات بالا حالات نامطلوب را از کل حالات کم می‌کنیم: <math>\frac{15!}{10!\times5!}</math>
▲* 10 پرتقال یکسان و 5 سیب یکسان در اختیار داریم. می خواهیم تمام این 15 میوه را در یک ردیف پشت سر هم قرار دهیم. به چند طریق این کار قابل انجام است؟
* سعید میمی‌خواهد خواهد 2۲ پیتزای یکسان، 3۳ همبرگر یکسان و 5۵ نوشابه یکسان را برای شام بخورد. او به چند طریق می تواندمی‌تواند این کار را انجام دهد؟▼
 
'''پاسخ:''' با توجه بهکنید اینکهکه تمام پرتقالغذاهای هاهم و تمام سیب هانوع، یکسان هستند،هستند همانندو توضیحاتفقط بالاترتیب حالاتخوردن نامطلوبغذاها رامهم ازمی‌باشد، کلهمانند حالاتمسائل کمقبل می کنیمداریم: <math>\frac{1510!}{102!\times3!\times5!}</math>
 
▲* سعید می خواهد 2 پیتزای یکسان، 3 همبرگر یکسان و 5 نوشابه یکسان را برای شام بخورد. او به چند طریق می تواند این کار را انجام دهد؟
 
'''پاسخ:''' توجه کنید که تمام غذاهای هم نوع ، یکسان هستند و فقط ترتیب خوردن غذاها مهم می باشد، همانند مسائل قبل داریم: <math>\frac{10!}{2!\times3!\times5!}</math><br />
 
== مثال ==
* به چند طریق می‌توان ۴ کتاب فیزیک، شیمی، ریاضی و [[هندسه]] را کنار هم قرار داد؟ <math>4!=24</math>
 
* به چند طریق میمی‌توان توان۵ 4پسر کتابو فیزیک،۴ شیمی،دختر ریاضیرا ودر [[هندسه]]یک راردیف قرار داد، به طوری که تمام پسرها کنار هم قرارو داد؟تمام دخترها کنار هم باشند؟ <math>42!\times5!\times4!=24</math>
* به چند روش می توانمی‌توان از بین 5۵ نفر، 3۳ نفر را انتخاب کرده و مدال هایمدال‌های طلا، نقره و برنز را به آنها اهدا کرد؟<math>\frac{5!}{(5-3)!}=\frac{5!}{2!}=\binom{5}{3}\times3!</math>▼
* به چند طریق می توان 5 پسر و 4 دختر را در یک ردیف قرار داد، به طوری که تمام پسر ها کنار هم و تمام دختر ها کنار هم باشند؟ <math>2!\times5!\times4!</math>
* به چند روش می توانمی‌توان اعضای مجموعه <math>\{1, 2, ..., 2n\}</math>را جایگشت داد، به طوری که [[اعداد زوج و فرد|اعداد زوج]] در مکان‌های زوج و اعداد فرد در مکان‌های فرد ظاهر شوند؟ <math>n!\times n!=(n!)^2</math>▼
▲* به چند روش می توان از بین 5 نفر، 3 نفر را انتخاب کرده و مدال های طلا، نقره و برنز را به آنها اهدا کرد؟<math>\frac{5!}{(5-3)!}=\frac{5!}{2!}=\binom{5}{3}\times3!</math>
▲* به چند روش می توان اعضای مجموعه <math>\{1, 2, ..., 2n\}</math>را جایگشت داد، به طوری که [[اعداد زوج و فرد|اعداد زوج]] در مکان‌های زوج و اعداد فرد در مکان‌های فرد ظاهر شوند؟ <math>n!\times n!=(n!)^2</math>
 
== جستارهای وابسته ==
خط ۸۲:
* {{یادکرد|کتاب= ترکیبیات|نویسنده= علی رضا علیپور| ناشر= انتشارات فاطمی| شابک=964-318-342-4| سال = اول 1382}}
 
[[رده:اختراع‌های اعراب]]▼
[[رده:ترکیبیات]]
[[رده:جایگشت‌ها]]
سطر ۸۷ ⟵ ۸۸:
[[رده:موضوعات فاکتوریل و دوجمله‌ای]]
[[رده:نظریه احتمالات]]
▲[[رده:اختراع‌های اعراب]]
برگرفته از «https://fa.wikipedia.org/wiki/جایگشت»