Auftreten von k in Kompositionen in n

Neue Frage »

gothino Auf diesen Beitrag antworten »
Auftreten von k in Kompositionen in n
Hallo,

folgende Aufgabe:

Sei . Zeige daß unter allen Kompositionen von der Teil genau mal auftritt.

Dazu ein Bsp: n = 3, k = 2, 2 tritt in den Kompositionen 1+2, 2+1 auf, also zweimal

Was ich bis jetzt weiß ist wieviele Kompositionen von n mit genau k Summanden es gibt, wieviele Kompositionen von n es insgesamt gibt und warum das so ist (Bijektion auf Potenzmenge von [n-1].
Leider hab ich noch keine Idee wie man auf obige Formel kommt?
Danke und LG
Gothino
AD Auf diesen Beitrag antworten »

Unter "Komposition" verstehst du also eine Darstellung von als Summe positiver ganzer Zahlen, wobei die Reihenfolge der Summanden Beachtung findet, ist das so?

Wie lautet denn genau die Bijektion, die dich zur Anzahl der Kompositionen bringt? Ich habe den starken Verdacht, dass dir diese Bijektion auch bei der Bestimmung der hier gesuchten Anzahl hilft. smile


P.S.: kann irgendwie nicht stimmen: Im Fall kommt da heraus, eine ziemliche unsinnige "Anzahl".

EDIT: Ok, hat sich geklärt: Deine Anzahlformel gilt ganz einfach nur für , das solltest du entsprechend korrigieren!
gothino Auf diesen Beitrag antworten »

Hallo

Ja so verstehe ich Kompositionen. Werden anscheinend auch geordnete (Zahl-)Partitionen genannt

Stimmt dass das Ergebnis für k = n keinen Sinn macht, die Bedingung steht genau so in der Aufgabe, muss ein Fehler sein:

Die Bijektion lautet folgendermaßen:
Sei A ... Menge der Tupel die die Kompositionen von n mit k Komponenten repräsentieren, also





Sehe aber nicht wie mir diese Bijektion helfen soll verwirrt
also inwieweit die eindeutig zugeordnete Teilmenge von P([n-1]) mir hilft zu bestimmen wie oft k in der dazugehörigen Komposition vorkommt. Genau diese Information geht ja mehr oder weniger verloren??
LG
gothino
AD Auf diesen Beitrag antworten »

Zitat:
Original von gothino


Das rechts ergibt wenig Sinn: ist das letzte zur Verfügung stehende Element... verwirrt
gothino Auf diesen Beitrag antworten »

tschuldingung, sollte k-1 heißen: Ist schon editiert
AD Auf diesen Beitrag antworten »

Ok, ich hatte eine andere Bijektion im Sinn - zur Beschreibung dieser Bijektion zunächst ein Beispiel einer Komposition von :



Dabei soll für eine "interne" Addition zur Erzeugung der Komposition stehen. Dieser speziellen Komposition wird nun das -Tupel zugeordnet.

Auf diese Weise hat man an genau Stellen jeweils entweder ein oder zu platzieren, jede dieser Zuordnungen ergibt eine andere Komposition.


Ein Summand in einer Komposition äußert sich in dieser Bijektion dann durch genau aufeinander folgende und davor und dahinter (falls nicht am Rande) jeweils ein .
 
 
gothino Auf diesen Beitrag antworten »

Super, danke, das schaut vielversprechend aus smile . Muss nun leider außer Haus aber werd mir das später noch genauer überlegen
lg
gothino
gothino Auf diesen Beitrag antworten »

Hab's mir angeschaut, aber ich komm einfach nicht drauf nach welchem Schema man diese Bijektion auswerten soll / kann, v.a. um die Frage zu beantworten wie oft ein bestimmtes Element vorkommt verwirrt
AD Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Ein Summand in einer Komposition äußert sich in dieser Bijektion dann durch genau aufeinander folgende und davor und dahinter (falls nicht am Rande) jeweils ein .

Zähle die möglichen (k-1)-Sequenzen beginnend an einer festen Stelle innerhalb der (n-1) Zeichen! Möglich sind da , wobei den Randfällen (kein + davor) sowie (kein + danach) eine besondere Bedeutung zukommt.
gothino Auf diesen Beitrag antworten »

Ich gebe also vor dass sich an der m-ten Stelle eine k-1 lange Sequenz von befindet, und weiß dass sich an der Stelle vorher und nachher ein befinden muss. An allen anderen Stellen kann sich ein oder befinden, es gibt also insgesamt Möglichkeiten für (bzw. Möglichkeiten für m = 1 oder m = n-k+1).
Insgesamt ergeben sich also Möglichkeiten.

In dieser Berechnung gibt es allerdings Doppelzählungen, um die muss man die Anzahl wieder reduzieren?
bin ich sehr weit weg?
lg
gothino
AD Auf diesen Beitrag antworten »

Welche Doppelzählungen meinst du? Etwas, dass in meinem obigen Beispiel

8 = 2 + 3 + 2 + 1

die "2" doppelt gezählt wird? Das ist ja auch so gewollt!

Oder meinst du was anderes? verwirrt
gothino Auf diesen Beitrag antworten »

Ja genau, zuerst zähle ich die Anzahl aller Möglichkeiten für die erste 2 (bei m = 1), also

. Fünf Fragezeichen bedeuten Möglichkeiten, also Kompositionen wo an der ersten Stelle eine 2 vorkommt.

Später zähle ich die Möglichkeiten für m = 6: , also Möglichkeiten, wo die Komposition an der vorletzten STelle eine 2 hat.
Die von dir genannte Komposition fällt aber unter beide Möglichkeiten, wird also doppelt gezählt.
Wie kann man das wieder bereinigen?
Vielleicht habe ich aber auch mißverstanden wie genau man an Stelle m zählen soll?
lg
gothino
AD Auf diesen Beitrag antworten »

Ich zitiere mal die Aufgabenstellung

Zitat:
Original von gothino
Zeige daß unter allen Kompositionen von der Teil genau mal auftritt.


Das ist was anderes als

Zitat:
Zeige daß es unter allen Kompositionen von genau Kompositionen gibt, wo der Summand auftritt.


Nehmen wir mal das Beispiel n=3,k=1: Da gibt es die 4 Kompositionen

3
1+2
2+1
1+1+1

In 3 der 4 Kompositionen kommt die "1" vor, aber sie kommt summa summarum insgesamt 5mal vor! Und das ist genau das, was gemäß



herauskommt.



P.S.: Vielleicht hast du's noch nicht gemerkt - aber du bist fertig: Es ist nun mal

. smile
gothino Auf diesen Beitrag antworten »

Eh super Finger1 , Warum hast du mir das nicht gleich gesagt smile

Ich hatte die Fragestellung schon richtig verstanden, das mit der Doppelzählung war einfach ein Denkfehler von mir: Dabei spielt es gar keine Rolle.
Also tausend dank für deine Hilfe
lg
gothino
AD Auf diesen Beitrag antworten »

Zitat:
Original von gothino
Warum hast du mir das nicht gleich gesagt

Hab ich doch:

Zitat:
Original von Arthur Dent
Welche Doppelzählungen meinst du? Etwas, dass in meinem obigen Beispiel

8 = 2 + 3 + 2 + 1

die "2" doppelt gezählt wird? Das ist ja auch so gewollt!

Aber das geht mir hier oft so: Dass die Leute erst beim dritten, vierten Mal endlich zuhören - manchmal auch gar nicht, hier zum Glück aber doch. Augenzwinkern
gothino Auf diesen Beitrag antworten »

Ich hab dir schon zugehört, nur haben's meine grauen Zellen nicht gleich verarbeiten können smile
Rone Auf diesen Beitrag antworten »

super Beweis, hat mir auch sehr geholfen, vielen dank Freude
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »