جایگشت

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
Each of the six rows is a different permutation of three distinct balls

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

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

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

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

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

PermutatiionQueue.jpg

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

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

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

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

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

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

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

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

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

جایگشت r شی از n شی را با نمادهای نمایش می‌دهند.

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

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

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

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

عملیات دوتایی
عددی تابعی مجموعه‌ای ساختاری
مقدماتی

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

حسابی

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

ترکیباتی

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

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

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

ترتیب کلی

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

توری‌ها

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

مجموعه‌ها

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

گروه‌ها

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

مدول‌ها

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

درخت‌ها

enracinement

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

# جمع متصل

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

bouquet
smash produit
joint

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

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

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