Teilbar durch Fakultät < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hi zusammen,
wie kann man beweisen, dass
n * (n-1) * (n-2) * ... * (n-K)
immer durch
(K+1) * K * (K-1) * (K-2) * ... * 1
teilbar ist?
|
|
| |
|
Hiho,
> wie kann man beweisen, dass
>
> n * (n-1) * (n-2) * ... * (n-K)
>
> immer durch
>
> (K+1) * K * (K-1) * (K-2) * ... * 1
durch einfaches abzählen.
$n * (n-1) * (n-2) * ... * (n-K)$ sind (k+1) aufeinanderfolgende natürliche Zahlen.
Daher kannst du die Zahlen so abzählen, dass eine von Ihnen durch 1 teilbar ist, eine andere durch 2, eine andere durch 3, etc… eine andere durch $(k+1)$. Damit ist das Produkt teilbar durch das Produkt der Faktoren.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:21 So 13.09.2020 | | Autor: | tobit09 |
Hallo Gono!
Leider kann ich deiner Idee keinen Beweis entnehmen.
> Daher kannst du die Zahlen so abzählen, dass eine von
> Ihnen durch 1 teilbar ist, eine andere durch 2, eine andere
> durch 3, etc… eine andere durch [mm](k+1)[/mm].
So wie ich deine Aussage interpretiere, ist sie nicht nur unbewiesen, sondern sogar auch falsch: Betrachte z.B. $n=7$ und $K=2$.
Vielleicht verstehe ich aber auch die gemeinte Aussage falsch.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:43 So 13.09.2020 | | Autor: | tobit09 |
Hallo MatheStein!
Der einzige mir bekannte Beweis funktioniert folgendermaßen:
Bezeichne für [mm] $n,K\in\IN_0$ [/mm] den Quotienten mit Dividend [mm] $n*(n-1)*\ldots(n-K)$ [/mm] und Divisor $(K+1)!$ mit [mm] $Q_{n,K}$. [/mm] Es genügt zu zeigen, dass [mm] $Q_{n,K}$ [/mm] eine natürliche Zahl ist.
1. Zeige durch Termumformungen, dass für alle [mm] $n\in\IN_0$ [/mm] gilt: [mm] $Q_{n+1,K}=Q_{n,K}+Q_{n,K-1}$ [/mm] für [mm] $K\ge [/mm] 1$ und [mm] $Q_{n+1,K}=n+1$ [/mm] für $K=0$.
2. Verwende 1., um per Induktion nach $n$ folgende Aussage zu zeigen:
Für alle [mm] $n\in\IN_0$ [/mm] gilt: Für alle [mm] $K\in\IN_0$ [/mm] ist [mm] $Q_{n,K}$ [/mm] eine natürliche Zahl.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:52 Mo 14.09.2020 | | Autor: | tobit09 |
Durch ![[]](/images/popup.gif) diesen Thread bin ich auf die kombinatorische Argumentationsmöglichkeit aufmerksam geworden.
Seien [mm] $n,k\in\IN_0$ [/mm] mit [mm] $k\le [/mm] n$.
Wir betrachten die Menge [mm] $M:=\{(x_1,\ldots,x_k)\;|\;x_1,\ldots,x_k\in\{1,\ldots,n\},\forall i\not=j\colon x_i\not=x_j\}$.
[/mm]
Per Induktion nach $k$ zeigt man, dass [mm] $|M|=\produkt_{i=0}^{k-1}(n-i)$ [/mm] gilt.
Wir definieren eine Äquivalenzrelation [mm] $\sim$ [/mm] auf $M$ durch [mm] $(x_1,\ldots,x_k)\sim(y_1,\ldots,y_k):\iff\{x_1,\ldots,x_k\}=\{y_1,\ldots,y_k\}$.
[/mm]
Sei [mm] $M/\sim$ [/mm] die Menge der Äquivalenzklassen (deren Vereinigung bekanntlich $M$ ist).
Erneut per Induktion nach $k$ zeigt man, dass $|a|=k!$ für alle [mm] $a\in M/\sim$.
[/mm]
Somit gilt [mm] $\produkt_{i=0}^{k-1}(n-i)=|M|=\sum_{a\in M/\sim}|a|=\sum_{a\in M/\sim}k!=|M/\sim|*k!$, [/mm] insbesondere teilt $k!$ tatsächlich [mm] $\produkt_{i=0}^{k-1}(n-i)$.
[/mm]
|
|
|
| |
|
Hi Tobi,
vielen Dank für die Hilfen. Kurze Frage -- würde hier nicht gelten, dass $ [mm] M/\sim [/mm] $ aus nur einer Äquivalenzklasse besteht, die alle Elemente aus $M$ enthält?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:51 Mo 14.09.2020 | | Autor: | fred97 |
> Hi Tobi,
>
> vielen Dank für die Hilfen. Kurze Frage -- würde hier
> nicht gelten, dass [mm]M/\sim[/mm] aus nur einer Äquivalenzklasse
> besteht, die alle Elemente aus [mm]M[/mm] enthält?
Nein. Schau Dir mal den Fall $k=2, n=3$ an. Die Äquivalenzklasse von $(1,2)$ ist
[mm] $\{(1,2),(2,1)\}$
[/mm]
und die Äquivalenzklasse von $(1,3)$ ist
[mm] $\{(1,3),(3,1)\}$.
[/mm]
|
|
|
| |
|
Kombinatorisch lässt sich das Problem mit Hilfe eines Paradebeispiels darstellen:
An einem Pferderennen nehmen n Pferde teil, die alle zu verschiedenen Zeiten durchs Ziel gehen. Sie sind von 1 bis n nummeriert. Jemand erstellt nun eine Liste1, in der alle möglichen Reihenfolgen der Zieleinläufe aufgeschrieben werden. Das gibt n! Ketten der Länge n.
Nun erfährt unser Freund, dass die ersten k Pferde einen Preis gewonnen haben (alle den selben, unabhängig von der Reihenfolge). Er beschließt, nun wieder eine Liste2 anzufertigen, in der jeweils alle Möglichkeiten stehen, wer die ersten k Pferde gewesen sein könnten.
Er geht so vor: Er wählt einen Eintrag aus Liste 1. Hinter den ersten k Pferden zieht er einen Strich.
+----------------+-----------------------------+
| k | n-k |
+----------------+-----------------------------+
Dann schreibt er die ersten k Pferde für die Liste2 auf.
Damit er nun nicht nochmals auf die ersten k Pferde stößt, streicht er alle Einträge aus der Liste1, bei denen die selben ersten k Pferde ebenfalls (in beliebiger Reihenfolge, aber wieder als erste) vorkommen. Wie viele sind das?
Die Anzahl der Möglichkeiten, die ersten k Pferde vorne beizubehalten und nur untereinander zu tauschen, beträgt k!. Zu jeder dieser Möglichkeiten kann man aber auch noch die n-k letzten Pferde untereinander tauschen. Das sind (n-k)! Möglichkeiten. Also tauchen die selben k Siegerpferde in k!(n-k)! Einträgen aus Liste1 auf. Streicht man sie nun alle aus der Liste und wählt dann einen neuen Eintrag aus, hat der wieder k!(n-k)! "Freunde" in Liste1 usw.. Zum Schluss enthält Liste2 x Elemente, [mm] x\in \IN.
[/mm]
Fazit: Hat man alle x Einträge in Liste2 gemacht (mathematisch: jeder Eintrag in Liste2 ist Repräsentant einer Äquivalenzklasse aus Liste1), so hat man in Liste1 genau x*k!(n-k)! Elemente gestrichen und Liste1 ist nun leer. Somit ist
x*k!(n-k)!=n! und damit
[mm] x=\bruch{n!}{k!(n-k)!}=\bruch{n(n-1)(n-2)...(n-k+1)}{(n-k)!}*\bruch{k!}{k!}=\bruch{n(n-1)(n-2)...(n-k+1)}{(n-k)!}
[/mm]
oder [mm] \bruch{n(n-1)(n-2)...(n-k+1)}{(n-k)!}=x\in \IN.
[/mm]
|
|
|
| |
|
Es gibt einen schönen Beweis, der nicht auf vollst. Ind. beruht und mit dem man sogar die Primteiler des Ergebnisses bestimmen kann. Ich schreibe hier sehr ausführlich, lass dich dadurch nicht abschrecken, die einzelnen Schritte sind leicht verständlich.
1. Schritt: es ist [mm] \bruch{n(n-1)(n-2)...(n-k)}{(k+1)k(k-1)...2*1}=\bruch{n(n-1)(n-2)...(n-k)}{(k+1)k(k-1)...2*1}*\bruch{(n-k-1)(n-k-2)...2*1}{(n-k-1)(n-k-2)...2*1}=\bruch{n!}{(k+1)!(n-k-1)!}
[/mm]
2. Schritt: Zur Vereinfachung der Schreibweise setze ich r=k+1 und erhalte
[mm] \bruch{n!}{r!(n-r)!}
[/mm]
Behauptung: für 0 [mm] \le [/mm] r [mm] \le [/mm] n gibt das eine ganze Zahl.
Hinweis: Für kleine Zahlen n=1,2,3,4 oder k=0,1,2 lässt sich das sofort hinschreiben und wegkürzen. Falls für den Beweis diese Fälle ausgeklammert und gesondert betrachtet werden müssten, lasse ich aber diese Einschränkungen unerwähnt.
Beweisidee:
Ich zeige, dass jeder Primfaktor p, der im Nenner vorkommt, im Zähler mindestens genau so oft vorkommt und daher im Nenner weggekürzt werden kann. Kürzt man im Nenner alle Primfaktoren weg, wird er zu 1, und wir haben eine ganze Zahl, die aus den nicht weggekürzten Primfaktoren besteht.
Warum Primfaktoren? Die Zahl 12 ist ein Faktor von 24, die Zahl 8 ebenfalls, und 24 lässt sich durch beide Zahlen teilen. Aber [mm] \bruch{24}{8*12} [/mm] ist keine ganze Zahl, weil beim Kürzen mit 8 bereits Primfaktoren aus der 12 weggekürzt werden und das Kürzen mit 12 dann nicht mehr geht. Da die Primfaktorzerlegung eindeutig ist, wird es damit keine Probleme geben.
Wie oft kommt die Primzahl p als Faktor in n! vor?
Beispiel: Wie oft kommt 5 in 131! vor?
Gehen wir die Faktoren 1, 2, 3,...,131 schrittweise durch, so erkennen wir, dass 5 zum ersten Mal bei 5, dann bei 10, 15, 20,...,130 vorkommt, nämlich bei jeder 5. Zahl. Das wäre 26 mal: 131:5=26,2. Wir runden das Ergebnis auf die nächste ganze Zahl ab, falls es nicht schon ganzzahlig ist.
Hierfür gibt es ein Symbol, eine eckige Klammer, bei der nur unten die Haken sind:
[mm] \lfloor [/mm] x [mm] \rfloor [/mm] = x, falls x eine ganze Zahl ist, sonst die von x auf die nächste kleinere ganze Zahl abgerundete Zahl, also
[mm] \lfloor [/mm] 3 [mm] \rfloor [/mm] =3
[mm] \lfloor [/mm] 3,78 [mm] \rfloor [/mm] =3
Damit können wir jetzt [mm] schreiben:\lfloor \bruch{131}{5} \rfloor =\lfloor [/mm] 26,2 [mm] \rfloor [/mm] =26.
Manche Zahlen enthalten aber den Primfaktor 5 mehrfach. Die erste ist [mm] 25=5*5=5^2, [/mm] die nächste 50, dann 75, 100 und 125, das sind [mm] \lfloor \bruch{131}{25} \rfloor =\lfloor [/mm] 5,24 [mm] \rfloor [/mm] =5.Da wir die jeweils erste 5 schon bei der ersten Zählung dabei hatten, kommen jetzt nur noch 5 weitere 5-en hinzu.
Die erste Zahl, die sogar 3 Fünfen als Primfaktor hat, ist 125. Zwei Fünfen sind schon abgezählt, also kommt noch eine hinzu, und 131! hat genau 26+5+1=32 mal den Faktor 5.
Wir erhalten die letzte 1 durch [mm] \lfloor \bruch{131}{125} \rfloor. [/mm] Führen wir dies weiter fort, so käme [mm] \lfloor \bruch{131}{625} \rfloor=0 [/mm] hinzu usw.
Allgemein gilt:
n! hat den Primfaktor p genau [mm] \lfloor \bruch{n}{p} \rfloor+\lfloor \bruch{n}{p^2} \rfloor+\lfloor \bruch{n}{p^3} \rfloor+\lfloor \bruch{n}{p^4} \rfloor... [/mm] mal, wobei wir beliebig fortfahren können, weil die Summanden für [mm] p^i [/mm] >n alle 0 werden. Das schreiben wir mit dem Summenzeichen so:
[mm] \summe_{i=1}\lfloor \bruch{n}{p^i} \rfloor
[/mm]
Nun ist klar, dass das selbe p in r! genau [mm] \summe_{i=1}\lfloor \bruch{r}{p^i} \rfloor [/mm] oft vorkommt und in (n-r)! dann [mm] \summe_{i=1}\lfloor \bruch{n-r}{p^i} \rfloor [/mm] mal.
Wenn wir also von der ersten Summe die beiden anderen abziehen, gibt das Ergebnis an, wie oft der Primfaktor p nach dem völligen Kürzen mit p im Zähler übrig bleibt. Ist keiner der Werte negativ, bleibt im Nenner auch kein p übrig.
[mm] \summe_{i=1}\lfloor \bruch{n}{p^i} \rfloor-\summe_{i=1}\lfloor \bruch{r}{p^i} \rfloor-\summe_{i=1}\lfloor \bruch{n-r}{p^i} \rfloor =\summe_{i=1}(\lfloor \bruch{n}{p^i}\rfloor-\lfloor\bruch{r}{p^i}\rfloor-\lfloor\bruch{n-r}{p^i} \rfloor)
[/mm]
Ich behaupte nun, dass keiner dieser Klammern in der rechten Summe negativ ist, und damit ist es auch nicht die Summe. Da das dann für alle Primzahlen p gilt, ist jedes p im Zähler mindestens genau so oft wie im Nenner vertreten.
Wir schätzen nun den Summanden [mm] \lfloor \bruch{n}{p^i}\rfloor-\lfloor\bruch{r}{p^i}\rfloor-\lfloor\bruch{n-r}{p^i} \rfloor [/mm] ab
Wir dividieren die Zahlen n und r durch [mm] p^i [/mm] mit Rest und erhalten dadurch:
[mm] n=a*p^i+u, [/mm] wobei u der Divisionsrest ist, also [mm] 0\le u
[mm] r=b*p^i+v, [/mm] wobei v der Divisionsrest ist, also [mm] 0\le v
Daraus ergibt sich nun
[mm] n-r=(a-b)*p^i+u-v.
[/mm]
Damit ist [mm] \lfloor \bruch{n}{p^i}\rfloor-\lfloor\bruch{r}{p^i}\rfloor-\lfloor\bruch{n-r}{p^i} \rfloor =\lfloor \bruch{a*p^i+u}{p^i}\rfloor-\lfloor\bruch{b*p^i+v}{p^i}\rfloor-\lfloor\bruch{(a-b)*p^i+u-v}{p^i} \rfloor =\lfloor a+\bruch{u}{p^i}\rfloor-\lfloor b+\bruch{v}{p^i}\rfloor-\lfloor a-b+\bruch{u-v}{p^i} \rfloor,
[/mm]
Wobei alle auftauchenden Brüche im letzten Teil betragsmäßig <1 sind, da [mm] 0\le [/mm] u,v [mm]
...= [mm] a-b-\lfloor a-b+\bruch{u-v}{p^i} \rfloor
[/mm]
Falls u-v positiv oder 0 ist, wird ggf. abgerundet auf a-b, das Gesamtergebnis ist a-b-(a-b)=0.
Falls u-v negativ ist, wird die letzte Klammer auf a-b-1 abgerundet. Das Gesamtergebnis ist dann a-b-(a-b-1)=1, es bleibt einmal der Faktor p im Zähler übrig.
Fazit: Jeder Primfaktor p kann nach dem Kürzen - wenn überhaupt - nur im Zähler übrig bleiben, also ist der ganze Bruch eine natürliche Zahl.
Zusatz: für jedes relevante i - also wenn [mm] p^i\le [/mm] n ist - kann p höchstens einmal im Ergebnis vorkommen.
In unserem Beispiel: [mm] 5^3<131, [/mm] aber [mm] 5^4>131, [/mm] deshalb kann für n=131 und beliebigem k im Ergebnis die 5 höchstens 3 mal als Primfaktor vorkommen.
So erhält man z.B. für n=131 und r=8 den Wert [mm] 1729815438000=2^4*3*5^3*13*31*43*127*131
[/mm]
Hier noch ein schönes Zahlenbeispiel.
Was kommt für n=20 und r=n-r=10 heraus?
Primfaktor 2 in 20!: 20/2=10, 20/4=5, 20/8=2, 20/16=1, zusammen 18 mal die 2 im Zähler.
Primfaktor 2 in 10!: 10/2=5, 10/4=2, 10/8=1, zusammen 8.
Dasselbe für das andere 10!, macht zusammen 16 mal die 2 im Nenner.
Damit hat der Bruch die Primpotenz [mm] 2^2.
[/mm]
Das selbe mit 3 (und 9) gibt für den Zähler 6+2=8 und für den Nenner zwei mal 3+1, also auch 8, somit kein Faktor 3
Mit 5: Zähler =4, Nenner=2+2, somit keine 5
Mit 7: Zähler=2, Nenner=2*1, keine 7
Mit 11: Zähler=1, Nenner0, somit 11
Dazu noch 13, 17 und 19.
Ergebnis: [mm] 2^2*11*13*17*19=184756.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:18 Mo 21.09.2020 | | Autor: | MatheStein |
Vielen Dank für die tolle Hilfe!
|
|
|
|
