Zahlpartition mit Einschränkung |
| 04.06.2011, 11:33 | Spass an Mathe | Auf diesen Beitrag antworten » |
| Zahlpartition mit Einschränkung Hi, ich hab mal eine Frage zu Zahlpartitionen. ich will die Anzahl der geordneten Zahlpartitionen der zahl 13 herausfinden, die ausschliesslich aus den Summanden 3,2 und 1 bestehen. Sie können aber auch nur aus Einsen bestehen, nur Einsen und einer 2 u.s.w. Meine Ideen: Ich hab damit angefangen, mir dass ganze mal schematisch zu überlegen 3+3+3+3+1 = k Partition mit k = 5 3+3+3+2+1+1 = k Partition mit k = 6 3+3+3+1+1+1+1 = k Partition mit k = 7 u.s.w. Das Ganze scheitert aber schon im Ansatz, weil mit ja auch Summmanden > 3 mit eingeschlossen werden. Kann mir jemand einen Tipp geben, wie ich solche Fälle auusschliessen kann, bzw. wie ich zu einem rechnerischen Ansatz komme? viele Grüsse |
||
| 04.06.2011, 12:12 | Suffi | Auf diesen Beitrag antworten » |
einfach durchzählen, ist in endlicher Zeit machbar |
||
| 04.06.2011, 12:28 | Spass an Mathe | Auf diesen Beitrag antworten » |
und wenn wir aus der 13 eine 90 machen? ist das dann immer noch in endlicher Zeit machbar? 
ich hab die 13 nur als beispiel angeführt. die tatsächliche Zahl, mit der ich da arbeiten muss, ist deutlich grösser |
||
| 04.06.2011, 13:54 | HAL 9000 | Auf diesen Beitrag antworten » |
Versuch doch, eine geeignete Rekursionsformel für die Anzahl der Partitionen von mit Summanden zu finden. Dazu noch die geeigneten Startwerte, und man kann tatsächlich eine explizite Formel für das von dir gesuchte entwickeln. |
||
| 04.06.2011, 17:24 | Spass an Mathe | Auf diesen Beitrag antworten » |
hab mir dazu Gedanken gemacht: die letzte Summand der Partition kann eine 1, 2 oder 3 sein. dann könnte eine Rekursionsformel unter Umständen so aussehen? : f( n , k<=3 ) = 3* f ( n-3 , k <= 3 ) + 3* f ( n-2 , k <= 3 ) + 3 * f ( n-1 , k <= 3 ) Also wie gesagt, gibt es drei Fälle, und für jeden der drei Fälle wieder 3.. u.s.w. würde dann aber ziemlich schnell eine ziemlich massive Zahl werden.. |
||
| 04.06.2011, 17:35 | HAL 9000 | Auf diesen Beitrag antworten » |
Nach der Rekursionsformel zu urteilen, stellt dein was ganz anderes dar als mein . 
Ich hatte jedenfalls an sowas wie gedacht, mit den Startwerten für alle sowie für alle . Für ergibt (*) nach kurzer Überlegung , der nächste Schritt wäre dann . Zur Erklärung von (*): Der erste Summand zählt die Partitionen, deren größter Summand gleich ist, der zweite Summand den Rest, d.h., wo der größte Summand kleiner als ist, mit anderen Worten . |
||
| Anzeige | ||
|
|
||
| 04.06.2011, 18:07 | Spass an Mathe | Auf diesen Beitrag antworten » |
hmmm.. liegt, vielleicht an meinen Kenntnissen, aber da blick ich nicht durch. Wie gesagt geht es darum, wie sich eine Zahl aus 1er 2er und 3er Summanden zusammen setzen kann, bzw. wie die Zahl in der Folge entsteht. Betrachten wir dass mal analog zu einem Basketballspiel (worum es in der Aufgabe, die ich lösen muss, tatsächlich auch geht
)dann können die ersten 1-3 Punkte ja entstehen, in dem ich einen Punkt mache, z.B. Freiwurf, oder 2 Punkte, oder 3 Punkte mache. sprich, die erste Punktaktion ( Summand ) , kann 1 2 oder 3 sein. dass sind ja in jedem Fall schon mal drei Möglichkeiten. Für die nächsten Punkte ( sprich den nächsten Summand ), gibt es wieder drei möglichkeiten. also mit anderen Worten 3 * 3 möglichkeiten, aus welchen und in welcher Reihenfolge sich die ersten 2 Summanden sich zusammen setzen können. Trotzdem danke für deine Hilfe. |
||
| 04.06.2011, 18:55 | HAL 9000 | Auf diesen Beitrag antworten » |
Ich bin eigentlich nach deinen Ausführungen im Eröffnungsbeitrag davon ausgegangen, dass bei dir die Reihenfolge der Summanden keine Rolle spielt, d.h., dass du z.B. 3+3+3+3+1 und 3+1+3+3+3 als ein- und dieselbe Zerlegung ansiehst. In deinem letzten Beitrag aber scheinst du das nun wieder anders zu sehen. Wäre schön, wenn du dich für eine Variante entscheidest.
|
||
| 04.06.2011, 19:12 | Spass an Mathe | Auf diesen Beitrag antworten » |
Hätte mich von Anfang an präziser ausdrücken müssen. Das war mein Fehler. Die Reihenfolge, so wie in dem Basketballbeispiel ist absolut relevant. muss mich entschuldigen. 
|
||
|
|
