سرفصل‌های این مبحث

ترکیبیات (ابزارهای شمارشی)

افراز

آخرین ویرایش: 16 بهمن 1403

دسته‌بندی: ترکیبیات (ابزارهای شمارشی)

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

در این بخش، برای آشنایی اولیه با مفهوم افراز به این لینک مراجعه کنید.

در بسیاری از موارد با مسائلی مواجه می‌شویم که می‌خواهیم یک مجموعه $n$ عضوی را به $r$ زیرمجموعه به‌گونه‌ای تقسیم کنیم که:

اجتماع آنها برابر مجموعه مفروض باشد.
اشتراک دوبه‌دوی آنها تهی باشد و هیچ‌کدام از زیر مجموعه‌ها، تهی نباشد.

تمرین

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

$A = \{1, 2, 3, 4, 5\}$

$\begin{array}{l} \{\{1, 2, 3, 4\}, \{5\}\} \\ \{\{1, 2, 3, 5\}, \{4\}\} \\ \{\{1, 2, 4, 5\}, \{3\}\} \\ \{\{1, 3, 4, 5\}, \{2\}\} \\ \{\{2, 3, 4, 5\}, \{1\}\} \end{array}$

در تمرین فوق:

به مجموعه $\{\{1, 2, 3, 4\}, \{5\}\}$ یک گردایه و به $\{5\}$ یک حجره می‌گویند.

همان‌طور که ملاحظه می‌کنید، تعداد حالت‌های مختلفی که یک مجموعه $5$ عضوی را به دو گروه می‌توان تبدیل نمود برابر با $5$ است و چون ترتیب قرار گرفتن عضوهای هر مجموعه در داخل مجموعه مهم نیست.

بنابراین می‌توان گفت که تعداد حالت‌های مختلفی که یک مجموعه $5$ عضوی را می‌توان، به دو گروه تقسیم نمود که در یک گروه یک عضو و در گروه دیگر چهار عضو باشد، برابر است با تعداد تبدیل های $5$ شی که $4$ شی آن از یک نوع و یک شی دیگر از نوع دوم باشد، به‌عبارت دیگر این تعداد برابر است با:

$(\begin{array}{l} 5 \\ 4, 1 \end{array}) = \frac{5!}{4! 1!} = 5$

قضیه

تعداد طریقی که می‌توان یک مجموعه $n$ عضوی را به $r$ دسته تقسیم کرد به‌طوری که در دسته اول $n_{1}$ عضو و در دسته دوم $n_{2}$ عضو و .... و در دسته $r$ ام، $n_{r}$ عضو قرار گیرند، برابر است با:

$(\begin{matrix} n \\ n_{1}, n_{2}, ..., n_{r} \end{matrix}) = \frac{n!}{n_{1}! n_{2}! ... n_{r}!}; n_{1} + n_{2} + \dots + n_{r} = n$

اثبات

افراز مرتب مختلف از مجموعه $S$ به‌صورت $[A_{1}, A_{2}, ..., A_{r}]$ وجود دارد که در آن $A_{1}$ شامل $n_{1}$ عضو و .... و $A_{r}$ شامل $n_{r}$ عضو است.

برای تعیین $A_{1}$ به تعداد $(\begin{matrix} n \\ n_{1} \end{matrix})$ راه موجود است.

برای تعیین $A_{2}$ به تعداد $(\begin{matrix} n - n_{1} \\ n_{2} \end{matrix})$ راه موجود است.

برای تعیین $A_{3}$ به تعداد $(\begin{matrix} n - n_{1} - n_{2} \\ n_{3} \end{matrix})$ راه موجود است.

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

$\begin{array}{l} (\begin{array}{l} n \\ n_{1} \end{array}) (\begin{matrix} n - n_{1} \\ n_{2} \end{matrix}) (\begin{matrix} n - n_{1} - n_{2} \\ n_{3} \end{matrix}) \dots \end{array}$

$\begin{array}{l} = \frac{n!}{n_{1}! (n - n_{1})!} \frac{(n - n_{1})!}{n_{2}! (n - n_{1} - n_{2})!} \times \frac{(n - n_{1} - n_{2})!}{n_{3}! (n - n_{1} - n_{2} - n_{3})!} \dots \end{array}$

$\begin{array}{l} = \frac{n!}{n_{1}! n_{2}! \dots n_{r}!} \end{array}$

$= (\begin{matrix} n \\ n_{1}, n_{2}, ..., n_{r} \end{matrix})$

تمرین

در یک کلاس، دوازده دانشجو وجود دارند، تعداد راه‌هایی را به‌دست آورید که بتوان سه آزمون متفاوت از این دوازده دانشجو گرفت به‌طوری‌که از هر چهار دانشجو یک آزمون به عمل آید.

روش اول-

تعداد افرازهای مرتبی از دوازده دانشجو را جستجو می‌کنیم که هر زیر مجموعه شامل چهار دانشجو است:

$(\begin{array}{l} 12 \\ 4, 4, 4 \end{array}) = \frac{12!}{4! 4! 4!}$

روش دوم_

$(\begin{array}{l} 12 \\ 4 \end{array}) (\begin{array}{l} 8 \\ 4 \end{array}) (\begin{array}{l} 4 \\ 4 \end{array})$

تعداد راه‌هایی را به‌دست آورید که نه اسباب بازی را می‌توان به‌صورت برابر بین سه بچه افراز کرد.

$(\begin{array}{l} 9 \\ 3, 3, 3 \end{array}) = \frac{9!}{3! 3! 3!}$

تعداد راه هایی را به‌دست آورید که نه دانشجو را به سه تیم به ترتیب با چهار، سه و دو دانشجو افراز شوند.

$(\begin{array}{l} 9 \\ 4, 3, 2 \end{array}) = \frac{9!}{4! 3! 2!} = 1260$

قضیه

قضیه بازگشتی $S (n, r)$

فرض کنید $n > 0$ و $1 \leq r \leq n$ باشد، تعداد افرازهای $r$ مجموعه ای یک مجموعه $n$ عضوی را با $S (n, r)$ نمایش می‌دهیم.

1- همواره $S (n, 1) = S (n, n) = 1$

2- اگر $n, r \in N$ و $n \geq 3$ و $2 \leq r \leq n - 1$ باشد، آن‌گاه:

$S (n, r) = S (n - 1, r - 1) + r S (n - 1, r)$

اثبات

1- افرازهای یک مجموعه ای $A$ عبارت است از $\{A\}$ و افرازهای $n$ مجموعه ای $A$ عبارت است از مجموعه های تک عضوی $A$ ، بنابراین:

$S (n, 1) = S (n, n) = 1$

2- ابتدا فرض کنید یک عضو دل‌خواه $a \in A$ را بر داریم، مجموعه باقیمانده را $B$ می‌نامیم و $B$ دارای $n - 1$ عضو است.

افرازهای $(r - 1)$ مجموعه ای وC این مجموعه را می نویسیم.

اکنون به هر یک از افرازهای $(r - 1)$ مجموعه ای $B$ مجموعه $\{a\}$ را می افزائیم که حاصل، یک افراز $r$ مجموعه ای $A$ خواهد شد.

از این طریق به تعداد $S (n - 1, r - 1)$ افراز $r$ مجموعه ای برای $A$ از این طریق حاصل می‌شود بنابراین:

$S (n, r) = S (n - 1, r - 1) + r S (n - 1, r)$

نکته

عدد $S (n, r)$ به عدد استرلینگ نوع دوم معروف است و ثابت می‌شود که علاوه بر فرمول بازگشتی بیان شده در قضیه فوق، فرمول زیر برای محاسبه آن وجود دارد:

$S (n, r) = \frac{1}{r!} [\sum_{i = 1}^{r} {(- 1)}^{i} (\begin{array}{l} r \\ i \end{array}) {(r - i)}^{n}]$

تست‌های این مبحث

تست شماره 1

تعداد افرازهای یک مجموعه چهار عضوی چندتا است؟

ده تا
دوازده تا
چهارده تا
پانرده تا

مشاهده پاسخ تست

تست شماره 2

تعداد افرازهای یک مجموعه هفت عضوی به‌طوری که حداقل یک مجموعه چهار عضوی در میان مجموعه ها باشد، کدام است؟

$110$ حالت
$123$ حالت
$155$ حالت
$175$ حالت

مشاهده پاسخ تست

تست شماره 3

یک مجموعه شش عضوی را به چند طریق می‌توان به حداقل دو زیر مجموعه افراز کرد به‌گونه‌ای که در هر افراز، تعداد اعضای زیر مجموعه ها یکسان باشد؟

$15$
$20$
$25$
$26$

مشاهده پاسخ تست

تست شماره 4

اگر $A, B, C$ افرازی برای مجموعه دوازده عضوی $U$ باشد و داشته باشیم:

$3 n (A) = 6 n (B) = 2 n (C)$

تعداد اعضای $A \cup C$ کدام است؟

$7$
$8$
$9$
$10$

مشاهده پاسخ تست

تست شماره 5

فرض کنید $A_{n}, A$ به‌صورت زیر باشد:

$\begin{array}{l} A = \{x \in ℤ |- 10 \leq x \leq 10\} \\ A_{n} = \{x \in ℤ |- n \leq x \leq n\} \end{array}$

کدام ‌یک از حالت های زیر، افرازی برای مجموعه A است؟

$\begin{array}{l} A_{10} - A_{8}, A_{7} - A_{5}, A_{4} - A_{2} \end{array}$
$\begin{array}{l} A_{10} - A_{7}, A_{7} - A_{4}, A_{4} - A_{2} \end{array}$
$\begin{array}{l} A_{10} - A_{7}, A_{7} - A_{5}, A_{5} - A_{3}, A_{3} \end{array}$
$A_{10} - A_{8}, A_{7} - A_{4}, A_{3} - A_{1}, A_{1}$

مشاهده پاسخ تست

تست شماره 6

دو مجموعه زیر مفروضند:

$\begin{array}{l} A = \{2 k - 1 |k = 0, 1, 2\} \\ B = \{m^{2} - 2 m |m = - 1, 0, 1\} \end{array}$

مجموعه $A \cup B$ را به چند طریق می‌توان افراز کرد به‌گونه‌ای که هیچ دو عدد مثبتی در یک زیر مجموعه قرار نگیرد؟

$6$
$8$
$9$
$10$

مشاهده پاسخ تست

تست شماره 7

کدام گزینه افرازی برای مجموعه اعداد صحیح می‌باشد؟

مجموعه اعداد صحیح منفی و اعداد صحیح مثبت
مجموعه اعداد حسابی و قرینه آنها
مجموعه اعداد حسابی و قرینه اعداد طبیعی
مجموعه اعداد طبیعی و قر ینه آنها

مشاهده پاسخ تست

تست شماره 8

چه تعداد از مجموعه های زیر افرازی برای مجموعه $A$ می‌باشد.

$A = \{ϕ, \{ϕ\}, a, b, c\}$

$\begin{array}{l} \{ϕ\}, \{\{ϕ\}\}, \{a\}, \{b, c\} \end{array}$
$\begin{array}{l} \{ϕ\}, \{\{ϕ\}\}, \{a, b\}, \{b, c\} \end{array}$
$\begin{array}{l} \{ϕ\}, \{a, b\}, \{c, \{ϕ\}\} \end{array}$
$\{ϕ, \{ϕ\},, \{a, b, c\}\}$

مشاهده پاسخ تست

تست شماره 9

مجموعه $A = \{3, 7, 10, 12, 15\}$ را در نظر بگیرید.

اگر $\{15, y + 5\}, \{3, 7, x - 2\}$ یک افراز برای $A$ باشد، آن‌گاه بیش‌ترین مقدار $x y$ کدام است؟

$70$
$78$
$84$
$88$

مشاهده پاسخ تست

تست شماره 10

مجموعه $7$ عضوی را به چند طریق می‌توان به زیر مجموعه های $4, 2, 1$ عضوی افراز کرد؟

$120$
$(\begin{matrix} 7 \\ 2 \end{matrix})$
$210$
$105$

مشاهده پاسخ تست

تست شماره 11

مجموعه $7$ عضوی را به چند طریق می‌توان به زیر مجموعه های $3, 2, 2$ عضوی افراز کرد؟

$105$
$210$
$(\begin{matrix} 7 \\ 3 \end{matrix})$
$150$

مشاهده پاسخ تست

تست شماره 12

یک مجموعه $7$ عضوی را به چند طریق می‌توان به دو زیر مجموعه افراز نمود؟

$64$
$63$
$62$
$61$

مشاهده پاسخ تست

تست شماره 13

مجموعه $A = \{a, b, c, d, e\}$ را به چند طریق می‌توان به $3$ زیر مجموعه افراز کرد؟

$10$
$20$
$25$
$40$

مشاهده پاسخ تست

تست شماره 14

یک گروه $8$ نفری را به چند طریق می‌توانند دو تیم $4$ نفره بسازند؟

$35$
$20$
$15$
$12$

مشاهده پاسخ تست

تست شماره 15

روی مجموعه $A = \{1, 2, 3, 4\}$ چند افراز می‌توان تعریف کرد به‌طوری که شامل $\{2, 3\}$ باشد؟

مشاهده پاسخ تست

تست شماره 16

یک مجموعه $6$ عضوی را به چند طریق می‌توان به زیر مجموعه هایی با تعداد اعضای مساوی افراز نمود؟

$15$
$20$
$25$
$27$

مشاهده پاسخ تست

تست شماره 17

تعداد افرازهای مجموعه $A = \{a, b, c, d, e\}$ که شامل یک مجموعه تک عضوی باشد، کدام است؟

$10$
$12$
$15$
$20$

مشاهده پاسخ تست

تست شماره 18

چند افراز متمایز از مجموعه $A = \{1, 2, 3, 4, 5\}$ وجود دارد که شامل یک مجموعه حداقل $3$ عضوی باشد؟

$25$
$26$
$15$
$20$

مشاهده پاسخ تست

تست شماره 19

یک مجموعه $6$ عضوی را به چند طریق می‌توان به زیر مجموعه هایی با تعداد اعضای نامساوی مساوی افراز نمود؟

$75$
$82$
$85$
$97$

مشاهده پاسخ تست

تست شماره 20

مجموعه $A = \{a, b, c, d, e\}$ را به چند طریق می‌توان به حداقل $3$ زیر مجموعه افراز کرد؟

$21$
$31$
$26$
$40$

مشاهده پاسخ تست

تست شماره 21

چند افراز از مجموعه $A = \{1, 2, 3, 4, 5\}$ وجود دارد که شامل حداقل یک مجموعه $2$ عضوی باشد؟

$35$
$27$
$50$
$20$

مشاهده پاسخ تست

تست شماره 22

یک گروه $6$ نفری به چند طریق می‌توانند سه تیم دو نفره بسازند؟

$35$
$20$
$15$
$12$

مشاهده پاسخ تست

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

ترکیبیات (ابزارهای شمارشی)

افراز

تست‌های این مبحث

nenomatica

مجموعه قوانین

دسترسی سریع

آیا می‌خواهید فیلم معرفی را مشاهده نمایید؟