Kombinatorisch rechnen

Question

ich soll die Stirling Zahl S,n,n-2 kombinatorisch bestimmen, also ohne Rekursion. Ich habe bis jetzt immer Rekursion benutzt. Was kann ich hier machen?

Answer 1

wenn du n Elemente in n-2 Partitionen zerlegen willst, hast du

entweder

n-3 einelementige Mengen und eine 3 elementige oder

n-4 einelementige und zwei   2-elementige   oder

n-4 einelementige und eine   4-elementige

Comments

Ist das die Lösung, oder ist die Lösung quasi "unendlich" ?

---

Jetzt musst du natürlich noch bei jeder Sorte ausrechnen wieviele es davon

gibt.

Du kannst ja das mit dem Ergebnis der Rekursion überprüfen.

---

Ich weiß leider gerade nicht, wie ich das machen soll, stehe voll auf dem Schlauch...

---

Du sagtest doch, bisher immer mit Rekursion gerechnet.

Dann rechne das doch mal vor und dann können wir ja

mal die kombinatorische Version versuchen.

---

okay , also die Formel ist doch richtig oder:

S(n,k) = S(n-1, k-1) + k*S(n-1,k)

Würde gerne sichergehen, bevor ich falsch weiterrechne.

---

Mit Rekursion geht das leider nicht. Es wird immer "kleiner", das heißt n-2, dann n-3, dann n-4 usw. Ich komme ja nie auf eine Rechnung dann.