جایگشت

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

جایگشت در قلمرو ترکیبیاتی آن به معنی مرتب‌سازی یا تغییر ترتیب اعضای یک مجموعه می‌باشد. ممکن است این چیدمان خطی و یا غیر خطی (مثلاً دور یک دایره که در این حالت جایگشت دوری نامیده می‌شود) صورت گیرد.اعضای مجموعه نیز می‌توانند هر چیزی باشند مثلاً شی یا عدد یا حرف و همچنین می‌توانند تکراری باشند یا متمایز.در هر مورد، مهم، تعداد طرق چیدن این اعضا است.

تعریف[ویرایش]

جایگشت (خطی):هر ترتیب (خطی) قرار گرفتن n شی در کنار هم را یک جایگشت می‌نامند. در مسایل ترکیبیاتی اکثراً تعداد جایگشت‌ها مد نظر است.

محاسبه[ویرایش]

فرض کنید می‌خواهیم n دانش آموز (به عنوان اشیا متمایز) را در یک صف قرار دهیم:

PermutatiionQueue.jpg

در جایگاه اول ممکن است هر یک از n دانش آموز بایستند پس برای مکان اول (ابتدای صف) n حالت مختلف وجود دارد.در جایگاه دوم n-۱ دانش آموز باقی‌مانده (به جز دانش آموزی که در جایگاه اول صف ایستاده) می‌توانند قرار بگیرند پس تا اینجا به (n*(n-۱ حالت مختلف توانستیم دو مکان اول را با دو دانش‌آموز پر کنیم.به همین ترتیب برای جایگاه سوم:

n\times(n-1)\times(n-2)

حالت و برای i امین جایگاه به تعداد:

 n\times(n-1)\times(n-2)\times\dots\times(n-i+1)

حالت داریم. با همین روند تمام n جایگاه را به :

n\times(n-1)\times(n-2)\times\dots\times2\times1

طریق می‌توان با n دانش آموز پر کرد.که همان تعداد روش‌های ایستادن n دانش آموز در یک صف می‌باشد.حاصل ضرب فوق را «جایگشت n شی متمایز» می‌نامند و آن را با نماد n! (خوانده می‌شود n فاکتوریل) نشان می‌دهند.

جایگشت r تایی(تبدیل)[ویرایش]

گاه جایگشت تنها r عضو از کل n عضو مجموعه مد نظر است.در این حالت می‌توان آن را تبدیل r از n نیز نامید.

تعریف[ویرایش]

اگر مجموعه‌ای از n شی در اختیار داشته باشیم، هر آرایش خطی متشکل از r تا از این اشیا، را یک جایگشت r شی از این n شی می‌نامیم.

نماد[ویرایش]

جایگشت r شی از n شی را با نمادهای  \mathbf{P}(n,r) = \mathbf{P}_r^n = {(n)}_r نمایش می‌دهند.

محاسبه[ویرایش]

درست مانند طریقه محاسبه جایگشت‌های n تایی(مربوط به کل مجموعه n تایی)که در بالا انجام گرفت عمل می‌کنیم، با این تفاوت که در اینجا تنها r جایگاه برای قرار گرفتن اشیا موجود است. پس تنها تا مرحله r ام پیش می‌رویم یعنی فقط r شی از n شی را در r مکان داده شده قرار می‌دهیم که با توجه به اثبات فوق، مقدار این جایگشت برار خواهد بود با:

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)!}

{P_r^n} = \frac{n!}{(n-r)!}

همان طور که مشاهده می‌شود داریم:

{P_n^n} = \frac{n!}{0!} = n!

که همان جایگشت n تایی می‌باشد که با جواب حاصل از انتخاب تمامی n عضو مجوعه n تایی و چیدن آنها در یک ردیف یعنی تبدیل n از n یکی است، که طبق تعاریف ذکر شده این امر واضح است.

منابع[ویرایش]

  • عباس ثروتی، سعید نعمتی. ترکیبیات. چاپ اول بهار 1384. انتشارات خوشخوان. ISBN 964-8601-36-4. 
  • علی رضا علیپور. ترکیبیات. چاپ اول 1382. انتشارات فاطمی. ISBN 964-318-342-4. 
عملیات دوتایی
عددی تابعی مجموعه‌ای ساختاری
مقدماتی

+ جمع
تفریق
× ضرب
÷ تقسیم
^ توان

حسابی

div خارج قسمت اقلیدسی
mod باقیمانده اقلیدسی
بزرگترین مقسوم علیه مشترک
کوچکترین مضرب مشترک

ترکیباتی

( ) ضریب بینم
A جایگشت

ترکیب
کانولوشن
جبر مجموعه‌ها

اجتماع
\ مجموعه مکمل
اشتراک
Δ تفاضل متقارن

ترتیب کلی

min کمینه
max بیشینه

توری‌ها

کرانه تحتانی
کرانه فوقانی

مجموعه‌ها

× ضرب دکارتی
اجتماع منفصل
^ توان مجموعه‌ای

گروه‌ها

حاصل‌جمع مستقیم
حاصل ضرب آزاد
produit en couronne

مدول‌ها

ضرب تانسوری
Hom هومومورفیزم
Tor پیچش
Ext extensions

درخت‌ها

enracinement

واریته‌های متصل

# جمع متصل

فضاهای نقطه‌دار

bouquet
smash produit
joint

برداری
(.) ضرب اسکالر
ضرب برداری
جبری
[,] کروشه لی
{,} کروشه پواسون
ضرب خارجی
هومولوژی
cup-produit
حاصل ضرب اشتراک
ترتیبی
+ الحاق
منطق بولی
عطف منطقی فصل منطقی یای انحصاری استلزام منطقی اگر و فقط اگر