پریش

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ترکیبیات یک پریش یک جایگشت است که هیچ کدام از عناصر در مکان اصلی خود نمی‌باشند در حقیقت یک رابطهٔ F وجود دارد از مجموعهٔ S به خودش بدون آن که هیچ عضوی با خودش رابطه داشته باشد یعنی برای همهٔ xهای عضو S داریم (F(x مخالف x است . و یک مشکل تکراری محاسبهٔ تعداد پریش‌ها است مشکل شمارش پریش‌ها اولین بار در سال ۱۷۰۸ توسط Pierre Reymond بررسی شد و البته همزمان Nicholas Bernoulli روی این موضوع کار می‌کرد.

مثال‌ها[ویرایش]

فرض کنید یک استاد می خواهد ۴ تا آزمون را بین ۴ تا دانشجو تقسیم کند که دانشجوی A آزمون A و دانشجوی B هم آزمون B را بدهد و D و C هم همین طور ولی پروفسور هنگام پخش برگه‌ها دچار اشتباه می‌شود و اکنون هیچکدام از دانشجویان برگهٔ خود را ندارد چندین راه برای برگه‌ها در دست دانشجویان وجود دارد؟ از میان ۲۴ تا جایگشت فقط ۹تا از آن‌ها پریش هستند.

BADC, BCDA, BDAC ,CADB, CDAB, CDBA ,DABC, DCAB, DCBA

و در هر کدام از جایگشت‌های دیگر حداقل یکی از دانشجویان برگهٔ خودش را دارد. و یا مثلاً می‌توان مسئله را این چنین بیان کرد کهn تا نامه داریم که نامهٔ۱ باید به نفر اول و نامهٔ۲ به نفر دوم و ... برسد و اگر پستچی دچار اشتباه شود به چند طریق ممکن است هیچکس نامهٔ خودش را نگیرد؟باز هم محاسبهٔ پریش !

شمارش پریش‌ها[ویرایش]

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

\tbinom{n}{1}(n-1)!=\tfrac{n!}{1!}

و اکنون می بینیم جایگشت هایی که دو تا از آن‌ها در جای خودشان هستند دو بار کم شده‌اند پس طبق اصل شمول و عدم شمول یک بار دیگر آن‌ها را جمع می کنیم که تعداد آن‌ها برابر است با

\tbinom{n}{2}(n-2)!=\tfrac{n!}{2!}

و به همین ترتیب داریم... پس تعداد کل پریش‌ها برابر است با

D(n)= n!-\tfrac{n!}{1!}+\tfrac{n!}{2!}-...+(-1)^n\tfrac{n!}{n!}

D(n)= n!(1-\tfrac{1}{1!}+\tfrac{1}{2!}-...+(-1)^n\tfrac{1}{n!})

محاسبهٔ تعداد پریش‌ها وقتیn به سمت \infty میل می‌کند[ویرایش]

وقتی n به سمت \infty میل می‌کند آن گاه مقدار

D(n)= 1-\tfrac{1}{1!}+\tfrac{1}{2!}-...+(-1)^n\tfrac{1}{n!}

به سمت \tfrac{1}{e} می‌رود پس تعداد کل پریش‌ها برابر می‌شود با \tfrac{n!}{e}

پیوند بیشتر[ویرایش]

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