Multinomialkoeffizient teilbar durch n

12.11.2015, 10:28

Matheneuling1991

Auf diesen Beitrag antworten »

Multinomialkoeffizient teilbar durch n

Ich muss für eine Aufgabe zeigen, dass folgendes gilt:

Seien n,p,q unterschiedliche Primzahlen und p teilt (q-1) (es kann sein, dass für diesen Teil nicht alle dieser Informationen benötigt werden);

Dann gilt:

$\begin{eqnarray*} \begin{pmatrix} n^{p-1} \\ n_1,..,n_{q-1} \end{pmatrix} \end{eqnarray*}$

ist durch n teilbar, sofern

$\begin{eqnarray*} \sum\limits_{i=1}^{q-1} n_i = n^{p-1} \end{eqnarray*}$ und kein $\begin{eqnarray*} n_1,..,n_{q-1} \end{eqnarray*}$ selbst $\begin{eqnarray*} n^{p-1} \end{eqnarray*}$ enspricht und alle ni nicht negative ganze Zahlen sind;

Siehe auch Die Definition des Multinominalkoeffizients bei wikipedia für das Multinominaltheorem;

https://de.wikipedia.org/wiki/Multinomialtheorem

Meine Gedanken:

Wenn ich einen Binominalkoeffizient

$\begin{eqnarray*} N=\begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

habe, ist es offensichtlich, dass die Aussage für k aus 1,...,n-1 gilt; Auch beim Multinominalkoeffizient wäre dies einfach für ein n zu zeigen;

Allerdings muss ich die Aussage irgendwie abwandeln, weil

$\begin{eqnarray*} n^{p-1} \end{eqnarray*}$ eben keine Primzahl mehr ist; Allerdings fehlt mir der Gedanke, wie;

Hat da jemand eine Idee?

EDIT: Mir fällt gerade auf, dass es vielleicht nicht in die Kombinatorik, sondern eher in die Zahlentheorie fällt; Falls dem so wäre bitte ich einen Moderator, das Thema einfach zu verschieben;

12.11.2015, 11:15

HAL 9000

Auf diesen Beitrag antworten »

Das $\begin{align*} p \mid (q-1) \end{align*}$ wird man hier nicht brauchen, und ebenfalls nicht, dass $\begin{align*} p,q \end{align*}$ überhaupt Primzahlen sind - die Aussage gilt auch so für alle $\begin{align*} p\geq 1,q\geq 3 \end{align*}$ . Allerdings sollte $\begin{align*} n \end{align*}$ schon noch Primzahl sein. Augenzwinkern

Augenzwinkern

Zeige die Aussage durch vollständige Induktion über $\begin{align*} q \end{align*}$ .

Den Induktionsanfang $\begin{align*} q=3 \end{align*}$ hast du schon selbst diskutiert: Das ist der Binomialkoeffizient $\begin{align*} \binom{n^{p-1}}{n_1,n_2} = \binom{n^{p-1}}{n_1} \end{align*}$ mit $\begin{align*} 0<n_1<n^{p-1} \end{align*}$ .

Im Induktionsschritt $\begin{align*} q\to q+1 \end{align*}$ kannst du für $\begin{align*} q\geq 3 \end{align*}$ dann nutzen

$\begin{align*} \binom{n^{p-1}}{n_1,\ldots,n_q} = \binom{n^{p-1}}{n_1,\ldots,n_{q-2},n_{q-1}+n_q}\cdot \binom{n_{q-1}+n_q}{n_q} \end{align*}$ .

Der zweite Faktor interessiert uns nur insoweit, dass $\begin{align*} \binom{n_{q-1}+n_q}{n_q} \end{align*}$ eine ganze Zahl ist, für den ersten Faktor nutzen wir die Induktionsvoraussetzung. Zu beachten ist, dass wir (durch eventuelles Umgruppieren) darauf achten müssen, dass $\begin{align*} n_{q-1}+n_q<n^{p-1} \end{align*}$ ist, weil ansonsten die Induktionsvoraussetzung nicht greift - aber das ist aufgrund der Symmetrie des Terms $\begin{align*} \binom{n^{p-1}}{n_1,\ldots,n_q} \end{align*}$ kein Problem.

12.11.2015, 12:03

Matheneuling1991

Auf diesen Beitrag antworten »

Du meinst beim Induktionsschritt sicher

q-1 nach q, richtig?

Ansonsten habe ich das kapiert und die Lösung ist wirklich fantastisch, vielen Dank!!! smile

smile

12.11.2015, 12:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Matheneuling1991
Du meinst beim Induktionsschritt sicher

q-1 nach q, richtig?

Nein, bezogen auf deine Behauptung für $\begin{align*} q \end{align*}$ , wo du ja $\begin{align*} \binom{n^{p-1}}{n_1,\ldots,n_{q-1}} \end{align*}$ geschrieben hast (was mich auch etwas gewundert hat) ist es tatsächlich $\begin{align*} q\to q+1 \end{align*}$ .

Wenn deine Behauptung für $\begin{align*} \binom{n^{p-1}}{n_1,\ldots,n_q} \end{align*}$ formuliert gewesen wäre, dann hättest du Recht. Dann wäre der Induktionsanfang auch nicht q=3, sondern q=2 gewesen usw.

12.11.2015, 16:48

Matheneuling1991

Auf diesen Beitrag antworten »

Stimmt, mein Fehler...

Vielen Dank für deine Hilfe! smile

smile

12.11.2015, 19:25

Matheneuling1991

Auf diesen Beitrag antworten »

Okay, Schande über mich, aber für q=3; Wie beweise ich es dort?
Kannst du mir eine (einfache) Möglichkeit zeigen, warum der Term durch n teilbar ist?

Anzeige

12.11.2015, 19:50

HAL 9000

Auf diesen Beitrag antworten »

Tja, so ganz einfach ist das nicht, wenn man es ordentlich machen will. Eine mögliche Variante:

Es sei $\begin{align*} g=\operatorname{ggT}\left(n^p,n_1\right) \end{align*}$ , und da $\begin{align*} n \end{align*}$ prim ist, ist auch $\begin{align*} g \end{align*}$ eine Potenz von $\begin{align*} n \end{align*}$ , sagen wir $\begin{align*} g=n^r \end{align*}$ . Aufgrund der Voraussetzung ist $\begin{align*} 0\leq r<p \end{align*}$ .

Nach dem Lemma von Bézout gibt es nun ganze Zahlen $\begin{align*} a,b \end{align*}$ mit $\begin{align*} an^p + bn_1 = g \end{align*}$ , und mit diesen Werten kann man nun Gleichung

$\begin{align*} \binom{n^p}{n_1} = n^{p-r} \cdot \left( (a+b)\cdot \binom{n^p-1}{n_1-1} + a\cdot \binom{n^p-1}{n_1} \right) \end{align*}$

zeigen, womit die Teilbarkeit durch $\begin{align*} n^{p-r} \end{align*}$ nachgewiesen ist.

EDIT: $\begin{align*} g=n^r \end{align*}$ korrigiert.

12.11.2015, 20:57

Matheneuling1991

Auf diesen Beitrag antworten »

Du meinst du g=n^r, oder? Wie kommst du auf die letzte Umformung des Binomialkoeffizienten?

12.11.2015, 20:58

HAL 9000

Auf diesen Beitrag antworten »

Wer länger hier im Forum ist weiß, dass ich diese unsäglichen "Wie kommst du drauf"-Fragen i.d.R. nicht beantworte. Man kann es beweisen, und ich kann auch noch Unterstützung beim Beweis geben - aber ich kann nicht darlegen, durch welche Inspirationen ich auf diese Idee gekommen bin. unglücklich

unglücklich

12.11.2015, 21:06

Matheneuling1991

Auf diesen Beitrag antworten »

Okay, dann helfe mir;

Erst einmal: Du meinst , dass der ggT g sich schreiben lässt als g=n^r, richtig? Weil die Primzahl n zu schreiben als n=p^r macht irgendwie nicht so viel Sinn;

Falls ja, gibst du mir einen Tipp, wie du auf die letzte Umformung gekommen bist? smile

smile

12.11.2015, 21:22

HAL 9000

Auf diesen Beitrag antworten »

Ja klar, $\begin{align*} g=n^r \end{align*}$ ist gemeint - ich korrigiere es oben. Ist eben irgendwie ungewohnt, n als Primzahl und p als Exponenten zu haben...

12.11.2015, 23:00

Matheneuling1991

Auf diesen Beitrag antworten »

Natürlich... Ist auch für mich ungewohnt, habe aber in dem Fall die Notation des Buches verwendet.. smile

smile

Kannst du mir noch einen Tipp geben, wie du auf die Umformung kommst?

Bis inklusive der Zeile, dass a,b exisitieren, sodass a*n^p+b*n1=g bin ich mitgekommen, dann leider nicht mehr;

13.11.2015, 08:18

HAL 9000

Auf diesen Beitrag antworten »

Ok, ausnahmsweise, wie "komme ich drauf" - ich hab mich dran erinnert wie man nachweist, dass $\begin{align*} \binom{2n}{n} \end{align*}$ immer durch $\begin{align*} (n+1) \end{align*}$ teilbar ist: Es ist

$\begin{align*} n\cdot \binom{2n}{n} = \frac{(2n)!}{n!(n-1)!} = (n+1)\cdot \binom{2n}{n+1} \end{align*}$

Daraus folgt $\begin{align*} (n+1) \left( \binom{2n}{n} - \binom{2n}{n+1} \right) = \binom{2n}{n} \end{align*}$ , was die Aussage beweist.

---------------------------

Diese "Technik" so ähnlich auf unser Problem übertragen: Es ist

$\begin{align*} \left( n^p -n_1\right)\cdot \binom{n^p}{n_1} = \frac{\left( n^p \right)!}{n_1!\left( n^p -n_1-1\right)!} = n^p\cdot \binom{n^p-1}{n_1} \end{align*}$ .

und ganz ähnlich

$\begin{align*} n_1\cdot \binom{n^p}{n_1} = \frac{\left( n^p \right)!}{(n_1-1)!\left( n^p -n_1\right)!} = n^p\cdot \binom{n^p-1}{n_1-1} \end{align*}$

D.h., sowohl das $\begin{align*} \left( n^p -n_1\right) \end{align*}$ -fache als auch das $\begin{align*} n_1 \end{align*}$ -fache unseres Zieles ist durch $\begin{align*} n^p \end{align*}$ teilbar. Damit ist auch für jede Linearkombination $\begin{align*} k=a\left( n^p -n_1\right) + cn_1 \end{align*}$ mit ganzen Zahlen $\begin{align*} a,c \end{align*}$ das $\begin{align*} k \end{align*}$ -fache unseres Binomialkoeffizienten durch $\begin{align*} n^p \end{align*}$ teilbar, über $\begin{align*} k=an^p + (c-a)n_1 = an^p + bn_1 \end{align*}$ mit $\begin{align*} b:=c-a \end{align*}$ kann man das noch etwar umparametrieren. Zu all den Zahlen $\begin{align*} k \end{align*}$ , die so darstellbar sind, gehört insbesondere der ggT von $\begin{align*} n^p \end{align*}$ und $\begin{align*} n_1 \end{align*}$ , dort kommt dann Binet ins Spiel...

------------------------------------

Prinzipiell kann man die obigen Überlegungen zu folgender allgemeineren Aussage zusammenfassen:

Zitat:

Für $\begin{align*} 0\leq k\leq n \end{align*}$ ist der Binomialkoeffizient $\begin{align*} \binom{n}{k} \end{align*}$ durch $\begin{align*} \frac{n}{\operatorname{ggT}(n,k)} \end{align*}$ teilbar.

(Die Fälle k=0 und k=n sind zwar in obigem Beweis nicht enthalten, aber ohnehin trivial.) Kann man vielleicht auch anderweitig mal gebrauchen. Augenzwinkern

Augenzwinkern

13.11.2015, 12:39

Matheneuling1991

Auf diesen Beitrag antworten »

Vielen Dank für die ausführliche Erklärung, da wäre ich sonst niemals drauf gekommen... Du bist toll!! smile

smile

Darf ich doch noch eines fragen: Reicht diese Umformung nicht bereits aus?

$\begin{align*} n_1\cdot \binom{n^p}{n_1} = \frac{\left( n^p \right)!}{(n_1-1)!\left( n^p -n_1\right)!} = n^p\cdot \binom{n^p-1}{n_1-1} \end{align*}$

Die Primfaktorzerlegung von n1 kann maximal (p-1) x den Faktor n enthalten; wenn n^p den Term aber teilt, muss n den Binomailkoeffizieten teilen, oder nicht?

13.11.2015, 18:08

HAL 9000

Auf diesen Beitrag antworten »

Ja, geht anscheinend auch. Manchmal denke ich halt überkompliziert. Big Laugh

Big Laugh

13.11.2015, 22:15

Matheneuling1991

Auf diesen Beitrag antworten »

Darüber bin ich sehr froh... smile

smile

Sonst hätte ich nie den Zusammenhang zwschen dem GGT und dem Binomialkoeffizient kennengelernt.. smile

smile

Danke für deine Hilfe.. ! smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »