Stars and Bars

Entwicklung eines Zufallsgenerators für gleichverteilte Mikrozustände (Implementierung in R)

Nach dem Postulat der statistischen Mechanik besitzen alle Mikrozustände, die ein System annehmen kann, die gleiche Wahrscheinlichkeit. Für zahlreiche Simulationen benötigt man einen Zufallsgenerator, der diese gleichverteilten Mikrozustände erzeugt. Dieser Zufallsgenerator wird in der Programmiersprache R entwickelt, die Erklärungen sind aber so allgemein gehalten, dass man sie leicht in eine andere Programmiersprache übersetzen kann.

Makrozustand statistische Mechanik Gleichverteilung Mikrozustand R (Programmiersprache) Zufallsgenerator Stars and Bars Partition Ziehung ohne Zurücklegen

Spezielle Abzählprobleme: Partitionen

Das Abzählproblem, nicht unterscheidbare Kugeln auf nicht unterscheidbare Urnen zu verteilen ist äquivalent zum Problem zu einer ganzen Zahl Z Zerlegung in L Summanden zu finden. Eine derartige Zerlegung wird als Partition bezeichnet. Wie viele Partitionen es gibt, wird für mehrere Fälle untersucht: Die Vertauschung der Reihenfolge zählt (oder zählt nicht) als neue Partition, die Null ist als Summand zugelassen, die Länge der Partition wird nicht festgelegt. Man kann für diese Abzählprobleme zwar Rekursionsformeln angeben, man kann mit einfachen Mitteln aber keine expliziten Formeln angeben, die die Rekursionsformeln lösen.

Abzählprobleme ungeordnete Partition Rekursion Stars and Bars Partition geordnete Partition Kombinationen mit Wiederholungen Kombinatorik Rekursionsformel Rekursionsanfang

Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars

Kombinationen mit Wiederholungen treten in mehreren Abzählproblemen auf, die zunächst sehr unterschiedlich wirken. Es wird ihre Äquivalenz gezeigt und die Formel hergeleitet, wie man die Anzahl aller Kombinationen mit Wiederholungen berechnet. Dazu verwendet man die Methode Stars and Bars. In den R-Skripten wird ein einfacher Algorithmus gezeigt, wie man die Menge alle Kombinationen mit Wiederholungen rekursiv berechnet.

Abzählprobleme Kombination Binomialkoeffizient Rekursion Stars and Bars Partition Kombinationen mit Wiederholungen Kombinatorik Rekursionsformel Rekursionsanfang