Siebformel für Anzahl der Lösungen für eine Gleichung

Neue Frage »

eisverticker Auf diesen Beitrag antworten »
Siebformel für Anzahl der Lösungen für eine Gleichung
Hallo liebe Matheboard-Community,

Ich habe ein Problem bei einer Aufgabe, wo ich die Siebformel (Prinzip der Inklusion und Exklusion) anwenden soll und ich hoffe ihr könnt mich da auf den richtigen Weg führen.
Wir haben die Gleichung
mit
und
sowie (die einzelnen Summanden sind also maximal b groß)

Sei nun und
Nun möchte ich die Anzahl der möglichen Lösungen |G| für die obige Gleichung herausbekommen:
1. Fall:

weil es nicht möglich ist in der Summe k zu erhalten (durch Wahl von b)

2. Fall: sonst
Hier liegt nun das Problem, für die Siebformel muss ich eine geeignete Wahl von Teilmengen mit

Es muss also auch möglich sein, den Schnitt der Teilmengen zu berechnen.

Mein Ansatz wäre gewesen die Lösungen der Gleichung als Wörter der Länge k zu betrachteni


aber da konnte ich mir leider auch keine Lösung herleiten.

Grüße eisverticker
HAL 9000 Auf diesen Beitrag antworten »

Sei die Menge aller Lösungstupel der Gleichung , d.h., ohne die Restriktion . Deren Anzahl ist . Dann betrachtet man folgende Teilmengen von :

... Menge aller Tupel aus mit der Eigenschaft

In dem Sinne ist dann , und die Siebformel kann drauf los gelassen werden.
 
 
eisverticker Auf diesen Beitrag antworten »

Vielen Dank für die Antwort, ich habe das ganze jetzt mal versucht in die Siebformel einzusetzen

Sei


und in der Siebformel

habe ich für die Mächtigkeit des Schnitts folgendes gewählt:


Der Gedanke dahinter ist, dass ich die aus dem Tupel "entferne" und die restlichen Kombination
betrachte und k entsprechend um die Summe der x_i verringere.
Allerdings bin ich damit nicht wirklich zufrieden, da ja ist und somit b unterschiedliche Werte annehmen könnte und damit auch die Mächtigkeit des Schnitts davon abhängt.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von eisverticker
und in der Siebformel

Stimmt nicht: Aus folgt .

Wenn man für den "leeren" Durchschnitt vereinbart, kann man sogar kurz und bündig schreiben. Augenzwinkern

Zitat:
Original von eisverticker
Der Gedanke dahinter ist, dass ich die aus dem Tupel "entferne"

Nur weil ist, darfst du sie noch lange nicht entfernen. unglücklich

Lass sie drin und berücksichtige dabei die Äquivalenz

.


Um es noch deutlicher zu sagen: Es ist bijektiv abbildbar auf die Menge

,

indem man setzt.

Das ganze macht natürlich nur für , also Sinn; für gilt sowieso .

EDIT (27.02.): Soso, wieder mal ist die Karawane weitergezogen, ohne sich nochmal umzublicken...
insertUser Auf diesen Beitrag antworten »
Nicht bijektiv ?
Hallo HAL 9000,
ich bin nicht wirklich überzeugt, dass die von Dir beschriebene Abbildung bijektiv ist, bzw. ob der Gedankengang richtig ist. Schließlich würde die Tupelmenge erlauben, dass man ein setzt, mit . Das wäre aber im Durchschnitt der Gi's nicht enthalten oder ?

P.S. Ich schaue mir die Seite ziemlich genau ein Jahr später an, vermute mal, dass ich von der gleichen Uni komme wie der einverticker Big Laugh Hast mir auf jeden Fall schonmal weitergeholfen, danke Dir !
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von insertUser
Schließlich würde die Tupelmenge erlauben, dass man ein setzt, mit . Das wäre aber im Durchschnitt der Gi's nicht enthalten oder ?

Wieso nicht? Der Durchschnitt der , um die es da geht, läuft ja auch nur über die Indexmenge statt über ganz , und für Indizes außerhalb (wie das von dir angesprochene ) können die beliebig nichtnegativ sein, da gibt es keine weiteren Bedingungen als dann noch die Summenbedingung.


Oder anders ausgedrückt:

enthält alle Tupel, die an den Stellen Werte enthalten. Du hast daraus wohl automatisch die Schlussfolgerung gezogen, dass an den anderen Stellen automatisch gilt? Unsinn, diese Menge wäre dann

,

aber von der Menge spreche ich nicht, und die ist auch von keinerlei Interesse im Rahmen dieser Siebformelbetrachtung. unglücklich

Jetzt "überzeugt" ? Big Laugh
insertUser Auf diesen Beitrag antworten »
Weiter auflösen
Danke für Deine Antwort, geht ja schneller als die Polizei erlaubt smile

Hab die Bijektion jetzt verstanden. Wenn ich das richtig sehe, dann entspricht die Mächtigkeit der Tupelmenge jetzt ja dem Verteilen ohne Beachtung der Reihenfolge und mit Wiederholung, also .
Da es auch egal ist, welche Indizes genau in enthalten sind, spielt nur die Mächtigkeit der Menge eine Rolle. Damit komme ich auf folgende Rechnung:


Sry für das fehlende Alignment, bin nicht so ganz lateX-stark.
Sieht für mich erstmal richtig aus, vielen Dank schomal im Voraus für evt. Korrekturen Augenzwinkern
HAL 9000 Auf diesen Beitrag antworten »

Nein, wie oben schon erwähnt ist , und analog dazu ist auch , so dass man insgesamt zu



kommt. Auch das mit dem eingeschränkten oberen Summenende ist ernst zu nehmen, bei bestimmten Parameterkonstellationen sowie "großen" könnte u.U. sogar negativ werden, was kombinatorikanzahlmäßig nun gar keinen Sinn macht. unglücklich
insertUser Auf diesen Beitrag antworten »

Dass das Omega falsch aufgelöst ist sehe ich deutlich (habe wohl aus Versehen n statt k geschrieben).
Aber wenn wir uns nochmal das Ding hier anschauen:

Dann müssen wir doch verteilen auf n mögliche Summanden oder ? Ich kann gerade nicht sehen, wieso dann bei Deiner Auflösung des Durchschnitts im Binomialkoeffizienten steht und nicht oder (die Rollen von n und k sind hier doch sozusagen "vertauscht").
Lieben Dank auch für den Hinweis mit dem oberen Summenende, da wäre ich sonst ungebremst reingelaufen smile
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von insertUser
Ich kann gerade nicht sehen, wieso dann bei Deiner Auflösung des Durchschnitts im Binomialkoeffizienten steht und nicht oder

Dann schau dir die Formel für die Anzahl bei den "Kombinationen mit Wiederholung" einfach noch mal richtig an. Ich kann doch nicht zigmal hier predigen, dass du einfach nur richtig einsetzen musst - soviel Selbständigkeit kann man ja im Hochschulbereich erwarten. unglücklich

https://de.wikipedia.org/wiki/Kombinatio...endarstellung_2
insertUser Auf diesen Beitrag antworten »

ok alles klar, jetzt sehe ich es auch. Vielen Dank nochmal !
Neue Frage »
Antworten »



Verwandte Themen

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