שלום לכולם!
אני מנסה לפתור את השאלה הבאה:
כמה יחסי שקילות יש על קבוצה בת 4 איברים?
להבנתי התשובה אמורה לצאת 15 אבל אני לא מצליח להבין למה.
אשמח בבקשה להסבר.
תודה רבה על כל העזרה!
יחס שקילות מחלק את הקבוצה למחלקות שקילות. מחלקות השקילות קובעות את היחס, והיחס קובע את מחלקות השקילות. כנראה שיהיה קל יותר לספור בכמה דרכים נוכל לחלק את הקבוצה הנתונה למחלקות שקילות. נפריד למקרים:
- כל האיברים באותה מחלקה (אפשרות אחת).
- כל האיברים במחלקות שונות, איבר בכל מחלקה (אפשרות אחת).
- שלושה איברים במחלקה אחת ועוד מחלקה עם איבר בודד (ארבע אפשרויות).
- שתי מחלקות כך שכל מחלקה מכילה שני איברים (שלוש אפשרויות).
- שתי מחלקות כך שכל מחלקה מכילה שני איברים ועוד שתי מחלקות שמכילות איבר אחד בודד כל אחת (שש אפשרויות).
סה"כ יוצא 15 אפשרויות.
קיימת דרך ספירה יותר יעילה עבור קבוצות גדולות יותר, אבל עבור 4, הדרך שתיארנו היא מהירה למדי. אם בכל זאת מעניין אותך כיצד ניתן לספור, אזי שים לב כי הבעיה שקולה לשאלה בכמה דרכים אפשר לחלק את הקבוצה והתשובה לשאלה היא המספר הרביעי של מספרי בל שמסומן על-ידי B_4. החישוב של מספר בל מתבצע על-ידי נוסחת הנסיגה הבאה:
B_{n+1}=\sum_{k=0}^{n}{n \choose k} B_{k}
במקרה של השאלה, נקבל:
\begin{align*}
B_4 &= \sum_{k=0}^3 \binom{3}{k} B_k = \binom{3}{0} \cdot 1 + \binom{3}{1} \cdot 1 + \binom{3}{2} \cdot 2 + \binom{3}{3} \cdot 5\\ &=1 \cdot 1+ 3\cdot 1 + 3 \cdot 2 + 1 \cdot 5 = 15
\end{align*}
כלומר B_4=15, כמו שקיבלנו קודם.