کلاس تخصصی المپیاد زیست شناسی، کمپبل تابستان 99 لینک خبرها
دسته‌بندی:   ریاضیات

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

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

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

در ریاضیات، (همانطور که گفتیم) جایگشت (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 نوشته شده است، شامل یک قطعه است که ترجمه آن به این شرح است:

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

  
مقاله‌ی قبلی »
« مقاله‌ی بعدی
دیگر مقالات سایت
لوئی پاستور، مرد واکسیناسیون

لوئی پاستور، مرد واکسیناسیون

لوئی پاستور (Louis Pasteur) متولد 27 دسامبر 1822 در دُل فرانسه، متوجه شد كه میكروب ها مسئول ترشح الكل هستند و به فرآیند پاستوریزاسیون رسید، جایی كه باكتری ها با گرم كرد...

گالوا، نبوغ در مقابل حماقت (3)

گالوا، نبوغ در مقابل حماقت (3)

اگر جسمی لازم است که مردم را به قیام وادارد من حاضرم خود را تقدیم کنم. -گالوا-

کارل فریدریش گاوس، پادشاه ریاضیات (1)

کارل فریدریش گاوس، پادشاه ریاضیات (1)

(قسمت اول)
تکامل تدریجی و توسعه منظم دانش حساب و تقریباً تمام آنچه در ریاضیات قرن ما (قرن 19 میلادی) افکار بدیعی بوده است که به وسیله گاوس داده شد. -لئوپولدکرونکر-...