מתוך ויקיפדיה, האנציקלופדיה החופשית
52 החלוקות של קבוצה בת 5 איברים: הנקודות מייצגות איברים בקבוצה; כאשר הן אינן צבועות הן מסמנות תת-קבוצות בעלות איבר יחיד. האזורים הצבועים מייצגים תת-קבוצות שלה. בקומבינטוריקה , מספרי בל (על שם המתמטיקאי האמריקאי אריק טמפל בל ) ניתנים על ידי נוסחת הנסיגה הבאה:
B
0
=
1
,
B
n
=
∑
k
=
0
n
−
1
(
n
−
1
k
)
B
k
{\displaystyle B_{0}=1,\quad B_{n}=\sum _{k\,=\,0}^{n\,-\,1}{\binom {n-1}{k}}B_{k}}
עבור מספר החלוקות הזרות של קבוצה לא-ריקה
A
{\displaystyle A}
איחוד הקבוצות מכסה את
A
{\displaystyle A}
לקבוצה בת 3 איברים ישנן 5 חלוקות זרות שונות:
{
{
1
}
,
{
2
}
,
{
3
}
}
{
{
1
}
,
{
2
,
3
}
}
{
{
2
}
,
{
1
,
3
}
}
{
{
3
}
,
{
1
,
2
}
}
{
{
1
,
2
,
3
}
}
{\displaystyle {\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
{\displaystyle n}
ללא הגבלת הכלליות , נבחר איבר כלשהו ונוסיפו לקבוצה בת
0
≤
k
≤
n
−
1
{\displaystyle 0\leq k\leq n-1}
(
n
−
1
k
)
{\displaystyle {\tbinom {n-1}{k}}}
B
n
−
k
−
1
{\displaystyle B_{n-k-1}}
n
−
k
−
1
{\displaystyle n-k-1}
זהות פסקל נקבל:
B
n
=
∑
k
=
0
n
−
1
(
n
−
1
k
)
B
n
−
k
−
1
=
∑
k
=
0
n
−
1
(
n
−
1
n
−
k
−
1
)
B
n
−
k
−
1
=
∑
k
=
0
n
−
1
(
n
−
1
k
)
B
k
{\displaystyle 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}}
מציאת מספר בל משולש בל (נקרא גם משולש פרס או משולש אייטקן ), הדומה למשולש פסקל , מספק את ערכי הסדרה:
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
{\displaystyle {\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
)
{\displaystyle C(m,n)=C(m-1,n-1)+C(m,n-1)}
