www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Binominalkoeffizient-Ungl.
Binominalkoeffizient-Ungl. < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Binominalkoeffizient-Ungl.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:35 Do 18.10.2012
Autor: Apfelchips

Aufgabe
Sei [mm]n,m \in \IN[/mm] mit [mm]m \neq 0[/mm] und [mm]m < n[/mm]. Zeigen Sie durch direkte Rechnung:

[mm]{{m \choose k}} < {{n \choose k} \mbox{ für } k = 1, \ldots, n; \qquad \bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}} \mbox{ für } k = 2, \ldots, n[/mm]



Ich bin mir nicht sicher, was mit "direkter Rechnung" gemeint ist, aber ich versuch's einfach mal (die zweite Ungleichung beachte ich erst einmal überhaupt nicht):

[mm]\bruch{m!}{k! * (m-k)!} < \bruch{n!}{k! * (n-k)!}[/mm]

sei k=n

[mm]\bruch{m!}{n! * (m-n)!} < \bruch{n!}{n! * \underbrace{(n-n)!}_{= 1}} = \bruch{n!}{n!} = 1[/mm]

Wenn [mm](m-n)![/mm] nun immer 1 wäre, dann wäre [mm]\bruch{m!}{n!} < 1[/mm] für alle [mm]n,m \in \IN[/mm] mit [mm]m \neq 0[/mm] und [mm]m < n[/mm] wahr.

Allerdings ist [mm](m-n)![/mm] immer negativ – und mit Fakultäten von negativen, ganzen Zahlen ist das ja so eine Sache …

Mein Beweis läuft daher ins Leere. Was mache ich da falsch?


        
Bezug
Binominalkoeffizient-Ungl.: Tipp
Status: (Antwort) fertig Status 
Datum: 17:42 Do 18.10.2012
Autor: pits

Hi Apfelchips,

> Sei [mm]n,m \in \IN[/mm] mit [mm]m \neq 0[/mm] und [mm]m < n[/mm]. Zeigen Sie durch
> direkte Rechnung:
>  
> [mm]{{m \choose k}} < {{n \choose k} \mbox{ für } k = 1, \ldots, n; \qquad \bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}} \mbox{ für } k = 2, \ldots, n[/mm]
>  
>
> Ich bin mir nicht sicher, was mit "direkter Rechnung"
> gemeint ist, aber ich versuch's einfach mal (die zweite
> Ungleichung beachte ich erst einmal überhaupt nicht):

genau so solltest du das machen.

  

> [mm]\bruch{m!}{k! * (m-k)!} < \bruch{n!}{k! * (n-k)!}[/mm]
>  
> sei k=n

Das k kann verschiedene Werte annehmen und deshalb sollte man das nicht festlegen. Wichtig ist hier nur, dass [mm] $k\leq [/mm] n$.

Also "einfach" mit der Ungleichung losrechnen (z.B.  erst mal auf beiden Seiten mit $k!$ multiplizieren. Ich würde dann die Terme mit k auf eine Seite bringen und die anderen auf die andere, aber da muss man dann selbst mal schauen.

Gruß
pits

Bezug
                
Bezug
Binominalkoeffizient-Ungl.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:25 Do 18.10.2012
Autor: Apfelchips


Hey pits,

>  Das k kann verschiedene Werte annehmen und deshalb sollte
> man das nicht festlegen. Wichtig ist hier nur, dass [mm]k\leq n[/mm].

Ich dachte mir schon fast, dass das, was ich versucht habe zu zeigen, nicht allgemein genug ist.


> Also "einfach" mit der Ungleichung losrechnen (z.B.  erst
> mal auf beiden Seiten mit [mm]k![/mm] multiplizieren. Ich würde
> dann die Terme mit k auf eine Seite bringen und die anderen
> auf die andere, aber da muss man dann selbst mal schauen.

Ich hab's mal gewagt und die Ungleichung (genau so) umgeformt. Die Zwischenschritte poste ich jetzt nicht (es sei denn,  das Ergebnis meiner Umformungsarbeiten ist falsch):

[mm]\bruch{(n-k)!}{(m-k)!} < \bruch{n!}{m!}[/mm]

k als Subtrahend im Zähler und Nenner des linken Bruchs sorgt dafür, dass der linke Ausdruck stets kleiner ist als der rechte (da [mm]k \geq 1[/mm]).

War das alles?

Bezug
                        
Bezug
Binominalkoeffizient-Ungl.: Antwort
Status: (Antwort) fertig Status 
Datum: 18:31 Do 18.10.2012
Autor: pits


> [mm]\bruch{(n-k)!}{(m-k)!} < \bruch{n!}{m!}[/mm]
>  
> k als Subtrahend im Zähler und Nenner des linken Bruchs
> sorgt dafür, dass der linke Ausdruck stets kleiner ist als
> der rechte (da [mm]k \geq 1[/mm]).
>  
> War das alles?

Yep. Ich würde so argumentieren, dass sowohl links als auch rechts $m-n$ Faktoren stehen, die linken sind jeweils immer kleiner als ihr gegenpaart im rechten Produkt.

Gruß
pits

Bezug
                                
Bezug
Binominalkoeffizient-Ungl.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:57 Do 18.10.2012
Autor: Apfelchips


> Ich würde so argumentieren, dass sowohl links als
> auch rechts [mm]m-n[/mm] Faktoren stehen, die linken sind jeweils
> immer kleiner als ihr gegenpaart im rechten Produkt.

Okay, dankeschön.

Dann kümmere ich mich mal um den zweiten teil der Aufgabe.
Hier fällt mir auf, dass in dem Nenner des vorletzten Terms eine Fakultät auftaucht, im Nenner des letzten Terms eine Potenz. Die Fakultät wächst schneller als jede beliebige Potenz, das heißt der Nenner des vorletzten Termins ist immer größer als der des letzten Terms. Dadurch ist der vorletzte Term immer kleiner als der letzte Term.

Für die ersten beiden Terme kann ich leider nicht so argumentieren. Es ist offensichtlich, dass ich die aus der ersten Ungleichung (die vor dem Semikolon in der Aufgabenstellung) gezogenen Erkenntnisse hier verwenden soll – allerdings stellt sich mir die Frage, wie.


Bezug
                                        
Bezug
Binominalkoeffizient-Ungl.: Antwort
Status: (Antwort) fertig Status 
Datum: 22:18 Do 18.10.2012
Autor: pits

Hi Apfelchips,

> Dann kümmere ich mich mal um den zweiten teil der
> Aufgabe.
>  Hier fällt mir auf, dass in dem Nenner des vorletzten
> Terms eine Fakultät auftaucht, im Nenner des letzten Terms
> eine Potenz. Die Fakultät wächst schneller als jede
> beliebige Potenz, das heißt der Nenner des vorletzten
> Termins ist immer größer als der des letzten Terms.
> Dadurch ist der vorletzte Term immer kleiner als der letzte
> Term.

So kannst du nicht argumentieren, denn das Wachsen würde dann ja nur für große Werte gelten. Ich würde die Fakultät und die Potenz wieder als Produkt auffassen und jeden Faktor vergleichen.

>  
> Für die ersten beiden Terme kann ich leider nicht so
> argumentieren. Es ist offensichtlich, dass ich die aus der
> ersten Ungleichung (die vor dem Semikolon in der
> Aufgabenstellung) gezogenen Erkenntnisse hier verwenden
> soll – allerdings stellt sich mir die Frage, wie.

Ich denke nicht, dass die Erkenntnis verwendet werden soll, sondern das gleiche Verfahren.  Wieder hinschreiben, durch Fakultäten ausdrücken, geschickt umformen und aufmerksam hinschauen.
Leider tippe ich gerade auf meiner Handytastatur, daher ist die Antwort etwas knapp.

Gruß pits  

Bezug
                                                
Bezug
Binominalkoeffizient-Ungl.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:17 Sa 20.10.2012
Autor: Apfelchips

Ich komme hier leider immer noch nicht wirklich weiter …

Zunächst einmal habe ich die Ungleichungskette wie folgt umgeschrieben:

[mm]\bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}}[/mm]

[mm]\bruch{1}{m^k}\left(\bruch{m!}{k!(m-k)!}\right) < \bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}}[/mm]


Nun schaue ich mir die letzten beiden Terme an:

[mm]\bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}} \qquad | * 2^{k-1}[/mm]

[mm]\bruch{2^{k-1}}{k(k-1)!} \leq 1 \qquad | * k(k-1)![/mm]

[mm]2^{k-1} \leq k(k-1)![/mm]

Weitere, sinnvolle Umformungsmöglichkeiten sehe ich hier nicht.


Nun zum zweiten und dritten Term:

[mm]\bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \qquad | * n^k[/mm]

[mm]\bruch{n!n^k}{k!(n-k)!} \leq \bruch{n^k}{k(k-1)!} \qquad | : n![/mm]

[mm]\bruch{n^k}{k(k-1)! * (n-k)!} \leq \bruch{n^k}{k(k-1)! * n(n-1)!}[/mm]

Hier ist der Zähler jeweils identisch und auch die Nenner sind ähnlich. Hier ist insbesondere im rechten Bruch ein Faktor mehr zu erkennen.


Ist dieser Wege eine sinnvolle Beweisstrategie?

Bezug
                                                        
Bezug
Binominalkoeffizient-Ungl.: Antwort
Status: (Antwort) fertig Status 
Datum: 14:29 Sa 20.10.2012
Autor: reverend

Hallo Apfelchips,

auch hier behandelst Du offenbar nur den Fall [mm] k\le{m}, [/mm] nicht aber [mm] m

> Ich komme hier leider immer noch nicht wirklich weiter …
>  
> Zunächst einmal habe ich die Ungleichungskette wie folgt
> umgeschrieben:
>  
> [mm]\bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}}[/mm]
>  
> [mm]\bruch{1}{m^k}\left(\bruch{m!}{k!(m-k)!}\right) < \bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}}[/mm]

Für [mm] k\le{m} [/mm] ist das ok.

> Nun schaue ich mir die letzten beiden Terme an:
>  
> [mm]\bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}} \qquad | * 2^{k-1}[/mm]
>  
> [mm]\bruch{2^{k-1}}{k(k-1)!} \leq 1 \qquad | * k(k-1)![/mm]
>  
> [mm]2^{k-1} \leq k(k-1)![/mm]
>  
> Weitere, sinnvolle Umformungsmöglichkeiten sehe ich hier
> nicht.

Die Aufspaltung der Fakultät ist hier nicht sinnvoll. Rechts steht ja eigentlich k! - und das hat k Faktoren, wovon der erste die 1 ist und die übrigen (k-1) Faktoren alle [mm] \ge{2} [/mm] sind.

Den Sonderfall k=1 muss man auch noch überprüfen.

> Nun zum zweiten und dritten Term:
>  
> [mm]\bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \qquad | * n^k[/mm]
>  
> [mm]\bruch{n!n^k}{k!(n-k)!} \leq \bruch{n^k}{k(k-1)!} \qquad | : n![/mm]
>  
> [mm]\bruch{n^k}{k(k-1)! * (n-k)!} \leq \bruch{n^k}{k(k-1)! * n(n-1)!}[/mm]
>  
> Hier ist der Zähler jeweils identisch und auch die Nenner
> sind ähnlich. Hier ist insbesondere im rechten Bruch ein
> Faktor mehr zu erkennen.

Auch hier ist es eher störend, k! als k(k-1)! zu schreiben.

> Ist dieser Wege eine sinnvolle Beweisstrategie?

Ich sehe keine Strategie. Du rechnest irgendwie herum, aber ohne zu wissen, wo Du eigentlich hinwillst.

[mm] \bruch{1}{n^k}\vektor{n\\k}=\bruch{1}{n^k}*\bruch{n!}{k!(n-k)!}\le\bruch{1}{k!}\quad\big|*k! [/mm]

[mm] \bruch{n!}{n^k}*\bruch{1}{(n-k)!}\le\bruch{n!}{n^k}\le{1} [/mm]

Der mittlere Teil ist eine einfache Abschätzung. [mm] \tfrac{1}{(n-k)!}\le{1} [/mm] gilt hier ja ohne Ausnahme.

edit: Diese Abschätzung ist falsch und daher nutzlos. Siehe meinen folgenden Beitrag.

Jetzt kannst Du den Bruch [mm] \bruch{n!}{n^k} [/mm] wieder faktorenweise betrachten.

Grüße
reverend


Bezug
                                                                
Bezug
Binominalkoeffizient-Ungl.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:11 Sa 20.10.2012
Autor: Apfelchips


> > Nun zum zweiten und dritten Term:
>  >  
> > [mm]\bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \qquad | * n^k[/mm]
>  
> >  

> > [mm]\bruch{n!n^k}{k!(n-k)!} \leq \bruch{n^k}{k(k-1)!} \qquad | : n![/mm]
>  
> >  

> > [mm]\bruch{n^k}{k(k-1)! * (n-k)!} \leq \bruch{n^k}{k(k-1)! * n(n-1)!}[/mm]
>  
> >  

> > Hier ist der Zähler jeweils identisch und auch die Nenner
> > sind ähnlich. Hier ist insbesondere im rechten Bruch ein
> > Faktor mehr zu erkennen.
>  
> Auch hier ist es eher störend, k! als k(k-1)! zu
> schreiben.
>  
> > Ist dieser Wege eine sinnvolle Beweisstrategie?
>
> Ich sehe keine Strategie. Du rechnest irgendwie herum, aber
> ohne zu wissen, wo Du eigentlich hinwillst.

Vermutlich ist das auch wirklich mein Problem …


>  
> [mm]\bruch{1}{n^k}\vektor{n\\ k}=\bruch{1}{n^k}*\bruch{n!}{k!(n-k)!}\le\bruch{1}{k!}\quad\big|*k![/mm]
>  
> [mm]\bruch{n!}{n^k}*\bruch{1}{(n-k)!}\le\bruch{n!}{n^k}\le{1}[/mm]
>  
> Der mittlere Teil ist eine einfache Abschätzung.
> [mm]\tfrac{1}{(n-k)!}\le{1}[/mm] gilt hier ja ohne Ausnahme.
>  
> Jetzt kannst Du den Bruch [mm]\bruch{n!}{n^k}[/mm] wieder
> faktorenweise betrachten.

Gestatte mir bitte diese blöde Frage: Warum sollte ich diesen Bruch weiter betrachten wollen? Das [mm]\bruch{1}{n^k}\vektor{n\\ k}\le\bruch{1}{k!}[/mm] wurde hiermit doch schon gezeigt, oder nicht?

Bezug
                                                                        
Bezug
Binominalkoeffizient-Ungl.: pardon - neuer Anlauf
Status: (Antwort) fertig Status 
Datum: 18:51 Sa 20.10.2012
Autor: reverend

Hallo nochmal,

nein, da ist mir ein Fehler unterlaufen - die Abschätzung ist unsinnig.

> > [mm]\bruch{1}{n^k}\vektor{n\\ k}=\bruch{1}{n^k}*\bruch{n!}{k!(n-k)!}\le\bruch{1}{k!}\quad\big|*k![/mm]
>  
> >  

> > [mm]\bruch{n!}{n^k}*\bruch{1}{(n-k)!}\le\bruch{n!}{n^k}\le{1}[/mm]
>  >  
> > Der mittlere Teil ist eine einfache Abschätzung.
> > [mm]\tfrac{1}{(n-k)!}\le{1}[/mm] gilt hier ja ohne Ausnahme.

Die Mitte streichen wir besser wieder, es gilt nämlich keineswegs [mm] n!/n^k\le{1}, [/mm] nimm z.B. mal k=1...

> > Jetzt kannst Du den Bruch [mm]\bruch{n!}{n^k}[/mm] wieder
> > faktorenweise betrachten.
>  
> Gestatte mir bitte diese blöde Frage: Warum sollte ich
> diesen Bruch weiter betrachten wollen? Das
> [mm]\bruch{1}{n^k}\vektor{n\\ k}\le\bruch{1}{k!}[/mm] wurde hiermit
> doch schon gezeigt, oder nicht?

Nein, leider nicht. Aber die faktorenweise Betrachtung klappt trotzdem.

Zu zeigen ist (siehe Zwischenschritt oben)

[mm] \bruch{n!}{n^k(n-k)!}\le{1} [/mm]

Nochmal multiplizieren...

[mm] n!\le n^k(n-k)! [/mm]

Jetzt haben wir links n Faktoren von 1 bis n, rechts n-k Faktoren von 1 bis n-k, die also eine genau gleiche Entsprechung auf der linken Seite haben, sowie k Faktoren, die alle =n sind. Die links noch verbliebenen sind aber alle [mm] \le{n}. [/mm] Die Ungleichung ist also wahr.

Besser ist das zu sehen, wenn man die Produktschreibweise wählt. Dann lautet die Ungleichung nach dem Kürzen von (n-k)! nämlich

[mm] \produkt_{i=1}^{k}(n-i+1)\le\produkt_{i=1}^{k}n [/mm]

...und für [mm] 1\le{i} [/mm] ist nun [mm] n-i+1\le{n}. [/mm]
So sieht man den Vergleich der Faktoren deutlicher.

Grüße
reverend


Bezug
                                                                                
Bezug
Binominalkoeffizient-Ungl.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:21 Sa 20.10.2012
Autor: Apfelchips


Hallo,

> Nein, leider nicht. Aber die faktorenweise Betrachtung
> klappt trotzdem.
>  
> Zu zeigen ist (siehe Zwischenschritt oben)
>  
> [mm]\bruch{n!}{n^k(n-k)!}\le{1}[/mm]
>  
> Nochmal multiplizieren...
>  
> [mm]n!\le n^k(n-k)![/mm]
>  
> Jetzt haben wir links n Faktoren von 1 bis n, rechts n-k
> Faktoren von 1 bis n-k, die also eine genau gleiche
> Entsprechung auf der linken Seite haben,

Bis hierhin kann ich's nachvollziehen.


> sowie k Faktoren,
> die alle =n sind. Die links noch verbliebenen sind aber
> alle [mm]\le{n}.[/mm] Die Ungleichung ist also wahr.

Aber warum sind die k Faktoren alle gleich n?


Dann noch zum Ausstehenden Vergleich [mm]\bruch{1}{m^k} {{m \choose k}} < \bruch{1}{n^k} {{n \choose k}}[/mm]:

Lässt sich hier nach Umformung zu [mm]\bruch{m!}{n!} < \bruch{m^k(m-k)!}{n^k(n-k)!}[/mm] genauso argumentieren?

Bezug
                                                                                        
Bezug
Binominalkoeffizient-Ungl.: Antwort
Status: (Antwort) fertig Status 
Datum: 09:21 So 21.10.2012
Autor: pits

Hallo apfelchips


> > [mm]n!\le n^k(n-k)![/mm]
>  >  
> > Jetzt haben wir links n Faktoren von 1 bis n, rechts n-k
> > Faktoren von 1 bis n-k, die also eine genau gleiche
> > Entsprechung auf der linken Seite haben,
>  
> Bis hierhin kann ich's nachvollziehen.
>  
>
> > sowie k Faktoren,
> > die alle =n sind. Die links noch verbliebenen sind aber
> > alle [mm]\le{n}.[/mm] Die Ungleichung ist also wahr.
>  
> Aber warum sind die k Faktoren alle gleich n?

Schreib dir die Faktoren alle mal hin für z.B. n=8 und k=3, dann sieht man wo die k (bzw 3) Faktoren sind, die alle gleich n (8) sind und es hilft beim verstehen.

> Dann noch zum Ausstehenden Vergleich [mm]\bruch{1}{m^k} {{m \choose k}} < \bruch{1}{n^k} {{n \choose k}}[/mm]:
>  
> Lässt sich hier nach Umformung zu [mm]\bruch{m!}{n!} < \bruch{m^k(m-k)!}{n^k(n-k)!}[/mm]
> genauso argumentieren?

Man kann genau so argumentieren, ich würde aber die beiden Fakultäten mit $m$ auf eine Seite schreiben und die beiden mit $n$ auf die andere Seite, denn [mm] $\frac{m!}{(m-k)!}$ [/mm] bedeutet ja dass von dem m Faktoren (aus $m!$) die letzten m-k Faktoren "abgeschnitten" werden.

Gruß
pits


Bezug
                                                                                                
Bezug
Binominalkoeffizient-Ungl.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:06 So 21.10.2012
Autor: Apfelchips


> > > sowie k Faktoren,
> > > die alle =n sind. Die links noch verbliebenen sind aber
> > > alle [mm]\le{n}.[/mm] Die Ungleichung ist also wahr.
>  >  
> > Aber warum sind die k Faktoren alle gleich n?
>  
> Schreib dir die Faktoren alle mal hin für z.B. n=8 und
> k=3, dann sieht man wo die k (bzw 3) Faktoren sind, die
> alle gleich n (8) sind und es hilft beim verstehen.

Danke, jetzt kann ich auch das nachvollziehen: Bei [mm]n^k[/mm] taucht der Faktor n genau k mal auf (im Beispiel eben [mm]1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 \leq (8 * 8 * 8) * (1 * 2 * 3 * 4 * 5)[/mm]).


> Man kann genau so argumentieren, ich würde aber die beiden
> Fakultäten mit [mm]m[/mm] auf eine Seite schreiben und die beiden
> mit [mm]n[/mm] auf die andere Seite, denn [mm]\frac{m!}{(m-k)!}[/mm] bedeutet
> ja dass von dem m Faktoren (aus [mm]m![/mm]) die letzten m-k
> Faktoren "abgeschnitten" werden.

Ich verstehe. Also:

[mm]\bruch{m!}{m^k(m-k)!} < \bruch{n!}{n^k(n-k)!}[/mm]


Bezug
                                                                                                        
Bezug
Binominalkoeffizient-Ungl.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:12 So 21.10.2012
Autor: pits

>
> Danke, jetzt kann ich auch das nachvollziehen: Bei [mm]n^k[/mm]
> taucht der Faktor n genau k mal auf (im Beispiel eben [mm]1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 \leq (8 * 8 * 8) * (1 * 2 * 3 * 4 * 5)[/mm]).

genau so! cool


> > Man kann genau so argumentieren, ich würde aber die beiden
> > Fakultäten mit [mm]m[/mm] auf eine Seite schreiben und die beiden
> > mit [mm]n[/mm] auf die andere Seite, denn [mm]\frac{m!}{(m-k)!}[/mm] bedeutet
> > ja dass von dem m Faktoren (aus [mm]m![/mm]) die letzten m-k
> > Faktoren "abgeschnitten" werden.
>  
> Ich verstehe. Also:
>  
> [mm]\bruch{m!}{m^k(m-k)!} < \bruch{n!}{n^k(n-k)!}[/mm]
>  

Genau so würde ich es machen. Und bei [mm]\frac{m!}{(m-k)!}[/mm] bleiben genau $k$ Faktoren stehen (ebenso bei [mm]\frac{n!}{(n-k)!}[/mm]), die man einzeln vergleichen kann.

Gruß
pits

Bezug
                                                                                                                
Bezug
Binominalkoeffizient-Ungl.: doch nicht so einfach...
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:23 So 21.10.2012
Autor: reverend

Hallo pits, hallo Apfelchips,

> > Also:
>  >  
> > [mm]\bruch{m!}{m^k(m-k)!} < \bruch{n!}{n^k(n-k)!}[/mm]
>  >  
>
> Genau so würde ich es machen. Und bei [mm]\frac{m!}{(m-k)!}[/mm]
> bleiben genau [mm]k[/mm] Faktoren stehen (ebenso bei
> [mm]\frac{n!}{(n-k)!}[/mm]), die man einzeln vergleichen kann.

Ja, das wäre noch kein Problem. Aber da steht ja noch mehr - nämlich [mm] m^k [/mm] bzw. [mm] n^k [/mm] im Nenner. Da muss man doch noch etwas mehr argumentieren.

Dabei wird die Ungleichung [mm] \left(1-\bruch{i}{m}\right)<\left(1-\bruch{i}{n}\right) [/mm] eine Rolle spielen. ;-)

Übrigens ist nach wie vor der Fall [mm] m
Grüße
reverend


Bezug
                        
Bezug
Binominalkoeffizient-Ungl.: noch nicht fertig!
Status: (Antwort) fertig Status 
Datum: 13:53 Sa 20.10.2012
Autor: reverend

Hallo Apfelchips,

damit ist diese Aufgabe noch nicht erledigt.

> >  Das k kann verschiedene Werte annehmen und deshalb sollte

> > man das nicht festlegen. Wichtig ist hier nur, dass [mm]k\leq n[/mm].
>  
> Ich dachte mir schon fast, dass das, was ich versucht habe
> zu zeigen, nicht allgemein genug ist.
>
> > Also "einfach" mit der Ungleichung losrechnen (z.B.  erst
> > mal auf beiden Seiten mit [mm]k![/mm] multiplizieren. Ich würde
> > dann die Terme mit k auf eine Seite bringen und die anderen
> > auf die andere, aber da muss man dann selbst mal schauen.
>  
> Ich hab's mal gewagt und die Ungleichung (genau so)
> umgeformt. Die Zwischenschritte poste ich jetzt nicht (es
> sei denn,  das Ergebnis meiner Umformungsarbeiten ist
> falsch):
>  
> [mm]\bruch{(n-k)!}{(m-k)!} < \bruch{n!}{m!}[/mm]
>  
> k als Subtrahend im Zähler und Nenner des linken Bruchs
> sorgt dafür, dass der linke Ausdruck stets kleiner ist als
> der rechte (da [mm]k \geq 1[/mm]).

Da ist die Argumentation von pits (die hier folgt) deutlich klarer: Es sind jeweils (n-m) Faktoren, und die linken sind kleiner als die rechten.

Allerdings ist mit dieser Rechnung und Argumentation nur der Fall [mm] $k\le [/mm] m<n$ erledigt, denn Du hast hier die Standarddefinition der Binomialkoeffizienten verwendet. Da muss in [mm] \vektor{m\\k} [/mm] gelten: [mm] k\le{m}. [/mm]

Offen bleibt nun aber noch der Fall [mm] m
Schau Dir dazu mal die []verallgemeinerte Definition an.

Du wirst für den noch offenen Fall mit k>m nun leicht zeigen können, dass [mm] \vektor{m\\k}=0 [/mm] ist.

> War das alles?

Nein, eben nicht.

Grüße
reverend


Bezug
                                
Bezug
Binominalkoeffizient-Ungl.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:19 Mo 22.10.2012
Autor: HuntingShadow

Hätte da mal eine dumme Frage: Wenn ich die von reverend angesprochene allgemeine Definition des Binomialkoeffizienten für die erste Ungleichung benutze erhalte ich doch theoretisch:

[mm] \bruch{m*...*(m-(k-1))}{k!} [/mm] < [mm] \bruch{n*...*(n-(k-1))}{k!} [/mm]

Sehe ich das richtig?
Und wenn man daruas jetzt durch beidseitige Multiplikation von k!

[mm] m\cdot{}...\cdot{}(m-(k-1)) [/mm] < [mm] n\cdot{}...\cdot{}(n-(k-1)) [/mm]

macht, heißt das doch unter der Vorraussetzung m<n, die in der Aufgabenstellung gegeben ist, dass der linke Teil kleiner als der rechte sein muss, oder mache ich mir das da zu einfach?



Bezug
                                        
Bezug
Binominalkoeffizient-Ungl.: Antwort
Status: (Antwort) fertig Status 
Datum: 11:35 Mo 22.10.2012
Autor: reverend

Hallo HuntingShadow, [willkommenmr]

> Hätte da mal eine dumme Frage:

Antworten können dumm sein (s.u.), Fragen doch aber nicht. ;-)

> Wenn ich die von reverend
> angesprochene allgemeine Definition des
> Binomialkoeffizienten für die erste Ungleichung benutze
> erhalte ich doch theoretisch:
>  
> [mm]\bruch{m*...*(m-(k-1))}{k!}[/mm] < [mm]\bruch{n*...*(n-(k-1))}{k!}[/mm]
>  
> Sehe ich das richtig?
> Und wenn man daruas jetzt durch beidseitige Multiplikation
> von k!
>  
> [mm]m\cdot{}...\cdot{}(m-(k-1))[/mm] < [mm]n\cdot{}...\cdot{}(n-(k-1))[/mm]
>  
> macht, heißt das doch unter der Vorraussetzung m<n, die="" in="" <br="">> der Aufgabenstellung gegeben ist, dass der linke Teil
> kleiner als der rechte sein muss, oder mache ich mir das da
> zu einfach?

Wie mans nimmt. In der Tat sieht es sogar so aus, als könnte die linke Seite sogar größer werden als die rechte, je nachdem wie groß die Beträge der negativen Faktoren werden. Allerdings können die n nicht übersteigen und bei genauerer Betrachtung droht tatsächlich keine Gefahr.

Viel einfacher aber ist die Überlegung, dass für den jetzt betrachteten Fall [mm] m
Grüße
reverend
</n,>

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de