Stirling Numbers: Πρώτου και Δεύτερου Είδους, Τύποι, Παραδείγματα και Εφαρμογές

Οι αριθμοί Stirling αποτελούν θεμελιώδη έννοια στη συνδυαστική και στα διακριτά μαθηματικά. Εμφανίζονται σε πολλά προβλήματα που σχετίζονται με μεταθέσεις, διαμερίσεις συνόλων και αναδρομικές σχέσεις.

Υπάρχουν δύο τύποι αριθμών Stirling:

• Stirling numbers of the first kind – μετρούν τις μεταθέσεις με συγκεκριμένο αριθμό κύκλων.

• Stirling numbers of the second kind – μετρούν τις διαμερίσεις ενός συνόλου σε μη κενά υποσύνολα.

---

1. Stirling Numbers of the First Kind

Ο αριθμός Stirling πρώτου είδους συμβολίζεται ως:

$$c(n,k)$$

Αντιπροσωπεύει τον αριθμό των μεταθέσεων ενός συνόλου $n$ στοιχείων που αποτελούνται από ακριβώς $k$ διακεκριμένους κύκλους.

Παράδειγμα

Για $c(4, 2)$ έχουμε:

$$c(4,2)=11$$

Υπάρχουν 11 μεταθέσεις του συνόλου $\{1,2,3,4\}$ με 2 κύκλους. Σε κυκλική γραφή τις χωρίζουμε σε πολλές γραμμές:

$$\begin{aligned} \{ &(1)(234),\ (1)(243),\ (134)(2),\ (143)(2), \\ &(124)(3),\ (142)(3),\ (123)(4),\ (132)(4), \\ &(12)(34),\ (13)(24),\ (14)(23)\} \end{aligned}$$Έτσι το σύνολο προβάλλεται όμορφα χωρίς να ξεφεύγει από το πλάτος της σελίδας. ✅

---

2. Stirling Numbers of the Second Kind

Ο αριθμός Stirling δεύτερου είδους συμβολίζεται ως:

$$S(n,k)$$

Μετρά τους τρόπους με τους οποίους μπορούμε να διαιρέσουμε ένα σύνολο με $n$ στοιχεία σε ακριβώς $k$ μη κενά υποσύνολα.

Παράδειγμα

Για $S(4, 2)$:

$$S(4,2)=7$$

Οι 7 διαμερίσεις του συνόλου $\{1,2,3,4\}$ σε δύο μη κενά υποσύνολα είναι:

$$\{1\mathrm{\mid }234,2\mathrm{\mid }134,3\mathrm{\mid }124,4\mathrm{\mid }123,12\mathrm{\mid }34,13\mathrm{\mid }24,14\mathrm{\mid }23\}$$

---

Αναδρομικός Τύπος

$$S(n+1,k)=k\cdot S(n,k)+S(n,k-1)$$

Ερμηνεία:

• Αν το στοιχείο $n+1$ τοποθετηθεί μόνο του → $S(n, k-1)$.

• Αν προστεθεί σε ένα από τα $k$ υπάρχοντα υποσύνολα → $k \cdot S(n, k)$.

---

Κλειστός Τύπος

$$S(n,k)=\frac{1}{k!}\sum _{j=0}^k(-1{)}^j\left(\genfrac{}{}{0px}{}{k}{j}\right)(k-j{)}^n$$

Προκύπτει μέσω της ένταξης-απαλοιφής (inclusion-exclusion).

---

3. Σχέση με τους Bell Numbers

Ο Bell Number $B_n$ δίνει τον συνολικό αριθμό διαμερίσεων ενός συνόλου $n$ στοιχείων:

$$B_n=\sum _{k=1}^{n}S(n,k)$$

Παράδειγμα:

$$B_3=S(3,1)+S(3,2)+S(3,3)=1+3+1=5$$

---

4. Εφαρμογές των Stirling Numbers

• Συνδυαστική – καταμέτρηση κύκλων και διαμερίσεων.

• Πιθανότητες – υπολογισμός τυχαίων μεταθέσεων και αναμενόμενων κύκλων.

• Θεωρία Αριθμών – σχέσεις με αρμονικούς αριθμούς και Bernoulli numbers.

• Πληροφορική – ανάλυση αλγορίθμων, hashing, κατανομή πόρων.

---

Συμπέρασμα

Οι Stirling Numbers αποτελούν θεμελιώδες εργαλείο στη συνδυαστική και συνδέουν τις μεταθέσεις, τις διαμερίσεις και πλήθος σημαντικών μαθηματικών εφαρμογών.