جایگشت (تبدیلات)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 03 شهریور 1400
دسته‌بندی: ترکیبیات (ابزارهای شمارشی)
امتیاز:
بازدید: 32 مرتبه

جایگشتnشی متمایز

ترتیب قرار گرفتن n شی متمایز در یک ردیف را جایگشت n شی متمایز می‌نامند.

بدیهی است که جابه‌جا شدن n شی در یک ردیف نیز به‌همین مفهوم است.

تمرین

حالات مختلفی را که می‌توان حروف a و b و c را در یک ردیف قرار داد، نشان دهید.

جایگشت - تبدیل - پیمان گردلو


بنابراین تعداد جایگشت های این سه حرف برابر 6 حالت می‌باشد.

تمرین

به چند حالت می‌توان اعداد 4  ,  3  ,  2  ,  1 را در یک ردیف قرار داد.

جایگشت - تبدیل - پیمان گردلو


بنابراین تعداد جایگشت های این چهار عدد برابر 24 حالت می‌باشد.

تعداد جایگشتnشی متمایز در یک ردیف (صف)

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

قضیه

تعداد جایگشت n شی متمایز که در یک ردیف قرار گرفته‌اند، برابر n! است.

اثبات

فرض کنید n شی متمایز را می‌خواهیم در یک ردیف که شامل n مکان می‌باشد، قرار دهیم.

در مکان اول می‌توانیم هر یک از n شی را قرار دهیم، یعنی برای پر کردن مکان اول n روش وجود دارد.

در مکان دوم از n-1 شی باقیمانده، انتخاب صورت می‌گیرد. 

در مکان سوم از n-2 شی باقیمانده، انتخاب صورت می‌گیرد. 

به‌همین ترتیب:

در مکان nام از n-2 فقط یک شی برای قرار دادن وجود دارد.

جایگشت - تبدیل - پیمان گردلو

لذا طبق اصل ضرب، تعداد جایگشت های n شی متمایز برابر است با: 

n×(n1)×(n2)××1=n!

تمرین

به چند طريق می‌توان شش دانش آموز را در يک صف قرار داد؟

مطابق قضيه تعداد جايگشت ها، شش دانش آموز به تعداد حالات زیر می‌توانند كنار هم بايستند:

6!=720

تعداد راه هايی را به‌دست آوريد كه در يک مهمانی، يک گروه هفت نفری را می‌توان در يک رديف هفت تايی در صندلی مرتب كرد. 

7×6×5×4×3×2×1=7!

تعداد راه هايی را به‌دست آوريد كه می‌توان چهار كتاب رياضی، سه كتاب تاريخ، سه كتاب شيمی و دو كتاب جامعه شناسی را در يک قفسه طوری مرتب كرد كه كتاب‌های هم موضوع كنار يک‌ديگر قرار گيرند.

کتاب‌های ریاضی، تاریخ، شیمی، جامعه شناسی را طناب پیچ می‌کنیم، پس چهار شی داریم که به 4! در کنار هم قرار می‌گیرند.


اما کتاب‌های ریاضی خود به 4! طریق، کتاب‌های تاریخ به 3! طریق، کتاب‌های شیمی به 3! و کتاب‌های جامعه شناسی به 2! طریق، جابه‌جا می‌شوند:


طبق اصل ضرب داریم:

4!×4!×4!×3!×2!

دریافت مثال

نکته

1- تعداد جایگشت n شی متمایز که r شی معین، کنار هم قرار دارند برابر است با:

r!(nr+1)!

2- تعداد جایگشت n شی متمایز که r شی معین، کنار هم قرار ندارند برابر است با:

n!r!(nr+1)!

دریافت مثال

تعداد جایگشتnشی متمایز در یک صف دایره‌ای

قضیه

تعداد جایگشت n شی متمایز که در یک صف دایره‌ای قرار گرفته‌اند، برابر است با:

(n1)!

اثبات

در یک صف دایره‌ای مکان اول، دوم و .... معنی ندارد، یعنی جای قرار گرفتن اشیا اهمیتی ندارد، بلکه قرار گرفتن هر شی در میان دو شی دیگر مهم است.

برای محاسبه تعداد جایگشت n شی متمایز در یک صف دایره‌ای، کافی است جای یک شی را ثابت نگه داریم و n-1 شی باقیمانده را به (n1)! روش جابه‌جا کنیم. 

تمرین

به چند طريق هفت نفر می‌توانند دور يک ميز گرد، بنشينند؟

نفر اول می‌تواند دور ميز گرد و هر مكانی بنشيند، آن‌گاه شش نفر ديگر به تعداد حالات زیر می‌توانند دور يک ميز گرد، بنشينند:

6×5×4×3×2×1=6!

دریافت مثال

جایگشت با اشیای تکراری

قضیه

جایگشت n شی که شامل k نوع می‌باشند، به‌طوری‌که m1 تا از این n شی از نوع اول،  m2 تا از این n شی از نوع دوم و ....و  mk تا از این n شی از نوع kام باشند و i=1kmi=n آن‌گاه:   

n!m1!×m2!××mk!

اثبات

می‌دانیم جایگشت n شی متمایز n! است ولی چون m1 تا از این اشیا، از یک نوع می‌باشند پس در n! حالت یک شی m1 بار تکرار شده است و چون این اشیا به m1! می‌توانند در یک ردیف بین خود جابه‌جا شوند لذا m1! از n! حالت یکسان است.      

به‌همین ترتیب شی نوع دوم m2 بار تکرار شده، لذا m2! از n! حالت یکسان می‌باشد.   

بنابراین اگر تا شی kام بررسی را انجام دهیم، تعداد جایگشت های n شی برابر است با: 

n!m1!×m2!××mk!

تمرین

چند عدد ده رقمی می‌توان با ارقام زیر نوشت:

2,2,3,3,3,3,5,5,5,5

دو شی از عدد 2 داریم یعنی m1=2.


چهار شی از عدد 3 داریم یعنی m2=4.


چهار شی از عدد 5 داریم یعنی m3=4.

n=m1+m2+m3=10n!m1!m2!m3!=10!2!×4!×4!

دریافت مثال

جایگشتrشی ازnشی (تبدیلrتایی)

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

در تبدیل r تایی با جابه‌جا کردن r شی یک حالت جدید به دست می‌آید، به‌عبارت دیگر تقدم و تاخر اشیا اهمیت دارد.

تمرین

با استفاده از مجموعه S=a,b,c,d جایگشت های مختلفی را در زیر بررسی کنید:

جایگشت هایی از چهار حرف که تمام حرف‌ها در یک زمان انتخاب شده‌اند.

bdca  ,  dcba  ,  acdb

جایگشت هایی از چهار حرف که سه حرف در یک زمان انتخاب شده‌اند. 

bad  ,  adb  ,  cbd  ,  bca

جایگشت هایی از چهار حرف که دو حرف در یک زمان انتخاب شده‌اند.

ad  ,  cb  ,  da  ,  bd

دریافت مثال

قضیه

تعداد جایگشت های r تایی n شی که با نماد pn,r نمایش داده می‌شود و به‌صورت زیر است:

p(n,r)=n(n1)(n2)(nr+1)=n!(nr)!

اثبات

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

عضو اول در این جایگشت را می‌توان به n راه مختلف انتخاب کرد.

عضو دوم در این جایگشت را می‌توان به n-1 راه مختلف انتخاب کرد.

عضو سوم در این جایگشت را می‌توان به n-2 راه مختلف انتخاب کرد.

به‌همین ترتیب: 

عضو rام یعنی عضو آخر را در این جایگشت می‌توان با n(r1)=nr+1 راه مختلف انتخاب کرد. 

بنابر اصل شمارش:

p(n,r)=n(n1)(n2)...(nr+1)=n(n1)(n2)...(nr+1)(nr)!(nr)!=n!(nr)!

نکته

if   r=np(n,n)=n!(nn)!=n!0!=n!

یعنی n! تعداد جایگشت n شی است که تمام آنها در یک زمان انتخاب می‌شود.  

به عبارت دیگر داریم:

Pn,n=n×n1×n2××1=n!

دریافت مثال

قضیه

تعداد جایگشت های r تایی n شی که یک شی خاص در همه آنها موجود باشد، برابر است با:

r.p(n1,r1)

اثبات

قرار دادن آن شی خاص در یکی از r مکان موجود (برای جایگشت r تایی) به r روش صورت می‌گیرد، بنابراین r-1 مکان دیگر باید با n-1 شی باقیمانده پر شوند، که جایگشت r-1 تایی n-1    شی است و برابر با p(n1,r1) لذا طبق اصل ضرب، تعداد جایگشت های مطلوب عبارت است از:

r.p(n1,r1)

نکته

به‌طور کلی تعداد جایگشت های r تایی n شی که در همه آنها k شی خاص موجود باشد، برابر است با:  

p(r,k)×p(nk,rk)    ;    (krn)

دریافت مثال

قضیه

تعداد جایگشت های r تایی n شی متمایز که فاقد k شی خاص می باشند، برابر است با: 

p(nk,r)    ;    (rnk)

اثبات

برای اثبات کافی است سوال را این‌گونه در نظر بگیریم که چند جایگشت r تایی می‌توان با n شی متمایز که فاقد k شی خاص است یعنی n-k تشکیل داد که این عمل به p(nk,r) طریق امکان پذیر است. 

دریافت مثال

قضیه

تعداد توابع یک‌به‌یک از یک مجموعه r عضوی به یک مجموعه n عضوی برابر با جایگشت r تایی از n می‌باشد، یعنی:  

N=p(n,r)    ;    (n>r)

اثبات

دو مجموعه A=a1  ,  a2  ,  ...  ,  ar و B=b1  , b 2  ,  ...  ,  bn را در نظر می‌گیریم، تابع یک‌به‌یک تابعی است که هر عضو از مجموعه A را با یک و فقط یک عضو از مجموعه B متناظر می‌کند، به‌عبارت دیگر هیچ زوج مرتبی یافت نشود که مولفه‌های دومش با هم برابر باشند، بنابراین:  

اولین عضو مجموعه A با یکی از n عضو مجموعه B متناظر خواهد بود، برای این انتخاب n روش وجود دارد.   

دومین عضو مجموعه A با یکی از n-1 عضو باقیمانده مجموعه B متناظر می‌شود. 

به‌همین ترتیب rامین عضو مجموعه A با یکی از n-r+1 عضو باقیمانده مجموعه B متناظر می‌گردد.   

بنابراین طبق اصل ضرب تعداد توابع یک‌به‌یک از مجموعه r عضوی A به مجموعه n عضوی B برابر است با:   

p(n,r)=n(n1)(n2)(nr+1)=n(n1)(n2)(nr+1)(nr)!(nr)!=n!(nr)!

نکته

1- تعداد توابع یک‌به‌یک از یک مجموعه n عضوی به یک مجموعه n عضوی دیگر برابر n! است. 

p(n,n)=n!(nn)!=n!0!=n!1=n!

2- تعداد توابع یک‌به‌یک از یک مجموعه r عضوی به یک مجموعه n عضوی که r>n صفر می‌باشد.

دریافت مثال

فرمول استرلینگ

وقتی n بزرگ است n! را می‌توان به‌وسیله عبارت زیر که فرمول استرلینگ خوانده می‌شود، تقریب کرد:

2πnnen

در این فرمول، e پایه لگاریتم طبیعی است.

تمرین

با استفاده از فرمول استرلینگ 10!را به طور تقریبی محاسبه کنید.

20π10e10=3/598/696

با استفاده از جدول، مقدار دقیق 10! چقدر است؟

با استفاده از جدول، مقدار دقیق 10! برابر است با 3/628/800   

درصد خطای محاسبه توسط فرمول استرلینگ چقدر است؟

3628800359869636288000/83%

تمرین

با استفاده از فرمول استرلینگ، مقدار اعداد زیر را محاسبه کنید. 

52!

52!104π52e528/052902017×1067

13!

13!26π13e136187239475

39!

39!78π39e392/035434435×1046

تمرین

با استفاده از فرمول استرلینگ تساوی زیر را ثابت کنید.

limn2nnπn22n=1

2nn=2n!n!22nnnπ22n=2n!nπ22nn!24πn2ne2n.πn22n2πnnen2=2n2n+1.e2n.π2n2n+1.e2n.π=1


بنابراین:

limn2nnnπ22n=1

مثال‌ها و جواب‌ها

جایگشت (تبدیلات)

9,000تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید