Anzahl zirkulärer Kompositionen

11/07/2012 - 13:23 von Hartmut Leister | Report spam
Hallo Newsgroup,

ich habe ein kombinatorisches Problem:
Wie viele verschiedene Möglichkeiten gibt es, s als Summe von k
Elementen aus {0,..,g} darzustellen, wobei die Reihenfolge relevant ist.

Wer kennt dafür eine Berechnungsvorschrift?

Beste Grüße
Hartmut



Das ganze ist Teilproblem folgender Frage:
Wie viele (endliche) Folgen gibt es mit folgenden Eigenschaften:
- die Folge hat k Elemente
- die Summe ihrer Elemente ist s
- die Folgenelemente sind nichtnegative ganze Zahlen
- die Folgen sind paarweise zirkulàr nichtàquivalent

Zwei Folgen heißen zirkulàr àquivalent, falls man die eine durch
Rotation/Shift auf die andere abbilden kann.

Demnach wàren also (2 2 1 ) und (2 1 2) zirkulàr àquivalent.

Mein Ansatz ist folgender:
(1) ich zàhle nur die Folgen, bei denen das erste Element bereits das
größte ist
(2) falls das erste Element g das einzige Maximum ist (das gilt für
g>s/2), erhàlt man die Anzahl der entsprechenden Folgen/Zyklen mit
erstem Element g duch die Kompositionszahl (siehe [1])
(3) falls das erste Element g=s/2, kann man die Anzahl der Duplikate
recht simpel abzàhlen (das sind ceil(k/2)-1))
(4) falls das erste Element g<s/2, kommen mitunter viele Duplikate vor -
siehe Beispiel

Ich illustriere das kurz am Beispiel k=3, s=5. Die Zyklen / Folgen sind:
1 : ( 5 0 0 )
2 : ( 4 1 0 )
3 : ( 4 0 1 )
4 : ( 3 2 0 )
5 : ( 3 0 2 )
6 : ( 3 1 1 )
7 : ( 2 2 1 )
8 : ( 2 1 2 ) -> àquivalent zu 7
Hier wàre also die gesuchte Zahl 8-1 = 7

[1] http://mathworld.wolfram.com/Composition.html
 

Lesen sie die antworten

#1 Ivo Siekmann
11/07/2012 - 20:33 | Warnen spam
On 11/07/12 11:23 PM, Hartmut Leister wrote:
Hallo Newsgroup,

ich habe ein kombinatorisches Problem:
Wie viele verschiedene Möglichkeiten gibt es, s als Summe von k
Elementen aus {0,..,g} darzustellen, wobei die Reihenfolge relevant ist.

Wer kennt dafür eine Berechnungsvorschrift?

Beste Grüße
Hartmut



Das ganze ist Teilproblem folgender Frage:
Wie viele (endliche) Folgen gibt es mit folgenden Eigenschaften:
- die Folge hat k Elemente
- die Summe ihrer Elemente ist s
- die Folgenelemente sind nichtnegative ganze Zahlen
- die Folgen sind paarweise zirkulàr nichtàquivalent


Ich denke, dies hier koennte weiterhelfen:
http://en.wikipedia.org/wiki/Partit..._theory%29

Mit Mathematica lassen sich Partitionen mithilfe des Befehls
IntegerPartitions berechnen.

Beste Gruesse
Ivo

Ähnliche fragen