מספרי בל
קפיצה לניווט
קפיצה לחיפוש
בקומבינטוריקה, מספרי בל (על שם המתמטיקאי האמריקאי אריק טמפל בל) ניתנים על ידי נוסחת הנסיגה הבאה:
- $ 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.
- בשמאל השורה הבאה נכתוב את האיבר הימני ביותר בשורה הקודמת.
- כל איבר (החל מהשני משמאל) הוא סכום האיבר השמאלי לו והאיבר מעל השמאלי לו. כלומר:
- $ C(m,n)=C(m-1,n-1)+C(m,n-1) $
קישורים חיצוניים
מספרי בל38993562Q816063