آشنایی با جایگشت‌ها
آشنایی با جایگشت‌ها

ریاضیات

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

در ریاضیات، (همانطور که گفتیم) جایگشت (Permutation) عملی است که اعضای یک مجموعه را در یک ترتیب صف می دهیم. در جایگشت‌ها بر خلاف مجموعه‌ها ترتیب و نحوه‌ی قرارگیری اشیا مهم و تاثیر گذار است. به عنوان مثال، شش جایگشت از مجموعه اشیا {1،2،3} وجود دارد:

(1،2،3) ، (1،3،2) ، (2،1،3) ، (2،3،1) ، (3،1،2) ، (3،2،1)

در شکل فوق، توپ‌های قرمز و سبز و آبی، به ترتیب نماینده‌ی اعداد 1 و 2 و 3 هستند.

این‌ها همه جایگشت‌های ممکن این مجموعه سه عضوی است. مطالعه جایگشت مجموعه‌های n عضوی مبحث مهمی در زمینه ترکیبیات می‌باشد. جایگشت‌ها تقریباً در هر شاخه ریاضیات و در بسیاری از زمینه‌های دیگر علوم مورد مطالعه قرار می‌گیرند. به عنوان چند مثال، جایگشت‌ها در علم کامپیوتر برای تجزیه و تحلیل الگوریتم‌های مرتب سازی استفاده می‌شوند. در فیزیک کوانتومی، برای توصیف حالات ذرات و در زیست شناسی ، برای توصیف توالی RNA.
فرض کنید می‌خواهیم n نفر (به عنوان n شی متمایز!) را در یک صف قرار دهیم و می‌خواهیم بدانیم به چند طریق می‌توان این کار را انجام داد. برای شمردن تعداد راه‌های انجام این کار، طبیعی است که n جایگاه را در نظر بگیریم و بررسی کنیم که در هر جایگاه چند نفر می‌توانند قرار بگیرند. یعنی برای قرار گیری یک فرد در هر جایگاه چند انتخاب وجود دارد. برای این کار به n جایگاه زیر دقت کنید:

در جایگاه اول چند نفر می‌توانند قرار بگیرند؟ n نفر داریم که هر کدام می‌توانند انتخابی برای این کار باشند. پس برای انجام این کار، n انتخاب وجود دارد و به n حالت می‌توان انتخاب کرد که چه کسی در این جایگاه بنشیند؟ برای جایگاه دوم چطور؟ از n نفر اولیه، 1 نفر در جایگاه اول نشسته است. پس در جایگاه دوم، n-1 نفر می‌توانند بنشینند، یعنی n-1 انتخاب داریم. (دقت کنید، فردی که در جایگاه اول نشسته است، دیگر نمی‌تواند در جایگاه دوم نیز قرار بگیرد.) اگر به همین ترتیب ادامه دهیم، برای نفر آخر صف، یک انتخاب بیشتر وجود ندارد. پس طبق اصل ضرب، پاسخ این مسئله برابر !n×(n1)×(n2)×...×1=n می‌باشد.

به عنوان مثال، تعداد جایگشت‌های با حروف کلمه Iran برابر است با 24=!4. زیرا برای انتخاب اولین حرف در جایگشت (چهار تایی) 4 انتخاب، برای انتخاب دومین حرف در جایگشت، 3 انتخاب و برای انتخاب حروف سوم و چهارم، به ترتیب 2 و 1 انتخاب داریم. همینطور تعداد جایگشت‌های با حروف کلمه olympiad که در آن، حرف اول حتما صدادار باشد، برابر است با !7×4. زیرا برای انتخاب اولین حرف در جایگشت (هشت تایی) 4 انتخاب (یکی از حروف o,y,i,a)، برای انتخاب دومین حرف در جایگشت 7 انتخاب (8 حرف داشتیم که یکی از آن‌ها استفاده شده است) و به همین ترتیب برای انتخاب بقیه‌ی حروف، 1،2،3،4،5،6 انتخاب داریم.

برای تمرین بیشتر، به مثال زیر نیز توجه نمایید.

به چند روش می‌توان 7 دختر و ۵ پسر را در یک ردیف قرار دارد؛ طوری که همه‌ی دخترها کنار هم قرار بگیرند؟ با کمی دقت، می‌توان در ابتدا تمام دخترها با هم به عنوان یک شیء بزرگ در نظر بگیریم. به این ترتیب، ۶ شیء مختلف شامل ۵ پسر یک شی که تمام دخترها با هم در آن هستند، داریم. تعداد جایگشت‌های این اشیا !6 است. دقت کنید خود دخترها نیز میان خود !7 ترتیب دارند. این یعنی طبق اصل ضرب پاسخ سوال برابر با !7×!6 می‌باشد.

 

تاریخچه‌ای مختصر از بررسی جایگشت‌ها

آل خلیل (717-786, Al-Khalil)، ریاضیدان و رمزنگار عرب، کتاب پیام‌های رمزنگاری را نوشت. این کتاب شامل اولین استفاده از جایگشت‌ها و ترکیبات، برای لیست کردن کلمات عربی ممکن با و بدون مصوت‌ها است. قانون تعیین تعداد جایگشت‌ها از اشیاء در فرهنگ هند در حدود 1150 شناخته شده بود. کتاب Lilavati که توسط ریاضیدان هندی Bhaskara نوشته شده است، شامل یک قطعه است که ترجمه آن به این شرح است:

محصول ضرب سری حسابی که با وحدت آغاز و افزایش می یابد و تا تعداد مکان ها ادامه می یابد ، تغییرات تعداد با ارقام خاص خواهد بود.

  
مقاله‌ی قبلی »
« مقاله‌ی بعدی
دیگر مقالات سایت
اختلاف با نوجوان و حل آن

اختلاف با نوجوان و حل آن

حتما برای شما هم اتفاق افتاده است که در مورد مسئله ای با نوجوان خود به اختلاف برسید، مثلا نوجوان شما با دوستی رفت و آمد دارد که از نظر شما فرد مناسبی نیست. این آغاز بگو مگو ها خواهد بود و جنگ در می گیرد. هرچه شما از آن دوست بدگویی می کنید، فرزند شما بیشتر از او دفاع می کند و گاهی فکر می کنید اوضاع برعکس پیش می رود و نه تنها او را از آن فرد جدا نکرده اید بلکه باعث تعصب بیشر نوجوان خود نسبت به آن فرد شده اید.

چرا بعضی‌ها باهوش‌تر هستند؟

چرا بعضی‌ها باهوش‌تر هستند؟

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

شما جزو کدام گروه از والدین هستید؟

شما جزو کدام گروه از والدین هستید؟

در برخورد با فرزندتان، به چه شکل برخورد می‌کنید؟