أرقام ستيرلينغ من النوع الثاني

تخضع أعداد ستيرلينغ من النوع الثاني لعلاقة التكرار (التي اكتشفها ماسانوبو ساكا لأول مرة في كتابه Sanpō-Gakkai عام 1782 ): ^{[ 12 ]}

${\displaystyle \left\{{n+1 \atop k}\right\}=k\left\{{n \atop k}\right\}+\left\{{n \atop k-1}\right\}\quad {\mbox{for}}\;0<k<n}$

مع الشروط الأولية

${\displaystyle \left\{{n \atop n}\right\}=1\quad {\mbox{ لـ}}\;n\geq 0\quad {\text{ و}}\quad \left\{{n \atop 0}\right\}=\left\{{0 \atop n}\right\}=0\quad {\text{ لـ}}n>0{\text{.}}}$

على سبيل المثال، يتم إعطاء الرقم 25 في العمود k  =  3 والصف n  = 5 بواسطة 25 = 7 + (3×6)، حيث 7 هو الرقم الموجود أعلى 25 وعلى يساره، و6 هو الرقم الموجود أعلى 25، و3 هو العمود الذي يحتوي على الرقم 6.      

لإثبات هذه العلاقة التكرارية، لاحظ أن تجزئة ⁠${\displaystyle n+1}$⁠ ...​​​${\displaystyle (n+1)}$إما أن يكون العنصر رقم n عنصرًا منفردًا أو لا. ويُعطى عدد الطرق التي يكون بها العنصر المنفرد أحد المجموعات الجزئية بالصيغة التالية:

${\displaystyle \left\{{n \atop k-1}\right\}}$

بما أنه يجب علينا تقسيم العناصر المتبقية البالغ عددها n إلى العناصر المتاحة${\displaystyle k-1}$المجموعات الفرعية . في الحالة الأخرى${\displaystyle (n+1)}$ينتمي العنصر رقم n إلى مجموعة جزئية تحتوي على عناصر أخرى. ويُعطى عدد الطرق بالصيغة التالية:

${\displaystyle k\left\{{n \atop k}\right\}}$

بما أننا نقسم جميع الكائنات باستثناء ⁠${\displaystyle (n+1)}$⁠ -th إلى k مجموعات فرعية، ثم يتبقى لدينا k خيارات لإدراج الكائن ⁠${\displaystyle n+1}$⁠ . جمع هاتين القيمتين يعطي النتيجة المرجوة.

تُعطى علاقة تكرارية أخرى بواسطة

${\displaystyle \left\lbrace {\begin{matrix}n\\k\end{matrix}}\right\rbrace ={\frac {k^{n}}{k!}}-\sum _{r=1}^{k-1}{\frac {\left\lbrace {\begin{matrix}n\\r\end{matrix}}\right\rbrace }{(kr)!}}.}$

والذي يترتب على تقييم${\displaystyle \sum _{r=0}^{n}\left\{{n \atop r}\right\}(x)_{r}=x^{n}}$في${\displaystyle x=k}$.

ويُفترض أيضاً أنه بالنسبة لقيمة ثابتة${\displaystyle n}$لدينا

${\displaystyle {\begin{aligned}\left\{{n \atop k}\right\}&={\frac {1}{nk}}\sum _{j=2}^{n-k+1}(j-2)!{\binom {-k}{j}}\left\{{n \atop k+j-1}\right\},\\\left\{{n \atop n}\right\}&=1.\end{aligned}}}$

هنا نبدأ بالحساب المتكرر لـ${\displaystyle \left\{{n \atop n-1}\right\}}$ثم احسب${\displaystyle \left\{{n \atop n-2}\right\}}$وهكذا حتى${\displaystyle \left\{{n \atop 1}\right\}}$.

وثمة تخمين آخر هو أنه بالنسبة لقيمة ثابتة${\displaystyle k}$لدينا

${\displaystyle {\begin{aligned}\left\{{n \atop k}\right\}&={\frac {1}{n-k}}\sum _{j=2}^{n-k+1}{\binom {n}{j}}\left\{{n-j+1 \atop k}\right\}(-1)^{j},\\\left\{{n \atop n}\right\}&=1.\end{aligned}}}$

إذا قمت بالتبديل${\displaystyle (j-2)!}$من المجموع الأول و${\displaystyle (-1)^{j}}$من الثاني، ستحصل على تخمينات مماثلة، ولكن لأعداد ستيرلينغ من النوع الأول .

تتضمن بعض الهويات البسيطة ما يلي

${\displaystyle \left\{{n \atop n-1}\right\}={\binom {n}{2}}.}$

وذلك لأن تقسيم n عنصرًا إلى n − 1   مجموعة يعني بالضرورة تقسيمها إلى مجموعة واحدة بحجم 2 و n − 2   مجموعة بحجم 1. لذلك نحتاج فقط إلى اختيار هذين العنصرين؛

و

${\displaystyle \left\{{n \atop 2}\right\}=2^{n-1}-1.}$

لتوضيح ذلك، لاحظ أولًا وجود 2 ^{^n} زوجًا مرتبًا من المجموعات الجزئية المتكاملة A و B. في حالة واحدة، تكون A فارغة، وفي حالة أخرى تكون B فارغة، لذا يتبقى 2 ^{^n} - 2   زوجًا مرتبًا من المجموعات الجزئية. أخيرًا، بما أننا نريد أزواجًا غير مرتبة بدلًا من أزواج مرتبة ، نقسم هذا العدد الأخير على 2، فنحصل على النتيجة المذكورة أعلاه.

ويؤدي توسيع صريح آخر لعلاقة التكرار إلى متطابقات على غرار المثال أعلاه.

يُقدّم الجدول الوارد في القسم 6.1 من كتاب الرياضيات الملموسة مجموعة كبيرة من الصيغ العامة للمجاميع المنتهية التي تتضمن أعداد ستيرلينغ. ومن بين المجاميع المنتهية ذات الصلة بهذا المقال:

${\displaystyle {\begin{aligned}\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}{n \choose j}\left\{{j \atop k}\right\}\\\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}(k+1)^{n-j}\left\{{j \atop k}\right\}\\\left\{{n+k+1 \atop k}\right\}&=\sum _{j=0}^{k}j\left\{{n+j \atop j}\right\}\\\left\{{n \atop \ell +m}\right\}{\binom {\ell +m}{\ell }}&=\sum _{k}\left\{{k \atop \ell }\right\}\left\{{n-k \atop m}\right\}{\binom {n}{k}}\end{aligned}}}$

تُعطى أعداد ستيرلينغ من النوع الثاني بالصيغة الصريحة التالية:

${\displaystyle \left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}=\sum _{j=0}^{k}{\frac {(-1)^{k-j}j^{n}}{(k-j)!j!}}.}$

يمكن استنتاج ذلك باستخدام مبدأ الإدراج والاستبعاد لحساب التطبيقات الشاملة من n إلى k، وباستخدام حقيقة أن عدد هذه التطبيقات الشاملة هو${\textstyle k!\left\{{n \atop k}\right\}}$.

بالإضافة إلى ذلك، فإن هذه الصيغة هي حالة خاصة من الفرق الأمامي من الرتبة k للحد الأحادي${\displaystyle x^{n}}$تم تقييمها عند x = 0:

${\displaystyle \Delta ^{k}x^{n}=\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}(x+j)^{n}.}$

لأن كثيرات حدود برنولي يمكن كتابتها بدلالة هذه الفروق الأمامية، فإن المرء يحصل مباشرة على علاقة في أعداد برنولي :

${\displaystyle B_{m}(0)=\sum _{k=0}^{m}{\frac {(-1)^{k}k!}{k+1}}\left\{{m \atop k}\right\}.}$

تقييم متعددة الحدود الأسية غير الكاملة لـ Bell B _{n , k} ( x ₁ , x ₂ ,...) على سلسلة الآحاد يساوي عدد ستيرلينغ من النوع الثاني:

${\displaystyle \left\{{n \atop k}\right\}=B_{n,k}(1,1,\dots ,1).}$

صيغة أخرى صريحة وردت في دليل NIST للدوال الرياضية هي

${\displaystyle \left\{{n \atop k}\right\}=\sum _{\begin{array}{c}c_{1}+\ldots +c_{k}=n-k\\c_{1},\ldots ,\ c_{k}\ \geq \ 0\end{array}}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}}$

زوجية عدد ستيرلينغ من النوع الثاني هي نفسها زوجية معامل ذي الحدين المرتبط به :

${\displaystyle \left\{{n \atop k}\right\}\equiv {\binom {z}{w}}\ {\pmod {2}},}$أين${\displaystyle z=n-\left\lceil \displaystyle {\frac {k+1}{2}}\right\rceil ,\ w=\left\lfloor \displaystyle {\frac {k-1}{2}}\right\rfloor .}$

يتم تحديد هذه العلاقة عن طريق تعيين إحداثيات n و k على مثلث سيربينسكي .

بشكل مباشر، لنفترض أن مجموعتين تحتويان على مواضع الرقم 1 في التمثيلات الثنائية لنتائج التعبيرات المعنية:

${\displaystyle {\begin{aligned}\mathbb {A}$ :\ \sum _{i\in \mathbb {A} }2^{i}&=nk,\\\mathbb {B}  :\ \sum _{j\in \mathbb {B} }2^{j}&=\left\lfloor {\dfrac {k-1}{2}}\right\rfloor .\\\end{aligned}}}

يمكن محاكاة عملية AND الثنائية عن طريق تقاطع هاتين المجموعتين:

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2={\begin{cases}0,&\mathbb {A} \cap \mathbb {B} \neq \emptyset$ ;\\1,&\mathbb {A} \cap \mathbb {B} =\emptyset  ;\end{cases}}}

للحصول على زوجية عدد ستيرلينغ من النوع الثاني في زمن O (1) . باستخدام الشفرة الزائفة :

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2:=\left[\left(\left(n-k\right)\ \And \ \left(\left(k-1\right)\,\mathrm {div} \,2\right)\right)=0\right];}$

أين${\displaystyle \left[b\right]}$هذا هو قوس إيفرسون .

زوجية عدد ستيرلينغ المركزي من النوع الثاني${\displaystyle \textstyle \left\{{2n \atop n}\right\}}$يكون فرديًا إذا وفقط إذا${\displaystyle n}$هو عدد فيبي ثنائي ، وهو عدد لا يحتوي تمثيله الثنائي على رقمين متتاليين 1. ^{[ 13 ]}

بالنسبة لعدد صحيح ثابت n ، فإن الدالة المولدة العادية لأعداد ستيرلينغ من النوع الثاني${\displaystyle \left\{{n \atop 0}\right\},\left\{{n \atop 1}\right\},\ldots }$يُعطى بواسطة

${\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}x^{k}=T_{n}(x),}$

أين${\displaystyle T_{n}(x)}$هي كثيرات حدود توشارد . إذا جمعنا أعداد ستيرلينغ مقابل المضروب المتناقص بدلاً من ذلك، فيمكننا إثبات المتطابقات التالية، من بين أمور أخرى:

${\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}}$

و

${\displaystyle \sum _{k=1}^{n+1}\left\{{n+1 \atop k}\right\}(x-1)_{k-1}=x^{n},}$

والتي لها حالة خاصة

${\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}(n)_{k}=n^{n}.}$

بالنسبة لعدد صحيح ثابت k ، فإن أعداد ستيرلينغ من النوع الثاني لها دالة توليد عادية نسبية

${\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}x^{n-k}=\prod _{r=1}^{k}{\frac {1}{1-rx}}={\frac {1}{x^{k+1}(1/x)_{k+1}}}}$

ولها دالة توليد أسية معطاة بواسطة ^{[ 14 ]}

${\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}={\frac {(e^{x}-1)^{k}}{k!}}.}$

دالة توليد ثنائية المتغيرات مختلطة لأعداد ستيرلينغ من النوع الثاني هي

${\displaystyle \sum _{k=0}^{\infty }\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}y^{k}=e^{y(e^{x}-1)}.}$

لو${\displaystyle n\geq 2}$و${\displaystyle 1\leq k\leq n-1}$، ثم

${\displaystyle {\frac {1}{2}}(k^{2}+k+2)k^{n-k-1}-1\leq \left\{{n \atop k}\right\}\leq {\frac {1}{2}}{n \choose k}k^{n-k}}$[ ^{15 ]​}

لقيمة ثابتة لـ${\displaystyle k,}$القيمة التقاربية لأعداد ستيرلينغ من النوع الثاني كما${\displaystyle n\rightarrow \infty }$يُعطى بواسطة

${\displaystyle \left\{{n \atop k}\right\}{\underset {n\to \infty }{\sim }}{\frac {k^{n}}{k!}}.}$

لو${\displaystyle k=o({\sqrt {n}})}$(حيث يرمز o إلى رمز o الصغير ) إذن

${\displaystyle \left\{{n+k \atop n}\right\}{\underset {n\to \infty }{\sim }}{\frac {n^{2k}}{2^{k}k!}}.}$^{[ 16 ]}

يوجد أيضًا تقريب صالح بشكل موحد: لكل k بحيث يكون 1 < k < n ، يكون لدينا

${\displaystyle \left\{{n \atop k}\right\}\sim {\sqrt {\frac {v-1}{v(1-G)}}}\left({\frac {v-1}{v-G}}\right)^{n-k}{\frac {k^{n}}{n^{k}}}e^{k(1-G)}\left({n \atop k}\right),}$

أين${\displaystyle v=n/k}$، و${\displaystyle G\in (0,1)}$هو الحل الفريد لـ${\displaystyle G=ve^{G-v}}$[ ^{17 ] الخطأ} النسبي محدود بحوالي${\displaystyle 0.066/n}$.

للثابت${\displaystyle n}$،${\displaystyle \left\{{n \atop k}\right\}}$تكون المتتالية أحادية النمط، أي أنها تتزايد ثم تتناقص. وتُبلغ القيمة القصوى عند قيمتين متتاليتين على الأكثر لـ k . أي أن هناك عددًا صحيحًا${\displaystyle k_{n}}$بحيث

${\displaystyle \left\{{n \atop 1}\right\}<\left\{{n \atop 2}\right\}<\cdots <\left\{{n \atop k_{n}}\right\}\geq \left\{{n \atop k_{n}+1}\right\}>\cdots >\left\{{n \atop n}\right\}.}$

بالنظر إلى جدول القيم أعلاه، فإن القيم القليلة الأولى لـ${\displaystyle k_{n}}$نكون${\displaystyle 0,1,1,2,2,3,3,4,4,4,5,\ldots }$

متى${\displaystyle n}$كبير

${\displaystyle k_{n}{\underset {n\to \infty }{\sim }}{\frac {n}{\log n}},}$

ويمكن تقريب القيمة القصوى لرقم ستيرلينغ باستخدام

${\displaystyle \log \left\{{n \atop k_{n}}\right\}=n\log n-n\log \log n-n+O(n\log \log n/\log n).}$^{[ 15 ]}

إذا كان X متغيرًا عشوائيًا يتبع توزيع بواسون بقيمة متوقعة λ، فإن عزمه النوني هو

${\displaystyle E(X^{n})=\sum _{k=0}^{n}\left\{{n \atop k}\right\}\lambda ^{k}.}$

على وجه الخصوص، فإن اللحظة n لتوزيع بواسون بقيمة متوقعة 1 هي بالضبط عدد تقسيمات مجموعة بحجم n ، أي أنها رقم بيل n ( هذه الحقيقة هي صيغة دوبينسكي ).

ليكن المتغير العشوائي X عدد النقاط الثابتة لتبديل عشوائي موزع توزيعًا منتظمًا لمجموعة منتهية حجمها m . عندئذٍ، العزم النوني لـ X هو

${\displaystyle E(X^{n})=\sum _{k=0}^{m}\left\{{n \atop k}\right\}.}$

ملاحظة: الحد الأعلى للمجموع هو m وليس n .

بمعنى آخر، العزم النوني لهذا التوزيع الاحتمالي هو عدد تقسيمات مجموعة حجمها n إلى m جزء على الأكثر . وقد تم إثبات ذلك في مقالة حول إحصاءات التبديل العشوائي ، مع اختلاف طفيف في الترميز.

يمكن أن تمثل أعداد ستيرلينغ من النوع الثاني العدد الإجمالي لأنماط القافية لقصيدة مكونة من n سطرًا.${\displaystyle S(n,k)}$يُعطي هذا عدد أنماط القافية الممكنة لـ n سطرًا باستخدام k مقطعًا صوتيًا فريدًا متناغمًا. على سبيل المثال، بالنسبة لقصيدة من 3 أسطر، يوجد نمط قافية واحد باستخدام قافية واحدة فقط (aaa)، و3 أنماط قافية باستخدام قافيتين (aab، aba، abb)، ونمط قافية واحد باستخدام ثلاث قوافي (abc).

عدد ستيرلينغ من النوع الثاني r${\displaystyle \left\{{n \atop k}\right\}_{r}}$يحسب عدد تقسيمات مجموعة من n عنصرًا إلى k مجموعة جزئية منفصلة غير فارغة، بحيث تكون العناصر r الأولى في مجموعات جزئية متميزة. ^{[ 18 ]} تحقق هذه الأعداد علاقة التكرار

${\displaystyle \left\{{n \atop k}\right\}_{r}=k\left\{{n-1 \atop k}\right\}_{r}+\left\{{n-1 \atop k-1}\right\}_{r}}$

يمكن العثور على بعض الهويات التوافقية والصلة بين هذه الأرقام والقواعد النحوية الخالية من السياق في ^{[ 19 ].}

عدد ستيرلينغ من النوع الثاني المرتبط بـ r هو عدد طرق تقسيم مجموعة من n عنصرًا إلى k مجموعة فرعية، بحيث تحتوي كل مجموعة فرعية على r عنصرًا على الأقل . ^{[ 20 ]} ويُرمز له بـ${\displaystyle S_{r}(n,k)}$ويخضع لعلاقة التكرار

${\displaystyle S_{r}(n+1,k)=k\ S_{r}(n,k)+{\binom {n}{r-1}}S_{r}(n-r+1,k-1)}$

تظهر الأرقام المرتبطة بالرقم 2 (التسلسل A008299 في OEIS ) في أماكن أخرى باسم "أرقام وارد" وكمقادير معاملات كثيرات حدود ماهلر .

لنرمز إلى العناصر n التي سيتم تقسيمها بواسطة الأعداد الصحيحة 1، 2، ...، n . ولنُعرّف أعداد ستيرلينغ المختزلة من النوع الثاني، والتي يُرمز لها بـ${\displaystyle S^{d}(n,k)}$، وهو عدد الطرق لتقسيم الأعداد الصحيحة 1، 2، ...، n إلى k مجموعة جزئية غير فارغة بحيث يكون لجميع العناصر في كل مجموعة جزئية مسافة زوجية لا تقل عن d . أي، لأي عددين صحيحين i و j في مجموعة جزئية معينة، يجب أن${\displaystyle |i-j|\geq d}$لقد ثبت أن هذه الأرقام تحقق

${\displaystyle S^{d}(n,k)=S(n-d+1,k-d+1),n\geq k\geq d}$

(ومن هنا جاء اسم "المختزل"). ^{[ 21 ]} لاحظ (سواء من خلال التعريف أو من خلال صيغة الاختزال)، أن${\displaystyle S^{1}(n,k)=S(n,k)}$، أرقام ستيرلينغ المألوفة من النوع الثاني.