جایگشت

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
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 باقیمانده اقلیدسی
بزرگترین مقسوم علیه مشترک
کوچکترین مضرب مشترک

ترکیباتی

( ) ضریب دوجمله‌ای
P جایگشت
C ترکیب

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

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

ترتیب کلی

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.