ترکیب و کاربرد آن در پیدا کردن زیر مجموعه ها
تعداد زیر مجموعه های k عضوی یک مجموعه n عضوی
می دانیم که جابجایی اعضا در مجموعه ها ، مجموعه جدیدی ایجاد نمی کند ، اما هر گاه بخواهیم یک زیر مجموعه ای k عضوی برای n عضو مجموعه ایجاد کنیم ، این کار به[math]\binom{n}{k}[/math] روش قابل انجام است .
مثال 1:
الف)تعداد زیر مجموعه های 5 عضوی از مجموعه 26 حرف انگلیسی برابر است با :[math]\binom{26}{5}[/math]
ب)تعداد زیر مجموعه های 5 عضوی حروف انگلیسی که حرف a در آنها است :
چون حرف a انتخاب شده است پس ما اینجا 25 حرف برای ما باقی می ماند از طرف دیگر از 5 حرفی که باید انتخاب کنیم یکی انتخاب شده و ثابت است (حرف a )
—- | —– | —- | —- | a |
پس در واقع جواب ما انتخاب 4 حرف از میان 25 حرف باقی مانده است : [math]\binom{25}{4}[/math]
پ)تعداد زیر مجموعه های 5 حرفی از مجموعه حروف انگلیسی که حرف a در انها نیست .
چون گفته حرف a نباید باشد پس از 26 حرف یک حرف یعنی a را حذف می کنیم پس اینجا ما باید از میان 25 حرف ما 5 حرف را انتخاب کنیم پس جواب ما : [math]\binom{25}{5}[/math]
با توجه به این مثالی که حل کردیم نتیجه می گیریم که :
اگر A یک مجموعه n عضوی باشد و a هم عضوی از این مجموعه باشد ([math] a\in A [/math])
الف ) تعداد زیر مجموعه های r عضوی مجموعه A برابر است با : [math]\binom{n}{r}[/math]
ب)تعداد زیر مجموعه های r عضوی که a در آنها است (باید شامل a باشد) برابر است با :[math]\binom{n-1}{r-1}[/math]
پ)تعداد زیر مجموعه های r عضوی A که a در آنها نیست (فاقد a هستند) برابر است با :[math]\binom{n-1}{r}[/math]
با توجه به توضیح بالا ،
تعداد زیر مجموعه های فاقد a + تعداد زیر مجموعه های شامل a | = | تعداد زیر مجموعه های r عضوی مجموعه A
|
[math] \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r} [/math]
ما تساوی بالا را در مورد یک عضو ثابت کردیم حالا می خواهیم بصورت کلی در مورد k عضو مطرح کنیم.
ما تساوی بالا را در مورد یک عضو ثابت کردیم حالا می خواهیم بصورت کلی در مورد k عضو مطرح کنیم.
تعداد زیر مجموعه های r عضوی از مجموعه A که شامل k عضو هستند(k عضو حتما باید باشند) برابر است با : [math]\binom{n-k}{r-k}[/math]
تعداد زیر مجموعه های r عضوی از مجموعه A که فاقد k عضو هستند (k عضو نباید در آنها باشند) برابر است با : [math]\binom{n-k}{r}[/math]
پس تساوی زیر در ترکیبیات همیشه برقرار می شود که :
[math] \binom{n}{r}=\binom{n-k}{r-k}+\binom{n-k}{r} [/math]
مثال 2: یک مجموعه 8 عضوی چند زیر مجموعه 4 عضوی دارد ؟
[math]\binom{8}{4}=\frac{8!}{(8-4)!4!}=\frac{8\times4!}{4!\times4!}=70[/math]
مثال 3:یک مجموعه n عضو ی، 55 زیر مجموعه n-2 عضوی دارد ، n کدام است ؟
[math]\binom{n}{n-2}=55\Rightarrow\frac{n!}{(n-2)!(n-(n-2))!}=55\\\\\frac{n(n-1)(n-2)!}{(n-2)!(n-n+2)!}=55\Rightarrow\frac{n(n-1)}{2!}=55\\\\\frac{n(n-1)}{2}=55 \Rightarrow n(n-1)=110 \Rightarrow n(n-1)=11\times10 \longrightarrow n =11[/math]
مثال 4:تعداد زیر مجموعه های 8 عضوی یک مجموعه 2 برابر تعداد زیر مجموعه های 7 عضوی آن است .این مجموعه چند عضو دارد ؟
[math]\binom{n}{8}=2\binom{n}{7} \Longrightarrow \frac{n!}{8!(n-8)!}=\frac{2n!}{7!(n-7)!}\\\\\frac{1}{8}=\frac{2}{n-7} \Longrightarrow n-7=16 \Longrightarrow n=23[/math]