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

22.02.2017, 10:06

eisverticker

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 $\begin{eqnarray*} x_1+...+x_n = k \end{eqnarray*}$
mit $\begin{eqnarray*} k,n, b \in \mathbb{N} \end{eqnarray*}$
und $\begin{eqnarray*} x_i \in \mathbb{N}_0 \end{eqnarray*}$
sowie $\begin{eqnarray*} 0 \le x_i \le b \end{eqnarray*}$ (die einzelnen Summanden sind also maximal b groß)

Sei nun $\begin{eqnarray*} B = \{ 0, ..., b \} \end{eqnarray*}$ und $\begin{eqnarray*} G = \{ (x_1, ..., x_n) \in B^n | \sum_{i=1}^n x_i = k \} \end{eqnarray*}$
Nun möchte ich die Anzahl der möglichen Lösungen |G| für die obige Gleichung herausbekommen:
1. Fall: $\begin{eqnarray*} n\cdot b < k \end{eqnarray*}$
$\begin{eqnarray*} |G| = \emptyset \end{eqnarray*}$
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 $\begin{eqnarray*} G_i \end{eqnarray*}$ mit
$\begin{eqnarray*} |G| = |\bigcup_{i=1}^m G_i| = \sum_{I \subseteq \{1,...,m \}} (-1)^{|I|+1} \cdot |\bigcap_{i \ \in I } A_i| \end{eqnarray*}$
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
$\begin{eqnarray*} w=x_1^{c_1}...x_n^{c_n} \end{eqnarray*}$
$\begin{eqnarray*} |w| = k \end{eqnarray*}$
aber da konnte ich mir leider auch keine Lösung herleiten.

Grüße eisverticker

22.02.2017, 10:22

HAL 9000

Auf diesen Beitrag antworten »

Sei $\begin{align*} \Omega \end{align*}$ die Menge aller Lösungstupel $\begin{align*} (x_1,\ldots,x_n)\in \mathbb{N}_0^n \end{align*}$ der Gleichung $\begin{align*} x_1+\ldots+x_n=k \end{align*}$ , d.h., ohne die Restriktion $\begin{align*} x_i\leq b \end{align*}$ . Deren Anzahl ist $\begin{align*} |\Omega| = \binom{n+k-1}{n-1} \end{align*}$ . Dann betrachtet man folgende Teilmengen von $\begin{align*} \Omega \end{align*}$ :

$\begin{align*} G_i \end{align*}$ ... Menge aller Tupel $\begin{align*} (x_1,\ldots,x_n) \end{align*}$ aus $\begin{align*} \Omega \end{align*}$ mit der Eigenschaft $\begin{align*} x_i\geq b+1 \end{align*}$

In dem Sinne ist dann $\begin{align*} G = \Omega \setminus \left( \bigcup_{i=1}^n G_i \right) \end{align*}$ , und die Siebformel kann drauf los gelassen werden.

23.02.2017, 01:11

eisverticker

Auf diesen Beitrag antworten »

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

Sei $\begin{eqnarray*} f(n,k) = \binom{n+k-1}{n-1} \end{eqnarray*}$
$\begin{eqnarray*} G_i = \{ (x_1,...,x_n ) \in \mathbb{N}_0^n | x_i > b \} \end{eqnarray*}$

und in der Siebformel $\begin{eqnarray*} |G| = |\bigcup_{i=1}^m G_i| = \sum_{I \subseteq \{1,...,m \}} (-1)^{|I|+1} \cdot |\bigcap_{i \ \in I } G_i| \end{eqnarray*}$

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

$\begin{eqnarray*} |\bigcap_{i \ \in I } G_i| = f(n-|I|, k-\sum_{i \in I} x_i) \end{eqnarray*}$
Der Gedanke dahinter ist, dass ich die $\begin{eqnarray*} x_i > b \end{eqnarray*}$ 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 $\begin{eqnarray*} b < x_i \leq k \end{eqnarray*}$ ist und somit b unterschiedliche Werte annehmen könnte und damit auch die Mächtigkeit des Schnitts davon abhängt.

23.02.2017, 07:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von eisverticker
und in der Siebformel $\begin{eqnarray*} |G| = |\bigcup_{i=1}^m G_i| = \sum_{I \subseteq \{1,...,m \}} (-1)^{|I|+1} \cdot |\bigcap_{i \ \in I } G_i| \end{eqnarray*}$

Stimmt nicht: Aus $\begin{align*} G = \Omega \setminus \left( \bigcup_{i=1}^n G_i \right) \end{align*}$ folgt $\begin{align*} |G| = |\Omega| - \left|\bigcup_{i=1}^n G_i\right| = |\Omega| - \sum_{\emptyset\neq I\subseteq\{1,\ldots,n\}} (-1)^{|I|+1} \cdot \left|\bigcap_{i\in I} G_i\right| \end{align*}$ .

Wenn man für den "leeren" Durchschnitt $\begin{align*} \bigcap_{i\in \emptyset} G_i := \Omega \end{align*}$ vereinbart, kann man sogar kurz und bündig $\begin{align*} |G| = \sum_{I\subseteq\{1,\ldots,n\}} (-1)^{|I|} \cdot \left|\bigcap_{i\in I} G_i\right| \end{align*}$ schreiben. Augenzwinkern

Zitat:

Original von eisverticker
Der Gedanke dahinter ist, dass ich die $\begin{eqnarray*} x_i > b \end{eqnarray*}$ aus dem Tupel "entferne"

Nur weil $\begin{align*} x_i>b \end{align*}$ ist, darfst du sie noch lange nicht entfernen. unglücklich

Lass sie drin und berücksichtige dabei die Äquivalenz

$\begin{align*} x_i\in\mathbb{N}_0,x_i\geq b+1 \quad\Longleftrightarrow\quad (x_i-b-1)\in\mathbb{N}_0 \end{align*}$ .

Um es noch deutlicher zu sagen: Es ist $\begin{align*} \bigcap_{i\in I} G_i \end{align*}$ bijektiv abbildbar auf die Menge

$\begin{align*} \left\{ (x_1',\ldots,x_n')\in \mathbb{N}_0^n \bigm| x_1'+\ldots+x_n' = k-|I|\cdot (b+1) \right\} \end{align*}$ ,

indem man $\begin{align*} x_i' = \begin{cases} x_i-b-1 & \;\mbox{für}\; i\in I\\ x_i & \;\mbox{für}\; i\in \{1,\ldots,n\}\setminus I\end{cases} \end{align*}$ setzt.

Das ganze macht natürlich nur für $\begin{align*} k-|I|\cdot (b+1) \geq 0 \end{align*}$ , also $\begin{align*} |I|\leq \frac{k}{b+1} \end{align*}$ Sinn; für $\begin{align*} |I|>\frac{k}{b+1} \end{align*}$ gilt sowieso $\begin{align*} \bigcap_{i\in I} G_i = \emptyset \end{align*}$ .

EDIT (27.02.): Soso, wieder mal ist die Karawane weitergezogen, ohne sich nochmal umzublicken...

20.02.2018, 15:42

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 $\begin{eqnarray*} x_{j} \geq b + 1 \end{eqnarray*}$ setzt, mit $\begin{eqnarray*} j \notin I \end{eqnarray*}$ . 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 !

20.02.2018, 17:33

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von insertUser
Schließlich würde die Tupelmenge erlauben, dass man ein $\begin{eqnarray*} x_{j} \geq b + 1 \end{eqnarray*}$ setzt, mit $\begin{eqnarray*} j \notin I \end{eqnarray*}$ . Das wäre aber im Durchschnitt der Gi's nicht enthalten oder ?

Wieso nicht? Der Durchschnitt der $\begin{eqnarray*} G_i \end{eqnarray*}$ , um die es da geht, läuft ja auch nur über die Indexmenge $\begin{eqnarray*} I \end{eqnarray*}$ statt über ganz $\begin{eqnarray*} \{1,\ldots,n\} \end{eqnarray*}$ , und für Indizes außerhalb $\begin{eqnarray*} I \end{eqnarray*}$ (wie das von dir angesprochene $\begin{eqnarray*} j \end{eqnarray*}$ ) können die $\begin{eqnarray*} x_j \end{eqnarray*}$ beliebig nichtnegativ sein, da gibt es keine weiteren Bedingungen als dann noch die Summenbedingung.

Oder anders ausgedrückt:

$\begin{eqnarray*} \bigcap_{i\in I} G_i \end{eqnarray*}$ enthält alle Tupel, die an den Stellen $\begin{eqnarray*} i\in I \end{eqnarray*}$ Werte $\begin{eqnarray*} \geq b+1 \end{eqnarray*}$ enthalten. Du hast daraus wohl automatisch die Schlussfolgerung gezogen, dass an den anderen Stellen automatisch $\begin{eqnarray*} \leq b \end{eqnarray*}$ gilt? Unsinn, diese Menge wäre dann

$\begin{eqnarray*} \bigcap_{i\in I} G_i \cap \bigcap_{j\in \{1,\ldots,n\}\setminus I} G_j^c \end{eqnarray*}$ ,

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

Jetzt "überzeugt" ? Big Laugh

20.02.2018, 21:13

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 $\begin{align*} \left(\begin{array}{c}n + k - 1 \\ k\end{array}\right) \end{align*}$ .
Da es auch egal ist, welche Indizes genau in $\begin{align*} I \end{align*}$ enthalten sind, spielt nur die Mächtigkeit der Menge eine Rolle. Damit komme ich auf folgende Rechnung:

$\begin{align*} |G| = |\Omega| - \left|\bigcup_{i=1}^n G_i\right|\\ |G| = |\Omega| - \sum_{\emptyset\neq I\subseteq\{1,\ldots,n\}} (-1)^{|I|+1} \cdot \left|\bigcap_{i\in I} G_i\right|\\ |G| = |\Omega| - \sum_{\emptyset\neq I\subseteq\{1,\ldots,n\}} (-1)^{|I|+1} \cdot \left(\begin{array}{c}k-|I|(b+1)+n-1 \\ n\end{array}\right)\\ |G| = |\Omega| - \sum_{p=1}^{n} (-1)^{p+1} \cdot \left(\begin{array}{c}n \\ p\end{array}\right) \cdot \left(\begin{array}{c}k-|I|(b+1)+n-1 \\ n\end{array}\right)\\ |G| = \left(\begin{array}{c}n+k-1 \\ n\end{array}\right) - \sum_{p=1}^{n} (-1)^{p+1} \cdot \left(\begin{array}{c}n \\ p\end{array}\right) \cdot \left(\begin{array}{c}k-|I|(b+1)+n-1 \\ n\end{array}\right)\\ \end{align*}$
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

20.02.2018, 21:26

HAL 9000

Auf diesen Beitrag antworten »

Nein, wie oben schon erwähnt ist $\begin{eqnarray*} |\Omega| = \binom{n+k-1}{n-1} \end{eqnarray*}$ , und analog dazu ist auch $\begin{eqnarray*} \left| \bigcap_{i\in I} G_i \right| = \binom{n+k-|I|(b+1)-1}{n-1} \end{eqnarray*}$ , so dass man insgesamt zu

$\begin{eqnarray*} |G| = \sum_{p=0}^{\min\left\{n,\left\lfloor \frac{k}{b+1} \right\rfloor\right\}} (-1)^p \binom{n}{p}\cdot \binom{n+k-p(b+1)-1}{n-1} \end{eqnarray*}$

kommt. Auch das mit dem eingeschränkten oberen Summenende ist ernst zu nehmen, bei bestimmten Parameterkonstellationen sowie "großen" $\begin{eqnarray*} p \end{eqnarray*}$ könnte u.U. $\begin{eqnarray*} \binom{n+k-p(b+1)-1}{n-1} \end{eqnarray*}$ sogar negativ werden, was kombinatorikanzahlmäßig nun gar keinen Sinn macht. unglücklich

20.02.2018, 22:17

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:
$\begin{align*} \left\{ (x_1',\ldots,x_n')\in \mathbb{N}_0^n \bigm| x_1'+\ldots+x_n' = k-|I|\cdot (b+1) \right\} \end{align*}$
Dann müssen wir doch $\begin{align*} \ k-|I|\cdot (b+1) \end{align*}$ verteilen auf n mögliche Summanden oder ? Ich kann gerade nicht sehen, wieso dann bei Deiner Auflösung des Durchschnitts im Binomialkoeffizienten $\begin{align*} n-1 \end{align*}$ steht und nicht $\begin{align*} n \end{align*}$ oder $\begin{align*} \ k-|I|\cdot (b+1) -1 \end{align*}$ (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

20.02.2018, 22:21

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 $\begin{align*} n-1 \end{align*}$ steht und nicht $\begin{align*} n \end{align*}$ oder $\begin{align*} \ k-|I|\cdot (b+1) -1 \end{align*}$

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

21.02.2018, 19:56

insertUser

Auf diesen Beitrag antworten »

ok alles klar, jetzt sehe ich es auch. Vielen Dank nochmal !

Neue Frage »

Antworten »

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

Verwandte Themen