اصل شمول و عدم شمول : مثال n مجموعه

۱۳۹۹/۰۲/۲۲ - - علی رضا نقش نیلچی -

فرض کنید n کارت داریم، هر کارت شماره‌ای از ۱ تا n دارد فرض کنید کارت با شمارهٔ m در جای درست قرار دارد اگر mامین کارت باشد. به چند طریق می‌توان کارت‌ها را بُر زد به طوری که حداقل یک کارت در جای درستش قرار داشته باشد؟

Am را مجموعه‌ای از جایگشت بگیرید که کارت با شمارهٔ m در جای درستش قرار دارد. در این صورت تعداد جایگشت‌های مورد نظر (W) برابر است با:

$W={\biggl |}\bigcup _{m=1}^{n}A_{m}{\biggr |}.$

با استفاده از اصل شمول و عدم شمول داریم:

$W=\sum _{m_{1}=1}^{n}\left|A_{m_{1}}\right|{}-\sum _{1\leq m_{1}<m_{2}\leq n}\left|A_{m_{1}}\cap A_{m_{2}}\right|{}+\sum _{1\leq m_{1}<m_{2}<m_{3}\leq n}\left|A_{m_{1}}\cap A_{m_{2}}\cap A_{m_{3}}\right|{}-\cdots {}+(-1)^{p-1}\sum _{1\leq m_{1}<\cdots <m_{p}\leq n}\left|A_{m_{1}}\cap \cdots \cap A_{m_{p}}\right|\cdots .$

هر مقدار $A_{m_{1}}\cap \cdots \cap A_{m_{p}}$ بیانگر مجموعهٔ جایگشت‌هایی است که در آن‌ها p کارت mp، …، m۱ در جای درست قرار دارند. توجه کنید که تعداد جایگشت‌های با p مقدار درست تنها به p بستگی دارد نه به مقادیر $m$ . به عنوان مثال، تعداد جایگشت‌هایی که اولین و سومین و ۱۷امین کارت در جای درست قرار دارند برابر با تعداد جایگشت‌هایی است که ۲امین و ۵امین و ۱۳امین کارت در جای درست قرار دارند. تنها این مهم است که از n کارت ۳ کارت انتخاب شده که در جای درست قرار گیرد. چون به تعداد ${n \choose p}$ مورد در هر مجموع وجود دارد، داریم:

$W={n \choose 1}\left|A_{1}\right|-{n \choose 2}\left|A_{1}\cap A_{2}\right|+{n \choose 3}\left|A_{1}\cap A_{2}\cap A_{3}\right|-\cdots +(-1)^{p-1}{n \choose p}\left|A_{1}\cap \cdots \cap A_{p}\right|\cdots .$

$\left|A_{1}\cap \cdots \cap A_{p}\right|$ تعداد جایگشت‌هایی است که p عنصر دارند که در جای درست قرار گرفته‌اند که برابر است با $(n-p)!$ . بنابراین در نهایت داریم:

$W={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-\cdots +(-1)^{p-1}{n \choose p}(n-p)!\cdots W=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!.$

با توجه به اینکه ${n \choose p}={\frac {n!}{p!(n-p)!}}$ بدست می‌آید:

$W=\sum _{p=1}^{n}(-1)^{p-1}\,{\frac {n!}{p!}}.$

یک جایگشت که در آن هیچ عنصری سر جایش نیست یک پریش نامیده می‌شود. وقتی $n!$ تعداد کل جایگشت‌ها است، احتمال (Q) این که یک جایگشت تصادفی یک پریش باشد برابر است با:

$Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},$

دل نوشته ها ی نقش و آموزش ریاضی

نوشته هائی در باره بازگشت به خود و مسائل ریاضی و آموزش آن

اصل شمول و عدم شمول : مثال n مجموعه

مشخصات وب

موضوعات وب

پیوندها

آرشیو وب

آمارگیر وبلاگ

آمارگیر وبلاگ

کد پربازدیدترین