מספרי בל
מתוך ויקיפדיה, האנציקלופדיה החופשית
פעולות נוספות
בקומבינטוריקה, מספרי בל (על שם המתמטיקאי האמריקאי אריק טמפל בל) ניתנים על ידי נוסחת הנסיגה הבאה:
- <math>B_0=1,\quad B_n=\sum_{k\,=\,0}^{n\,-\,1}\binom{n-1}{k}B_k</math>
עבור מספר החלוקות הזרות של קבוצה לא-ריקה <math>A</math>, כאשר איחוד הקבוצות מכסה את <math>A</math>.
דוגמה עריכה
לקבוצה בת 3 איברים ישנן 5 חלוקות זרות שונות:
- <math>\begin{align}&\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{align}</math>
הסבר עריכה
תהי קבוצה בת <math>n</math> איברים. ללא הגבלת הכלליות, נבחר איבר כלשהו ונוסיפו לקבוצה בת <math>0\le k\le n-1</math> איברים שאותם נבחר ב-<math>\tbinom{n-1}{k}</math> אפשרויות.
על כל אפשרות כזו ישנן <math>B_{n-k-1}</math> אפשרויות לחלוקת <math>n-k-1</math> האיברים הנותרים לקבוצות לא-ריקות. על פי זהות פסקל נקבל:
- <math>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</math>
משולש בל עריכה
משולש בל (נקרא גם משולש פרס או משולש אייטקן), הדומה למשולש פסקל, מספק את ערכי הסדרה:
- <math>\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}</math>
- האיבר הראשון הוא 1.
- בשמאל השורה הבאה נכתוב את האיבר הימני ביותר בשורה הקודמת.
- כל איבר (החל מהשני משמאל) הוא סכום האיבר השמאלי לו והאיבר מעל השמאלי לו. כלומר:
- <math>C(m,n)=C(m-1,n-1)+C(m,n-1)</math>