| |
| Autor |
 Unabhängigkeit bestimmen |
|
tripleggg
Ehemals Aktiv 
Dabei seit: 20.05.2020
Mitteilungen: 82
 |  Beitrag No.40, vom Themenstarter, eingetragen 2021-12-04
|
binomialkoeffzienten meinst du ? n über i ? why
|
 Profil
|
Nuramon
Senior 
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.41, eingetragen 2021-12-04
|
\(\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}\)
Beispiel für $n=5$ und $i=3$:
Wir wollen ein Element $\pi$ von $A_i$ konstruieren, so wie in No. 31 beschrieben.
Dazu wählen eine $i$-elementige Teilmenge von $\{1,2,3,4,5\}$, etwa $\{1,3,4\}$.
Das größte Element dieser Teilmenge ist $4$, also setzen wir $\pi(i)=4$.
$\pi(1),\pi(2)$ soll eine Permutation von $1,3$ sein, also z.B. $\pi(1)=3,\pi(2)=1$.
Übrig bleiben die nicht ausgewählten Elemente $2,5$, mit denen wir z.B. $\pi(4)=5, \pi(5)=2$ definieren können.
Insgesamt erhalten wir die Permutation $3,1,4,5,2$. Diese ist tatsächlich ein Element von $A_i$.\(\endgroup\)
|
Profil
|
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 8294
Wohnort: Milchstraße
 | Beitrag No.42, eingetragen 2021-12-04
|
@Nuramon:
Deine Herleitung der Formel in #31 finde ich finde ich schon sehr klasse! (Bin nicht drauf gekommen.) Noch überraschender finde ich außerdem, dass sich die Formel dann so sehr vereinfacht. Deshalb frage ich mich, ob es ein noch einfacheres Argument gibt, das diese Formel begründet, oder ob es schlicht "Zufall" ist, dass die Formel so simpel wird.
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.43, eingetragen 2021-12-04
|
@StrgAltEntf: Ich bin auch noch auf der Suche nach einem einfacheren Argument, insbesondere für Teil (b). Mit meinem derzeitigen Ansatz läuft es entweder auf ein Teleskopprodukt oder Induktion hinaus.
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8294
Wohnort: Milchstraße
| Beitrag No.44, eingetragen 2021-12-04
|
\quoteon(2021-12-04 22:35 - Nuramon in Beitrag No. 43)
@StrgAltEntf: Ich bin auch noch auf der Suche nach einem einfacheren Argument, insbesondere für Teil (b). Mit meinem derzeitigen Ansatz läuft es entweder auf ein Teleskopprodukt oder Induktion hinaus.
\quoteoff
Offen ist ja auch noch die Unabhängigkeit.
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.45, eingetragen 2021-12-04
|
Oh sorry, ich meinte die Unabhängigkeit, nicht Teil (b). ( Über (b) habe ich noch gar nicht nachgedacht.)
Edit: (b) ist wesentlich einfacher als (a).
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8294
Wohnort: Milchstraße
| Beitrag No.46, eingetragen 2021-12-04
|
@tripleggg:
Du siehst jetzt vielleicht, dass die Aufgabe, die dir hier gestellt wurde, wohl etwas anspruchsvoller ist. Mein Ansinnen in den zahlreichen Beiträgen war es, dir zu vermitteln, was überhaupt zu beweisen ist. Ich hoffe, das ist nun einigermaßen rüber gekommen.
|
Profil
|
tripleggg
Ehemals Aktiv 
Dabei seit: 20.05.2020
Mitteilungen: 82
| Beitrag No.47, vom Themenstarter, eingetragen 2021-12-05
|
ich habe dein bsp verstanden aber wir gehen wir oben weiter dann ?
ich weiß ja dass die Möglichkeiten davon einmal $(n-i)!(i-1)!$ , aber das problem entsteht bei dem problem, dass wir eine Einschränkung machen müssen, weil die zahlen die $1,...,i-1$ müssen ja kleiner als i sein wobei $i+1,...,n$ relativ egal ist.
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.48, eingetragen 2021-12-05
|
\(\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}\)
Wenn Du das Beispiel aus No.41 tatsächlich verstanden hast, dann solltest Du das ganze auch umgekehrt hinbekommen. Vielleicht wird es dann klarer.
Also, sei $n=6$ und $i=4$.
Welche $i$-elementige Teilmenge von $\{1,2,3,4,5,6\}$ muss man auswählen, um mit dem Verfahren aus No.31 die Permutation $5,1,3,6,2,4$ erhalten zu können?\(\endgroup\)
|
Profil
|
tripleggg
Ehemals Aktiv
Dabei seit: 20.05.2020
Mitteilungen: 82
| Beitrag No.49, vom Themenstarter, eingetragen 2021-12-05
|
Profil
|
tripleggg
Ehemals Aktiv
Dabei seit: 20.05.2020
Mitteilungen: 82
| Beitrag No.50, vom Themenstarter, eingetragen 2021-12-05
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.51, eingetragen 2021-12-05
|
\(\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}\)
Ja, das ist korrekt. Ehrlich gesagt verstehe ich nicht, woran Dein Verständnis zur Zeit scheitert. Das von Dir in No. 47 angesprochene Problem wird dadurch berücksichtigt, dass $\pi(i)$ als das Maximum der ausgewählten Teilmenge definiert wird.\(\endgroup\)
|
Profil
|
tripleggg
Ehemals Aktiv
Dabei seit: 20.05.2020
Mitteilungen: 82
|  Beitrag No.52, vom Themenstarter, eingetragen 2021-12-05
|
was jetzt das endergebnis ist, daran scheiterts ich kann schwer die einzelnen bestandteile schwer zusammensetzten, deswegen brauche ich die lösung letzter tag ist heute
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.53, eingetragen 2021-12-05
|
\(\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}\)
Im Verfahren aus No. 31 gibt es drei Stellen, an denem man etwas auswählen muss:
1. Man wählt eine Teilmenge $T$ von $N:=\{1,\ldots, n\}$ mit $|T|=i$.
2. Man wählt eine Permutation von $T\setminus \{\max (T)\}$.
3. Man wählt eine Permutation von $N\setminus T$.
Wie viele Möglichkeiten gibt es bei jeder dieser Wahlen? (Das hast Du eigentlich alles auch schon in diesem Thread beantwortet)
Wie viele Möglichkeiten gibt es also insgesamt?\(\endgroup\)
|
Profil
|
tripleggg
Ehemals Aktiv
Dabei seit: 20.05.2020
Mitteilungen: 82
| Beitrag No.54, vom Themenstarter, eingetragen 2021-12-05
|
zu 3. sage ich (n-i)!
zu 2. sage ich (n-1)!
zu 1 sage ich wenn wir i haben und einen N würde ich einfach den binomialkoeffzienten bestimmen
$\binom{n}{i}*(n-1)!(n-i)!$
ich weiß nicht was du genau bei der 2 meinst, wenn damit das hier gemeint ist (i-1)! dann würde sich das umändern auf $\binom{n}{i}*(i-1)!(n-i)!$
weil wir haben ja eine gewisse permuation von den elementen 1,..bis,i-1
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8294
Wohnort: Milchstraße
| Beitrag No.55, eingetragen 2021-12-05
|
Hallo,
die Unabhängigkeit lässt dich mit vollständiger Induktion unter Zuhilfenahme von Nuramons Trick wie folgt beweisen.
Um deutlich zu machen, dass wir mit Permutationen auf \(\{1,...,n\}\) hantieren, führen wir einen zusätzlichen oberen Index n ein.
Es sei \(J=\{j_1,...,j_k\}\subseteq\{1,...,n\}\) mit \(j_1<... 1. Wie viele Möglichkeiten gibt es, ein \(\pi\in A^n_{j_1}\cap...\cap A^n_{j_k}\) zu wählen?
- Wir wählen zunächst eine Teilmenge \(M\subseteq\{1,...,n\}\) mit \(j_k\) Elementen. (Dafür gibt es \(\binom n{j_k}\) Möglichkeiten.) Die Elemente aus M sollen die Werte \(\pi(1),...,\pi(j_k)\) werden. Die Elemente aus M können wir der Größe nach ordnen; sei \(\phi:\{1,...,j_k\}\to M\) eine monoton wachsende Bijektion.
- Von M wählen wir das größte Element \(x=\phi(j_k)\) und setzen \(\pi(j_k)=x\). Damit gilt schon mal \(\pi\in A_{j_k}^n\).
- \(M\setminus\{x\}\) hat dann \(j_k-1\) Elemente. Für eine Permutation \(\pi'\in A^{j_k-1}_{j_1}\cap...\cap A^{j_k-1}_{j_{k-1}}\) (davon gibt es nach IV \(a_{j_1,...,j_{k-1}}^{j_k-1}=\frac{(j_k-1)!}{j_1\cdot...\cdot j_{k-1}}\) Möglichkeiten) setzen wir dann \(\pi(j)=\phi(\pi'(j))\) für \(j[Die Antwort wurde nach Beitrag No.53 begonnen.]
|
Profil
|
tripleggg
Ehemals Aktiv
Dabei seit: 20.05.2020
Mitteilungen: 82
| Beitrag No.56, vom Themenstarter, eingetragen 2021-12-05
|
geht es nicht einfacher ?
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8294
Wohnort: Milchstraße
| Beitrag No.57, eingetragen 2021-12-05
|
\quoteon(2021-12-05 14:52 - tripleggg in Beitrag No. 56)
geht es nicht einfacher ?
\quoteoff
Interessiert mich auch. Ihr werden die Aufgabe vielleicht in eurer Übung besprechen. Kannst ja dann mal berichten.
|
Profil
|
tripleggg
Ehemals Aktiv
Dabei seit: 20.05.2020
Mitteilungen: 82
| Beitrag No.58, vom Themenstarter, eingetragen 2021-12-05
|
wollte der @nuramon auch auf dieses konzept hinaus ?
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8294
Wohnort: Milchstraße
| Beitrag No.59, eingetragen 2021-12-05
|
#55 noch ein wenig korrigiert und ergänzt. Hoffe, es stimmt jetzt.
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.60, eingetragen 2021-12-05
|
\(\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}\)
Ich hätte es etwas anders formuliert, aber im Kern so wie StrgAltEntf.
Mir ist noch ein anderer Beweis eingefallen:
Wir definieren für jedes $i\in \{1,\ldots, n\}$ eine Abbildung $f_i:S_n\to S_n$ wie folgt:
Für $\pi\in S_n$ sei $m:= \arg\max_{j\leq i} \pi(j)$. Wir definieren dann $f_i(\pi)$ als die Permutation
$$ f_i(\pi)(j) = \begin{cases}\pi(j), &\text{falls } j> i \lor j < m\\
\pi(m), &\text{falls } j=i\\
\pi(j+1), &\text{falls } m < j [Die Antwort wurde nach Beitrag No.58 begonnen.]\(\endgroup\)
|
Profil
|
tripleggg
Ehemals Aktiv
Dabei seit: 20.05.2020
Mitteilungen: 82
| Beitrag No.61, vom Themenstarter, eingetragen 2021-12-05
|
was eine kranke scheiße ehrlich, ich hätte echt dieses jahr stocha nicht belgen sollen ... junior prof...
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.62, eingetragen 2021-12-05
|
\(\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}\)
Im Prinzip ist das nicht kompliziert, es ist nur etwas anstrengend richtig zu formulieren (das ist häufig der Fall bei Kombinatorischen Problemen).
Hier nochmal No.60, aber etwas anschaulicher:
Sei $1\leq i_1 < i_2< i_3 < \ldots < i_k \leq n$.
Wir starten mit einer beliebigen Permutation $\pi\in S_n$ und wollen diese schrittweise zu einer Permutation aus $A_{i_1}\cap \ldots \cap A_{i_k}$ transformieren.
Zuerst transformieren wir $\pi$ so, dass das Ergebnis in $A_{i_k}$ liegt. Die zweite Transformation erzeugt dann ein Ergebnis, dass sowohl in $A_{i_k}$, als auch in $A_{i_{k-1}}$ liegt. U.s.w.
Erste Transformation:
Sei $\pi= (a_1,\ldots, a_n)$. Betrachte die ersten $i_k$ Werte $a_1,\ldots, a_{i_k}$.
Sei $a_m$ das Maximum dieser $i_k$ Werte.
Die erste Transformation von $\pi$ ist dann $\pi' := (a_1,\ldots, a_{m-1}, a_{m+1}, a_{m+2}, \ldots, a_{i_k -1},a_{i_k} ,a_m, a_{i_k+1}, a_{i_k+2}, \ldots, a_n)$.
In anderen Worten: $\pi'$ entsteht aus $\pi$, indem der größte der ersten $i_k$ Werte an die Position $i_k$ geschoben wurde und die Reihenfolge der anderen Werte gleich geblieben ist.
$\pi'$ ist ein Element von $A_{i_k}$, da $a_m$ per Definition der größte der ersten $i_k$ Werte ist.
Sei umgekehrt $p\in A_{i_k}$ beliebig. Wie viele $\pi\in S_n$ gibt es dann mit $\pi' = p$?
Na ja, bis auf die Position des maximalen Wertes ist die Reihenfolge der ersten $i_k$ Werte von $\pi$ durch $p$ festgelegt. Für den maximalen Wert gibt es $i_k$ Mögliche Positionen.
Diese Betrachtung zeigt, dass es für jedes Element $p$ von $A_{i_k}$ genau $i_k$ Permutationen in $S_n$ gibt, die zu $p$ transformiert werden. Also ist $n! = |S_n| = |A_{i_k}|\cdot i_k$.
Zweite Transformation:
Eigentlich genauso wie die erste, nur starten wir diesmal mit einem Element $\pi \in A_{i_k}$. Von diesem betrachten wir die ersten $i_{k-1}$ Werte, bestimmen davon das Maximum und bilden eine Permutation $\pi'\in A_{i_{k-1}}$.
Da wir bei der Transformation höchstens die ersten $i_{k-1}$ Werte in eine andere Reihenfolge gebracht haben, aber alle anderen Werte gleich gelassen haben, ist $i_k$ wegen $i_k>i_{k-1}$ immer noch ein Rekord von $\pi'$, also sogar $\pi'\in A_{i_k}\cap A_{i_{k-1}}$.
Außerdem können wir uns wie bei der ersten Transformation überlegen, dass $A_{i_k}$ genau $i_{k-1}$ mal so viele Elemente hat wie $A_{i_k}\cap A_{i_{k-1}}$.
Also gilt
$$ |A_{i_k}\cap A_{i_{k-1}}| = \frac{|A_{i_k}|}{i_{k-1}} = \frac{|S_n|}{i_{k-1}i_k}.$$
Die dritte Transformation erzeugt dann aus einem Element $\pi\in A_{i_k}\cap A_{i_{k-1}}$ ein Element $\pi'\in A_{i_k}\cap A_{i_{k-1}} \cap A_{i_{k-2}}$.
Und so weiter, bis man am Ende nach der $k$-ten Transformation ein Element in $A_{i_k}\cap A_{i_{k-1}} \cap \ldots \cap A_{i_1}$ erhält und bewiesen hat, dass
$$ \left|A_{i_k}\cap A_{i_{k-1}} \cap \ldots \cap A_{i_1}\right| = \frac{|S_n|}{i_1i_2\cdots i_k}.$$
\(\endgroup\)
|
Profil
|
Bozzo
Senior 
Dabei seit: 11.04.2011
Mitteilungen: 2289
Wohnort: Franken
 | Beitrag No.63, eingetragen 2021-12-06
|
Es ist |Ai| = n⋅(n-1)⋅⋅⋅(i+1)⋅1⋅(i-1)⋅⋅⋅2⋅1 = n!/i, da man n Moeglichkeiten fuer π(n) hat, danach noch n-1 Moeglichkeiten fuer π(n-1), usw. bis schliesslich i+1 Moeglichkeiten, π(i+1) zu waehlen. Dann hat man nur eine Moeglichkeit π(i) zu waehlen, weil man hier die groesste verbleibende Zahl nehmen muss, und schliesslich wieder i-1 Moeglichkeiten fuer π(i-1), usw. bis schliesslich zwei Moeglichkeiten fuer π(2) und eine fuer π(1).
Fuer i < j hat man analog |Ai ∩ Aj| = n⋅(n-1)⋅⋅⋅(j+1)⋅1⋅(j-1)⋅⋅⋅(i+1)⋅1⋅(i-1)⋅⋅⋅2⋅1 = n!/(i⋅j), da man wenn man die Werte der Permutation vom letzten an rueckwaerts besetzt, immer die volle Anzahl an verbleibenden Zahlen waehlen kann, ausser an j. und i. Stelle, an denen man jeweils die groesste Zahl waehlen muss, die man noch uebrig hat.
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8294
Wohnort: Milchstraße
| Beitrag No.64, eingetragen 2021-12-06
|
Profil
|
| tripleggg hat die Antworten auf ihre/seine Frage gesehen. | | Seite 2 | Gehe zur Seite: 1 | 2 |
|
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?
