מספרי בל

בקומבינטוריקה, מספרי בל (על שם המתמטיקאי האמריקאי אריק טמפל בל) ניתנים על ידי נוסחת הנסיגה הבאה:

52 החלוקות של קבוצה בת 5 איברים: הנקודות מייצגות איברים בקבוצה; כאשר הן אינן צבועות הן מסמנות תת-קבוצות בעלות איבר יחיד. האזורים הצבועים מייצגים תת-קבוצות שלה.

$B_{0}=1,\quad B_{n}=\sum _{k\,=\,0}^{n\,-\,1}{\binom {n-1}{k}}B_{k}$

עבור מספר החלוקות הזרות של קבוצה לא-ריקה $A$, כאשר איחוד הקבוצות מכסה את $A$.

דוגמה

לקבוצה בת 3 איברים ישנן 5 חלוקות זרות שונות:

${\begin{aligned}&{\bigl \{}\{1\},\{2\},\{3\}{\bigr \}}\\&{\bigl \{}\{1\},\{2,3\}{\bigr \}}\\&{\bigl \{}\{2\},\{1,3\}{\bigr \}}\\&{\bigl \{}\{3\},\{1,2\}{\bigr \}}\\&{\bigl \{}\{1,2,3\}{\bigr \}}\end{aligned}}$

הסבר

תהי קבוצה בת $n$ איברים. ללא הגבלת הכלליות, נבחר איבר כלשהו ונוסיפו לקבוצה בת $0\leq k\leq n-1$ איברים שאותם נבחר ב-${\tbinom {n-1}{k}}$ אפשרויות.
על כל אפשרות כזו ישנן $B_{n-k-1}$ אפשרויות לחלוקת $n-k-1$ האיברים הנותרים לקבוצות לא-ריקות. על פי זהות פסקל נקבל:

$B_{n}=\sum _{k\,=\,0}^{n\,-\,1}{\binom {n-1}{k}}B_{n-k-1}=\sum _{k\,=\,0}^{n\,-\,1}{\binom {n-1}{n-k-1}}B_{n-k-1}=\sum _{k\,=\,0}^{n\,-\,1}{\binom {n-1}{k}}B_{k}$

משולש בל

מציאת מספר בל

משולש בל (נקרא גם משולש פרס או משולש אייטקן), הדומה למשולש פסקל, מספק את ערכי הסדרה:

${\begin{matrix}&\color {red}1\\&1&\color {red}2\\&2&3&\color {red}5\\&5&7&10&\color {red}15\\&15&20&27&37&\color {red}52\\&52&67&87&114&151&\color {red}203\\&203&255&322&409&523&674&\color {red}877\end{matrix}}$

1. האיבר הראשון הוא 1.
2. בשמאל השורה הבאה נכתוב את האיבר הימני ביותר בשורה הקודמת.
3. כל איבר (החל מהשני משמאל) הוא סכום האיבר השמאלי לו והאיבר מעל השמאלי לו. כלומר:

$C(m,n)=C(m-1,n-1)+C(m,n-1)$

קישורים חיצוניים

• מספרי בל, באתר MathWorld (באנגלית)