| |
| Autor |
  Binomialkoeffizienten |
|
Nofi
Junior 
Dabei seit: 15.01.2021
Mitteilungen: 5
 |
 Notiz  Profil
 Quote
 Link |
Triceratops
Aktiv 
Dabei seit: 28.04.2016
Mitteilungen: 5453
Herkunft: Berlin
 |      Beitrag No.1, eingetragen 2021-01-16
|
So müsste es gehen: Sei $X = \{A_1,\dotsc,A_n,B_1,\dotsc,B_n\}$ eine Menge mit $2n$ Elementen. Die rechte Seite zählt $n$-elementige Teilmengen $T \subseteq X$ zusammen mit einem Element $x \in T$. Es sei o.B.d.A. $x \in \{B_1,\dotsc,B_n\}$ (der andere Fall geht analog, daher der Faktor $2$ auf der linken Seite!), und es sei $k$ die Kardinalität von $T \cap \{A_1,\dotsc,A_n\}$. Reicht das als Tipp?
|
Notiz Profil
Quote
Link |
Nofi
Junior
Dabei seit: 15.01.2021
Mitteilungen: 5
|  Beitrag No.2, vom Themenstarter, eingetragen 2021-01-16
|
Ja, das reicht als Tipp. Auf den Trick mit der doppelten Abzählung bin ich nicht gekommen.
Dieser Beweis ist an Eleganz nicht zu toppen. Kompliment! Und vielen Dank für die schnelle Hilfe.
|
Notiz Profil
Quote
Link |
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2585
| Beitrag No.3, eingetragen 2021-01-16
|
\(\begingroup\)\(\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}}\)
2021-01-16 03:50 - Triceratops in Beitrag No. 1 schreibt:
So müsste es gehen: Sei $X = \{A_1,\dotsc,A_n,B_1,\dotsc,B_n\}$ eine Menge mit $2n$ Elementen. Die rechte Seite zählt $n$-elementige Teilmengen $T \subseteq X$ zusammen mit einem Element $x \in T$. Es sei o.B.d.A. $x \in \{B_1,\dotsc,B_n\}$ (der andere Fall geht analog, daher der Faktor $2$ auf der linken Seite!), und es sei $k$ die Kardinalität von $T \cap \{A_1,\dotsc,A_n\}$. Reicht das als Tipp? Ich komme mit diesem Tipp auf
$$ n\binom{2n}n = 2\sum_{k=0}^{n-1}(n-k)\binom nk \binom n{n-k} = 2\sum_{k=0}^{n-1}(n-k)\binom nk^2.$$
Wie kommt man von hier auf den gewünschten Ausdruck?\(\endgroup\)
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 6662
Herkunft: Milchstraße
 | Beitrag No.4, eingetragen 2021-01-16
|
\(\begingroup\)\(\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{\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}}\)
2021-01-16 12:00 - Nuramon in Beitrag No. 3 schreibt:
Ich komme mit diesem Tipp auf
$$ n\binom{2n}n = 2\sum_{k=0}^{n-1}(n-k)\binom nk \binom n{n-k} = 2\sum_{k=0}^{n-1}(n-k)\binom nk^2.$$ 👍
Anscheinend stimmen aber beide Formeln - und es ist nicht \(\binom nk^2=\binom{2n}k\).\(\endgroup\)
|
Notiz Profil
Quote
Link |
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2585
| Beitrag No.5, eingetragen 2021-01-16
|
\(\begingroup\)\(\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}}\)
Mit ein bisschen Umformen habe ich folgende Lösung gefunden:
Unter Ausnutzung der Symmetrie des Binomialkoeffizienten, lässt sich die zu zeigende Gleichung äquivalent umformen zu:
$$\sum_{k=0}^{2n} n \binom{2n}k = 2 \sum_{k=0}^{n} k \binom{2n}k$$
was wiederum zu
$$2n\cdot 2^{2n-1}= 2\sum_{k=1}^{n} k \binom{2n}k$$
äquivalent ist.
Auf der linken Seite steht jetzt die Anzahl aller Tupel $(x,T)$ wobei $x\in\{1,\ldots, 2n\}$ ein ausgewähltes Element und $T\subseteq \{1,\ldots, 2n\}\setminus\{x\}$ eine Teilmenge ist.
Die rechte Seite zählt diese Tupel indem zuerst eine $k$-elementige Teilmenge $T'\subseteq \{1,\ldots, 2n\}$ ausgewählt wird, aus dieser dann ein Element $x\in T'$ und schließlich entweder $T:= T'\setminus \{x\}$ oder $T:= \{1,\ldots, 2n\}\setminus T'$ gesetzt wird.\(\endgroup\)
|
Notiz Profil
Quote
Link |
Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 5453
Herkunft: Berlin
| Beitrag No.6, eingetragen 2021-01-16
|
Vielleicht funktioniert mein Ansatz wirklich nicht mit der genannten Formel. Meine grobe Idee war, dass ich bei $\binom{2n}{k}$, also den $k$-elementigen Teilmengen von $\{A_1,\dotsc,A_n,B_1,\dotsc,B_n\}$, jedes ausgewählte $B_i$ durch das $A_i$ ersetze; aber das geht natürlich nicht.
@Nofi: Deine Antwort klingt so, als ob du den Ansatz zu Ende bringen konntest. Wenn ja, wie?
|
Notiz Profil
Quote
Link |
Nofi
Junior 
Dabei seit: 15.01.2021
Mitteilungen: 5
| Beitrag No.7, vom Themenstarter, eingetragen 2021-01-17
|
@triceratops
Ich fand den Tipp spontan so überzeugend, dass ich mich gleich mal dafür bedankthabe, ohne ihn genauer zu betrachten. Nachdem dann @Nuramon seine Formel mitgeteilt hat, habe ich mal nachgerechnet und muss ihm recht geben. Meine Formel habe ich inzwischen ganz normal „zu Fuß“ bewiesen, mit dem üblichen Instrumentarium. Lohnt sich nicht,das hier auszubreiten.
Bemerkenswert ist jedoch, dass wir jetzt zusammen die äußerst seltsame Formel
  
sum((n-k)(n;k)^2,k=0,n-1)=sum((n-k)(2n;k),k=0,n-1)
bewiesen haben, habt Ihr die schon mal irgendwo gesehen?
|
Notiz Profil
Quote
Link |
Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 5453
Herkunft: Berlin
| Beitrag No.8, eingetragen 2021-01-17
|
Könntest du vielleocht trotzdem sagen, was du mit "dem üblichen Instrumentarium" meinst?
|
Notiz Profil
Quote
Link |
StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3779
Herkunft: Raun
| Beitrag No.9, eingetragen 2021-01-17
|
Zum üblichen Instrumentarium zähle ich die Induktion, zum Beispiel von n-1 auf n. Weil da der Weg von Induktionsannahme zur Induktionsbehauptung nicht zu sehen ist, versuche das rückwärts, mit \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\) in der Induktionsbehauptung
\(\binom{2n}{k}=\binom{2n-1}{k-1}+\binom{2n-1}{k} = \binom{2n-2}{k-2}+ \binom{2n-2}{k-1}+ \binom{2n-2}{k-1}+ \binom{2n-1}{k}\)
ersetzen und gleiche Binomialkoeffizienten zusammenfassen. Dann sollte mehrfach (viermal) die Induktionsannahme erscheinen (bin noch nicht ganz durch mit rechnen...)
|
Notiz Profil
Quote
Link |
Nofi
Junior
Dabei seit: 15.01.2021
Mitteilungen: 5
| Beitrag No.10, vom Themenstarter, eingetragen 2021-01-17
|
Notiz Profil
Quote
Link |
Nofi
Junior
Dabei seit: 15.01.2021
Mitteilungen: 5
| Beitrag No.11, vom Themenstarter, eingetragen 2021-01-17
|
Induktion habe ich auch versucht, bin aber kläglich im Formelsalat stecken geblieben.
|
Notiz Profil
Quote
Link |
Nofi hat die Antworten auf ihre/seine Frage gesehen.
Nofi hat selbst das Ok-Häkchen gesetzt. | | Nofi wird per Mail über neue Antworten informiert. |  [Neues Thema]  [Druckversion] |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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?
