Quersumme bei n<100000

20.08.2012, 18:58

chenino

Quersumme bei n<100000

Hallo
Ich hab mehrere Aufgaben der Gleichen Art und zu allen auch Lösungen, allerdings kann ich die Lösungswege nicht Nachvollziehen.
Die Aufgabe ist jedes Mal, wie viele ganze Zahlen zwischen 1 und y gibt es, deren Queersumme n ergibt.
nun weiß ich , das bei
$\begin{eqnarray*} x_1 + x_2 + ...+x_k = n \end{eqnarray*}$ gilt
$\begin{eqnarray*} \begin{pmatrix}n+k-1\\k-1 \end{pmatrix} \end{eqnarray*}$
Nun zählen wir dabei aber auch werte, bei denen eines der $\begin{eqnarray*} x_i \end{eqnarray*}$ >=10 ist, was bei natürlichen Zahlen ja nicht der Fall sein darf.
Also müssen wir diese wieder irgendwie abziehen.
In einer der Aufgaben (n=15, 1<x<1000000) kam dazu ein Term $\begin{eqnarray*} \sum\limits_{i=4}^9 \begin{pmatrix} i\\4 \end{pmatrix} \end{eqnarray*}$ der 6 mal (also für jeden Buchstaben einmal) abgezogen wird, um diese Werte rauszufiltern. Ähnliches habe ich auch in anderen Aufgaben gesehen, aber nirgendwo fand ich eine Erklärung, wie dieser Term zustande kam. Weiß dies von euch vielleicht einer und kann mir erklären wie ich diesen bei anderen ähnlichen Aufgaben bilden kann?
Im vorraus schonmal Dankeschön

20.08.2012, 19:14

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von chenino
nun weiß ich , das bei
$\begin{eqnarray*} x_1 + x_2 + ...+x_k = n \end{eqnarray*}$ gilt
$\begin{eqnarray*} \begin{pmatrix}n+k-1\\k-1 \end{pmatrix} \end{eqnarray*}$

Diesen fragmentarischen Stil versteht nur der, der das Problem sowieso schon vorher kennt. Was du hier sagen willst, ist wohl

Zitat:

Es gibt genau $\begin{eqnarray*} \binom{n+k-1}{k-1} \end{eqnarray*}$ verschiedene Tupel $\begin{eqnarray*} (x_1,\ldots,x_k) \end{eqnarray*}$ nichtnegativer ganzer Zahlen mit Summe $\begin{eqnarray*} x_1 + x_2 + \ldots +x_k = n \end{eqnarray*}$ .

Wenigstens ein kleiner Schritt in Richtung derart verständlicher Formulierungen wäre wünschenswert.

Zitat:

Original von chenino
In einer der Aufgaben (n=15, 1<x<1000000) kam dazu ein Term $\begin{eqnarray*} \sum\limits_{i=4}^9 \begin{pmatrix} i\\4 \end{pmatrix} \end{eqnarray*}$ der 6 mal (also für jeden Buchstaben einmal) abgezogen wird, um diese Werte rauszufiltern. Ähnliches habe ich auch in anderen Aufgaben gesehen, aber nirgendwo fand ich eine Erklärung, wie dieser Term zustande kam.

Die Erklärung lautet auf den Punkt gebracht: Siebformel - siehe hier für eine damit entwickelte Komplettformel für dein Problem:

Würfeln

20.08.2012, 19:33

chenino

Auf diesen Beitrag antworten »

Es tut mir leid, wenn meine Formulierung grad nicht so sauber war, bitte das zu verzeihen, hab heute 8 Stunden lernen mit mäßigem Erfolg hinter mir und die letzten 2 Stunden saß ich vor der Aufgabe, deshalb bin ich wohl auch nichtmehr ganz fit.

Die Anmerkung das dies eine Siebformel ist, hatte ich gesehen, allerdings half mir dies auch nicht viel weiter. Gibt es irgendein einfaches Muster, wie ich die Grenzen hierfür setzen kann?
Bei einer Siebformel hatte ich im Kopf, dass das Vorzeichen wechselt, also $\begin{eqnarray*} -1^k \end{eqnarray*}$ und das tat es ja in diesem Falle nicht. Ich verstehe auch nicht wirklich, warum in dem Link v = 5 gewählt wird, da wir doch 6 Augen auf einem Würfel haben, und wieso der Startwert der Summe dort 0 ist, und bei mir 4 erschliesst sich mir grade auch nicht.
$\begin{eqnarray*} s-n \end{eqnarray*}$ verstehe ich auch grade nicht, da ich nicht weiß, welche Bedeutung s hat. Könntest du mir da vielleicht noch nachhelfen?

Versteh mich nicht falsch, ich versuch das Nachzuvollziehen, aber irgendwie entwickelt sich da grad bei mir kein Verständnis...

Danke aber für deine bisherige Antwort

20.08.2012, 19:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von chenino
Ich verstehe auch nicht wirklich, warum in dem Link v = 5 gewählt wird, da wir doch 6 Augen auf einem Würfel haben, und wieso der Startwert der Summe dort 0 ist, und bei mir 4 erschliesst sich mir grade auch nicht.

Ich habe wirklich nicht die geringste Lust, das Würfelbeispiel zu erläutern, zumal es in dem Thread dort gut erklärt ist (Würfelaugenzahl MINUS EINS), du offenbar aber nicht die Muße hast, das zu durchdenken.

Vielleicht entwickeln wir alles nochmal hier gemeinsam, mit deinen Symbolen (in dem Thread haben die ja eine andere Bedeutung). Starten wir mit ein paar Mengendefinitionen:

$\begin{eqnarray*} \Omega \end{eqnarray*}$ ... Menge aller $\begin{eqnarray*} k \end{eqnarray*}$ -Tupel $\begin{eqnarray*} (x_1,\ldots,x_k) \end{eqnarray*}$ nichtnegativer ganzer Zahlen mit Summe $\begin{eqnarray*} x_1+\ldots+x_k=n \end{eqnarray*}$

$\begin{eqnarray*} A_i \end{eqnarray*}$ ... Menge aller $\begin{eqnarray*} k \end{eqnarray*}$ -Tupel $\begin{eqnarray*} (x_1,\ldots,x_k) \end{eqnarray*}$ aus $\begin{eqnarray*} \Omega \end{eqnarray*}$ mit $\begin{eqnarray*} x_i>v \end{eqnarray*}$ (bei dir $\begin{eqnarray*} v=9 \end{eqnarray*}$ )

Die gesuchte Anzahl aller $\begin{eqnarray*} k \end{eqnarray*}$ -Tupel $\begin{eqnarray*} (x_1,\ldots,x_k) \end{eqnarray*}$ aus $\begin{eqnarray*} \Omega \end{eqnarray*}$ mit $\begin{eqnarray*} x_i\leq v \end{eqnarray*}$ für alle $\begin{eqnarray*} i \end{eqnarray*}$ ist nun $\begin{eqnarray*} N = \left| \Omega \setminus \left( \bigcup\limits_{i=1}^k A_i \right) \right| \end{eqnarray*}$ , was man laut Siebformel berechnen kann als

$\begin{eqnarray*} N = \sum_{I\subset\{1,\ldots,k\}} (-1)^{|I|} \left| \bigcap\limits_{i\in I} A_i \right| \end{eqnarray*}$ ,

nochmal sei betont, dass die $\begin{eqnarray*} I \end{eqnarray*}$ -Summation über alle $\begin{eqnarray*} 2^k \end{eqnarray*}$ Teilmengen von $\begin{eqnarray*} \{1,\ldots,k\} \end{eqnarray*}$ verläuft.

Im Fall $\begin{eqnarray*} n \geq |I|(v+1) \end{eqnarray*}$ ist nun aber

$\begin{eqnarray*} \left| \bigcap\limits_{i\in I} A_i \right| = \binom{n-|I|(v+1)+k-1}{k-1} \end{eqnarray*}$ ,

überleg dir mal warum! Betrachte dazu z.B. im Fall $\begin{eqnarray*} I=\{1,3\} \end{eqnarray*}$ für dann $\begin{eqnarray*} (x_1,\ldots,x_k) \in A_1\cap A_3 \end{eqnarray*}$ die Summe

$\begin{eqnarray*} (x_1-v-1) + x_2 + (x_3-v-1) + x_4 + \ldots + x_k = n-2(v+1) \end{eqnarray*}$ .

20.08.2012, 20:00

chenino

Auf diesen Beitrag antworten »

Vielen dank dir, für die Hilfe.
Ich glaub ich versteh das ganze so langsam. Scheiterte bei mir nicht an Muße, sondern unkonzentriertheit und dadurch überlesen, aber ich glaub deine Ausführung hat mir geholfen. Werde das nochmal kurz sacken lassen und dann gleich nochmal durchrechnen smile

Danke fürs schnelle Antworten

20.08.2012, 20:11

HAL 9000

Auf diesen Beitrag antworten »

Im anderen Fall $\begin{eqnarray*} n < |I|(v+1) \end{eqnarray*}$ ist nun einfach

$\begin{eqnarray*} \left| \bigcap\limits_{i\in I} A_i \right| = 0 \end{eqnarray*}$ ,

d.h. es gibt dort keine solchen Tupel. Damit reicht es also, über die Teilmengen $\begin{eqnarray*} |I| \end{eqnarray*}$ mit $\begin{eqnarray*} |I|\leq \frac{n}{v+1} \end{eqnarray*}$ zu summieren. Es gibt es nun genau $\begin{eqnarray*} \binom{k}{j} \end{eqnarray*}$ Teilmengen $\begin{eqnarray*} I \end{eqnarray*}$ mit $\begin{eqnarray*} |I|=j \end{eqnarray*}$ , also bekommt man alles zusammengewurschtelt

$\begin{eqnarray*} N = \sum_{j=0}^{\left\lfloor \frac{n}{v+1} \right\rfloor} (-1)^j \binom{k}{j} \binom{n-j(v+1)+k-1}{k-1} \end{eqnarray*}$ .

Für $\begin{eqnarray*} n=15,k=6,v=9 \end{eqnarray*}$ bekommt man also z.B.

$\begin{eqnarray*} N = \sum_{j=0}^1 (-1)^j \binom{6}{j} \binom{15-10j+5}{5} = \binom{20}{5} - 6\binom{10}{5} = 13\,992 \end{eqnarray*}$ .

20.08.2012, 21:08

chenino

Auf diesen Beitrag antworten »

nochmals vielen lieben dank. Jetzt hast du mir sogar eine Formel gegeben, die ich in der Klausur direkt eingeben kann. Ich bin dir echt dankbar dafür smile

hab einen schönen abend !

20.08.2012, 21:32

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von chenino
Jetzt hast du mir sogar eine Formel gegeben, die ich in der Klausur direkt eingeben kann.

Nun ja, ich hoffe wenigstens, dass du dich bemüht hast, alle Schritte der Entstehung dieser Formel nachzuvollziehen. Ich kenne ja eure Klausuren nicht, aber geben die sich nur mit dem numerischen Ergebnis zufrieden oder wollen sie auch einen Rechenweg? Augenzwinkern

20.08.2012, 22:08

chenino

Auf diesen Beitrag antworten »

Naja, wir müssen es nicht ganz so ausführlich angeben wie du, so eine kurze Erklärung der Formel ala dieser Wert bedeutet das und muss so gewählt werden reicht meist.....Ausser halt es ist nen Beweis verlang, dass sollt dabei nicht der Fall sein.
Ja, ich hab mir Mühe gegeben und hoffe ich habs auch verstanden, werds morgen nochmal revue passieren lassen, da mir dann grad auch die Energie fehlt nach einem weiteren Lernmarathon und ich mir über garnichtsmehr sicher sein kann Augenzwinkern

Ich finds aber super nett das du mir das alles nochmal ausgeführt hast!

Neue Frage »

Antworten »

Quersumme bei n<100000

Verwandte Themen