Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Binomialkoeffizienten » Binomialkoeffizienten
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J Binomialkoeffizienten
Nofi
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 15.01.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-01-15


Kann mir jemand einen Tipp geben, wie man die folgende Identität beweist?
Ich versuche es schon einige Zeit und komme nicht zu Potte!

fed-Code einblenden

Mit Dank im Voraus

Nofi





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5461
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nofi
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 15.01.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2587
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6673
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2587
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5461
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nofi
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 15.01.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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


fed-Code einblenden

bewiesen  haben, habt Ihr die schon mal irgendwo gesehen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5461
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2021-01-17


Könntest du vielleocht trotzdem sagen, was du mit "dem üblichen Instrumentarium" meinst?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3785
Herkunft: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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...)




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nofi
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 15.01.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2021-01-17


Zuerst habe ich

fed-Code einblenden
gerechnet und dann die beiden Ausdrücke voneinander abgezogen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nofi
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 15.01.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2021-01-17


Induktion habe ich auch versucht, bin aber kläglich im Formelsalat stecken geblieben.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag 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 [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
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]