| |
| Autor |
  Alle Binomialkoeffizienten sind ungerade |
|
Wally
Senior 
Dabei seit: 02.11.2004
Mitteilungen: 9721
Wohnort: Dortmund, Old Europe
 |  Themenstart: 2022-02-02
|
\(\begingroup\)\(\newcommand{\D}{\displaystyle}\)
Alle Werte von \(\displaystyle {n\choose k}\) sind ungerade für n=1,3,7,15,31. Für n=63 sind es jedenfalls die ersten 8.
Gibt es einen "schönen" Beweis, dass genau für \( n=2^m-1\) alle \(\displaystyle {n\choose k}\) ungerade ist? Und stimmt das überhaupt?
Viele Grüße
Wally \(\endgroup\)
|
 Profil
|
Diophant
Senior 
Dabei seit: 18.01.2019
Mitteilungen: 10673
Wohnort: Rosenfeld, BW
 |  Beitrag No.1, eingetragen 2022-02-02
|
Hallo Wally,
schau mal hier.
(Aus der Schatztruhe des MP).
Gruß, Diophant
|
Profil
|
Kuestenkind
Senior
Dabei seit: 12.04.2016
Mitteilungen: 2566
 | Beitrag No.2, eingetragen 2022-02-02
|
Huhu Wally,
es gibt aktuell gerade eine nette Vorlesung von Borcherds:
https://www.youtube.com/watch?v=KIvuGT5V1Fg&list=PL8yHsr3EFj53L8sMbzIhhXSAOpuZ1Fov8&index=8
Gruß,
Küstenkind
[Die Antwort wurde vor Beitrag No.1 begonnen.]
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.3, eingetragen 2022-02-02
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Hallo,
in Diophants Link wird erstmal nur eine Richtung bewiesen, aber man kann die Überlegung verallgemeinern:
Sei $n=b_0+2b_1+ 2^2b_2+\ldots+ 2^mb_m$ mit $b_0,b_1,\ldots \in \{0,1\}$ die Binärentwicklung von $n\in \IN$.
Dann gilt in $\IF_2[x]$ die Identität:
$$ \begin{align*}
(1+x)^n &= (1+x)^{b_0} (1+x^2)^{b_1}\cdots (1+x^{2^m})^{b_m}\\
&= c_0+c_1x+c_2x^2+\ldots,
\end{align*}$$
wobei $c_k\in\{0,1\}$ und $c_k=1$, genau dann, wenn die Binärdarstellung von $k$ höchstens an den Stellen Einsen enthält, wo auch die Binärdarstellung von $n$ Einsen enthält.
Andererseits ist offenbar auch $c_k\equiv \binom nk \pmod 2$.
Für $n=2^a-1$ kommen in der Binärdarstellung von $n$ nur Einsen vor, also gilt insbesondere $c_k=1$ für $0\leq k\leq n$.
Wenn $n$ nicht von der Form $2^a-1$ ist, dann gibt es ein $i\(\endgroup\)
|
Profil
|
Wally
Senior
Dabei seit: 02.11.2004
Mitteilungen: 9721
Wohnort: Dortmund, Old Europe
| Beitrag No.4, vom Themenstarter, eingetragen 2022-02-02
|
Herzlichen Dank, ihr drei!
Ähnliche Überlegungen wie in Diophants Link hatte ich auch im Kopf, genauso wie Überlegungen ähnlich zu dem Video - ich war aber zu faul, das jeweils genauer auszuarbeiten.
Nuramon, auf deine Rechnung wäre ich nicht gekommen!
Viele Grüße
Wally
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.5, eingetragen 2022-02-02
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Die Überlegung aus No.3 funktioniert auch mit anderen Primzahlbasen als 2:
Sei $p$ prim und $n,k\in \IN$. Es seien $n=n_0+n_1p+ n_2p^2+\ldots$ und $k=k_0+k_1p+k_2p^2+\ldots$ die $p$-adischen Darstellungen von $n$ und $k$.
Dann gilt
$$ \binom nk \equiv \binom {n_0} {k_0}\binom {n_1} {k_1}\binom {n_2} {k_2}\cdots \pmod p.$$
Insbesondere ist $\binom nk$ genau dann durch $p$ teilbar, wenn es ein $i\in\IN$ gibt mit $n_i < k_i$.
\(\endgroup\)
|
Profil
|
Creasy
Senior 
Dabei seit: 22.02.2019
Mitteilungen: 584
Wohnort: Bonn
 | Beitrag No.6, eingetragen 2022-02-03
|
Hey,
Nervemind, führte zu nicht viel..
Viele Grüße
Creasy
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.7, eingetragen 2022-02-03
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Auf Wikipedia steht auch noch eine kombinatorische Herleitung der Formel aus No.5.
Interessant daran ist, dass man damit dann auch eine ähnliche, wenn auch kompliziertere Formel für den Rest von $\binom nk$ modulo $p^2$ herleiten kann:
Seien wieder $n=n_0+n_1p+\ldots$ und $k=k_0+k_1p+\ldots $ die $p$-adischen Darstellungen.
Wie bei Wikipedia sei $N$ eine Menge mit $n$ Elementen, die wir in $n_0+n_1+n_2+\ldots$ Zyklen partitionieren, und zwar jeweils in $n_i$ Zyklen der Länge $p^i$.
Indem wir auf jedem Zyklus der Länge $p^i$ die Gruppe $\IZ/p^i$ durch Rotation operieren lassen, erhalten wir insgesamt eine Operation von $G:= \bigoplus_{i\geq 0} (\IZ/p^i)^{n_i}$ auf $N$.
Damit operiert $G$ aber gleichzeitig auch auf der Menge der $k$-elementigen Teilmengen von $N$. Und da $|G|$ eine Potenz von $p$ ist, ist auch die Länge jeder Bahn dieser Wirkung eine Potenz von $p$.
Daher ist $\binom nk$ modulo $p^2$ gleich der Anzahl aller $k$-Teilmengen von $N$, die in einer Bahn der Länge $1$ oder der Länge $p$ sind.
Die Anzahl der Bahnen der Länge $1$ (also der Fixpunkte) ist $c(n,k):=\binom {n_0} {k_0}\binom{n_1}{k_1}\cdots$ (siehe Wikipedia).
Eine $k$-Teilmenge $T$ von $N$ erzeugt eine Bahn der Länge $p$ genau dann, wenn $T$ die Vereinigung von einigen ganzen Zyklen und einer nichtleeren echten Teilmenge eines Zyklus ist, die invariant unter $p$-facher Rotation ist.
(Beispiel: Für $n=7, k=3, p=3$ bestehe $N$ aus den Zyklen $\{1,2,3\}, \{4,5,6\}, \{7\}$. Dann hat die Bahn der Teilmenge $T:=\{1,3\}\cup \{7\}$ die Länge $3$: Eine Rotation liefert $\{2,1\} \cup\{7\}$, zwei Rotationen liefern $\{3,2\}\cup\{7\}$ und die dritte Rotation ergibt wieder $T$.)
Sei $Z=\{a_1,a_2,\ldots, a_{p^i}\}$ ein Zyklus der Länge $p^i$. Die Teilmengen $X$ von $Z$, die invariant unter $p$ Rotationen sind, sind eindeutig bestimmt durch die Menge $X \cap \{a_1,a_2,\ldots, a_p\}$, denn aufgrund der Invarianz ergibt sich $X= \{a_{i+pj}\mid 1\leq i \leq p,a_{i}\in X, 0\leq j < p^{i-1}\}$.
Für $1\leq l \leq p-1$ gibt es also genau $\binom pl$ nichtleere echte Teilmengen $X$ von $Z$, die invariant unter $p$ Rotationen sind und $|X \cap \{a_1,a_2,\ldots, a_p\}| = l$ erfüllen. Für ein solches $X$ gilt außerdem $|X|= lp^{i-1}$.
Damit können wir jetzt die Anzahl der Teilmengen von $N$ bestimmen, deren Bahnen die Länge $p$ haben:
Wir müssen einen Zyklus $Z$ mit $|Z|>1$ auswählen (wenn der Zyklus Länge $p^i$ haben soll, gibt es dafür $n_i$ Möglichkeiten), von diesem Zyklus müssen wir dann eine nichtleere echte Teilmenge $X$ wählen, die invariant unter $p$ Rotationen ist, und schließlich müssen wir noch eine Teilmenge von $N\setminus Z$ finden, die $k-|X|$ Elemente hat und invariant unter der Wirkung von $G$ ist.
Zusammenfassend erhalten wir:
$$\binom nk \equiv c(n,k) + \sum_{i\geq 1}n_i \sum_{l=1}^{p-1}\binom pl c(n-p^i, k- lp^{i-1}) \pmod{p^2}. $$
Beispiel:
Es ist $\binom{21}9 = 293930 \equiv 8 \pmod 9$.
Mit der Formel hätte man das so berechnen können:
$$\begin{align*}
\binom{21}9 &= \binom{210_3}{100_3} \\
&\equiv \binom 21 \binom 10\binom 00 &+ 2\cdot\left(\binom 31\cdot\binom 10\binom 12 \binom 00 + \binom 32 \cdot \binom 10\binom 11 \binom 00\right) \\ &&+ 1 \cdot \left(\binom 31 \cdot \binom 20\binom 02 \binom 02 +\binom 32\cdot \binom 20 \binom 02\binom 01\right)\\
&\equiv 8 \pmod 9
\end{align*}$$
Für die Reste modulo $p^k$ mit $k\geq 3$ geht der Ansatz auch, aber die Formeln werden immer komplizierter, da es z.B. schon für $k=3$ zwei Typen von Teilmengen von $N$ gibt, deren Bahn die Länge $p^2$ hat (entweder besteht die Teilmenge aus Fixpunkten und einem Teilzyklus, der nur unter $p^2$ Rotationen invariant ist oder sie besteht aus Fixpunkten und zwei Teilzyklen, die jeweils unter $p$ Rotationen invariant sind).
Auf Wikipedia sind auch noch andere Verallgemeinerungen verlinkt, die habe ich mir aber noch nicht genauer angesehen.
\(\endgroup\)
|
Profil
|
Wally hat die Antworten auf ihre/seine Frage gesehen.
Wally hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
