ابتدا به چند تعریف زیر توجه کنید:
مجموعه تهی (Empty set): مجموعه تهی، مجموعهای است که هیچ عضوی ندارد. مجموعه تهی را با ϕ یا {} نشان میدهند.
زیرمجموعه (Subset): یک زیرمجموعه، مجموعهای است که همه اعضای آن از یک مجموعه دیگر به نام اَبَرمجموعه یا فوق مجموعه (super set) استخراج شدهاند.
اجتماع مجموعهها (Union of Sets): اجتماع (یا جمع) دو مجموعه، مجموعهای است که اعضای آن، اعضای هر یک از دو مجموعه را با هم در بر میگیرد. اجتماع را با نماد ⋃ بین دو مجموعه نشان میدهند. بدین ترتیب، اجتماع {2,3} و{2,4}، مجموعه{2,3,4} است.
اشتراک مجموعهها (Intersection of Sets): اشتراک دو مجموعه، مجموعهای است که شامل اعضای مشترک هر دو مجموعه باشد. اشتراک را با نماد⋂ بین دو مجموعه نشان میدهند. اشتراک {2,3} و{2,4}، مجموعه {2} است.
تعریف افراز
یک افراز (partition) از مجموعه A، مجموعهای ناتهی، شامل زیرمجموعههایی از مجموعه A است، بهطوری که هر عضو از مجموعه A دقیقاً در یکی از این زیرمجموعهها وجود داشته باشد.
بهطور دقیقتر، افرازهای مجموعه A، خانوادهای از زیرمجموعههای A (که با S مشخص میشود) هستند اگر و تنها اگر شرایط زیر را داشته باشند:
این خانواده مجموعه، نباید شامل مجموعه تهی باشد ( $ \phi ∉S$ ).
مجموعههای خانواده S، مجموعه A را پوشش دهد، یعنی $ \bigcup_ {B∈S} B=A $ .
اگر اشتراک هر دو مجموعه از S را بگیریم، به یک مجموعه تهی برسیم. به عبارت دیگر، اعضای مجموعه A باید دو به دو مجزا باشند، یعنی اگر L و M عضو S باشند و $L \neq M$، آنگاه $L \cap M = ϕ $.
این افرازها، بخش (part)، بلوک (block) یا سلول (cell) نیز نامیده میشوند.
نوشتن افرازهای مجموعه
مجموعه چهارعضوی $A= \lbrace a,b,c,d \rbrace $ را در نظر بگیرید. با انجام مراحل زیر، میتوان افرازهای این مجموعه را نوشت. برای نوشتن افرازها، باید ترکیبات مختلف آنها را بنویسیم.
گام 1 : ابتدا افرازهای 4 عضوی را مینویسیم که برابر با خود مجموعه است و در شرایط بالا صدق میکند:
$$ A= \lbrace a,b,c,d \rbrace $$
گام 2: اکنون، اجزای سه و یک عضوی را جدا میکنیم:
$$ \lbrace a,b,c \rbrace , \lbrace d \rbrace ; \lbrace a,b,d \rbrace , \lbrace c \rbrace ; \lbrace a,c,d \rbrace , \lbrace b \rbrace ; \lbrace b,c,d \rbrace , \lbrace a \rbrace $$
گام 3: مشابه روند قبل، اکنون، ترکیبات دو عضوی را مینویسیم:
$$ \lbrace a,b\rbrace , \lbrace c,d\rbrace; \lbrace a,c\rbrace , \lbrace b,d\rbrace; \lbrace a,d\rbrace , \lbrace b,c\rbrace $$
گام ۴: اکنون، ترکیبات 2، 1 و 1 عضوی را مشخص میکنیم:
$$
\lbrace a,b \rbrace , \lbrace c\rbrace , \lbrace d \rbrace ; \lbrace a,c \rbrace , \lbrace b \rbrace , \lbrace d \rbrace ; \lbrace a,d \rbrace , \lbrace b \rbrace , \lbrace c \rbrace ; \lbrace b,c \rbrace , \lbrace a \rbrace , \lbrace d \rbrace ; \lbrace b,d \rbrace , \lbrace a \rbrace , \lbrace c \rbrace ;
\lbrace c,d \rbrace , \lbrace a \rbrace , \lbrace b \rbrace $$
گام 5: میبینیم که فقط ترکیبهای 1 عضوی برای نوشتن باقی میمانند:
$$ \lbrace a \rbrace ; \lbrace b \rbrace ; \lbrace c \rbrace ; \lbrace d \rbrace $$
بنابراین، مشاهده میشود که 15 افراز ممکن برای یک مجموعه چهارعضوی دلخواه وجود دارد.
چند نکته
مجموعه {x,y,z} شامل ۵ افراز زیر است:
• {{x},{y},{z}}{{x},{y},{z}}
• {{x,y},{z}}{{x,y},{z}}
• {{x,z},{y}}{{x,z},{y}}
• {{z,y},{x}}{{z,y},{x}}
• {{x,y,z}}{{x,y,z}}
توجه کنید که:
• $ \lbrace \lbrace \rbrace, \lbrace x,z \rbrace, \lbrace y \rbrace \rbrace $ نمیتواند یک افراز برای مجموعه باشد، زیرا شامل یک مجموعه تهی است.
• $ \lbrace \lbrace x,y\rbrace,\lbrace x,y\rbrace \rbrace $ نمیتواند یک افراز از مجموعه باشد، زیرا عضو y تکرار شده است.
• $ \lbrace \lbrace x \rbrace, \lbrace y \rbrace \rbrace $ نمیتواند یک افراز مجموعه باشد، زیرا یکی از سه عضو مجموعه در آن وجود ندارد.
مجموعه منفرده یا تکعضوی مانند $ \lbrace a\rbrace $ فقط یک افراز دارد و آن هم، خودش است .
همچنین، مجموعه تهی یک افراز دارد که خودش است.
عدد بل
با استفاده از اعداد بل (Bell Numbers) میتوان تعداد افرازهای ممکن یک مجموعه را محاسبه کرد. در حالت کلی، $ B_{n} $ تعداد افرازهای مجموعهای با n عضو است. فرمول مشخص سادهای برای $ B_{n} $ وجود ندارد. اما با کمک رابطه بازگشتی زیر میتوان تعداد افرازهای ممکن یک مجموعه را بهدست آورد:
$$ B_{n+1} = \sum_ k^n \binom{n}{k} B_{k} $$ که سیگما از k=0 تا n
که در آن، $ \binom{n}{k} $نماد انتخاب k شی از n شی یا همان ترکیب است و با فرمول زیر محاسبه میشود:
$ \binom{n}{k} = \frac{n!}{k! \times \big( n-k \big)! } $
بنابراین، باید تعداد افرازهای ممکن مجموعههای کوچکتر از مجموعه مورد نظر را نیز محاسبه کنیم. برای مجموعه تهی، میدانیم که $ B_{0} =1$ . در نتیجه، مقدار $ B_{1} =1$ بهدست میآید و اگر همینطور ادامه دهیم، به $ B_{4} =15 $ میرسیم که برای مجموعه چهارعضوی $ \lbrace a,b,c,d \rbrace $، آنها را نوشتیم.
$$
B_{2} = \sum_k^1 \binom{1}{k} B_{k} = \binom{1}{0} B_{0} + \binom{1}{1} B_{1} = 1.1+1.1 = 1+1=2
///
B_{3} = \sum_k^2 \binom{2}{k} B_{k} =1.1+2.1 + 1.2 = 1+2+2 =5
///
B_{4} = \sum_k^3 \binom{3}{k} B_{k} =1.1+3.1 + 3.2+1.5 = 15 $$
