מספרי בל

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

B_{0} = 1, B_{n} = \sum_{k = 0}^{n - 1} (\binom{n - 1}{k}) B_{k}

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

דוגמה

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

\begin{aligned} {{1}, {2}, {3}} \\ {{1}, {2, 3}} \\ {{2}, {1, 3}} \\ {{3}, {1, 2}} \\ {{1, 2, 3}} \end{aligned}

הסבר

תהי קבוצה בת $n$ איברים. ללא הגבלת הכלליות, נבחר איבר כלשהו ונוסיפו לקבוצה בת $0 \leq k \leq n - 1$ איברים שאותם נבחר ב- $(\binom{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} 1 \\ 1 & 2 \\ 2 & 3 & 5 \\ 5 & 7 & 10 & 15 \\ 15 & 20 & 27 & 37 & 52 \\ 52 & 67 & 87 & 114 & 151 & 203 \\ 203 & 255 & 322 & 409 & 523 & 674 & 877 \end{matrix}

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

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

מספרי בל39184698Q816063