Zusammenfassen von Paaren < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Auf wieviele verschiedene Arten kann man 2n Personen zu n (ungeordneten)
Paaren zusammenfassen? Gib alle Möglichkeiten für n = 1, 2, 3 explizit an. |
Nehmen wir an es handelt sich um 2 Personen, also n=1. Ich bezeichne diese mit a und b. Ungeordnete Paare heißt doch, dass ich sowohl das Paar a,b also auch das Paar b,a bilden kann, oder? Falls ja, dann wäre es doch ziemlich einfach. Dann gibt es insgesamt [mm] n^{2} [/mm] Arten. Ich würde mich über einen Hinweis freuen,
Tstesefliege
|
|
| |
|
Hallo Tsetsefliege!
Ok, hier der Hinweis:
das ist falsch.
Schreib doch mal alle Möglichkeiten für n=1,2,3 auf. Dann siehst Du bestimmt mehr, und für die Lösung der Aufgabe ist der Schritt ja sowieso gefordert.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:03 Mo 08.11.2010 | | Autor: | Peter_Pein |
> Hallo Tsetsefliege!
>
> Ok, hier der Hinweis:
> das ist falsch.
>
> ... Dann
> siehst Du bestimmt mehr,...
>
> Grüße
> reverend
>
da es um ungeordnete Paare geht, sollte "Tsetsefliege" eigentlich weniger (als [mm]n^{2}[/mm]) sehen ![[sorry]](/images/smileys/sorry.gif "[sorry]")
Gruß,
Peter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:12 Mo 08.11.2010 | | Autor: | reverend |
Hehe. Das meinte ich nicht, aber gerade darum danke für den Hinweis!
"Mehr sehen" sollte sowas wie "deutlicher sehen" heißen, nicht etwa eine Mengenangabe.
lg
rev
|
|
|
| |
|
Ok, also für die verschiedenen n schaut das dann so aus:
n = 1 , 1 Paar
n = 2, 6 Paare
n = 3, 15 Paare
Es handelt sich dabei doch um eine injektive Funktion der geraden natürlichen Zahlen in eine bestimmte Anzahl der natürlichen Zahlen oder?
|
|
|
| |
|
Hallo nochmal,
nein, nicht ganz. Gefragt war doch:
Auf wieviele verschiedene Arten kann man 2n Personen zu n (ungeordneten) Paaren zusammenfassen?
Schauen wir mal n=2 an. Es gibt die Personen a,b,c,d und damit folgende Zusammenfassungen zu n Paaren:
$ [mm] \{(a,b),\ (c,d)\}, \{(a,c),\ (b,d)\}, \{(a,d),\ (b,c)\} [/mm] $
- also nur 3 Möglichkeiten. Bei n=3 wird es etwas schwieriger, aber da wird auch deutlich, wie es möglicherweise weiter geht. Schreib doch mal explizit alle möglichen Zusammenfassungen auf, also alle Möglichkeiten, n Paare aus den 2n Personen zu bilden.
Grüße
reverend
|
|
|
| |
|
Also wenn n = 3 komme ich auf insgesamt 15 Möglichkeiten. Ich komme jedoch leider nicht weiter.
Explizit würde das bei n=3 bei mir so aussehen:
{(a,b),(c,d),(e,f)} {(a,c),(b,d),(e,f)} {(a,f),(b,c),(e,d)}
{(a,b),(c,e),(d,f)} {(a,c),(b,e),(d,f)} {(a,f),(b,d),(e,c)}
{(a,b),(c,f),(d,e)} {(a,c),(b,f),(d,e)} ....... {(a,f),(b,e),(c,d)}
Dazwischen gibt es noch 3 dieser Blöcke, also insgeamt 15 Mögl.
|
|
|
| |
|
Hat denn niemand einen Idee wie man dieses Beispiel weiter verfolgen könnte?
|
|
|
| |
|
Hallo nochmal,
ja, ist ok.
Für n=1 gibt es also 1 Möglichkeit
Für n=2 gibt es also 3 Möglichkeiten, wobei 3=1*3
Für n=3 gibt es also 15 Möglichkeiten, wobei 15=1*3*5
Es gebe also m(n) Möglichkeiten, nur abhängig von n. Du müsstest jetzt noch eine Überlegung finden, die dafür garantiert, dass $ m(n+1)=(2n+1)*m(n) $ ist, und am besten auch eine Schreibweise für die Bildung von m(n).
Grüße
reverend
|
|
|
| |
|
Aber ich kann doch einfach auch folgendes schreiben: Es handelt sich ja anscheinend um die aufsteigende Multiplaktion der ungeraden Zahlen, also
1*3*5*7...*(2n+1)
[mm] \produkt_{k=0}^{n}(2k+1) [/mm] = [mm] \bruch{(2n+1)!}{2^{n}*n!}
[/mm]
Jetzt muss ich noch den Indizes angleichen, also auf der rechten Seite setze ich für jedes n ein (n-1) ein.
=> Die Anzahl der Möglichkeiten aus 2n Personen n Paare zu bilden = [mm] \bruch{(2n-1)!}{2^{n-1}*(n-1)!}
[/mm]
|
|
|
| |
|
Ja, wunderbar. Die Formel stimmt, aber Du musst noch zeigen, warum.
Grüße
reverend
|
|
|
| |
|
Genügt es nicht einfach die Ergebnisse aus der Formel mit denen aus der expliziten Form zu überprüfen? Du hast vorhin noch erwähnt ich muss Überlegungen für die folgende Formel finden: m(n+1)=2(n+1)*m(n)
Wenn ich jedoch für n gleich 1 setz, steht auf der linken Seite 3 und auf der rechten Seite 4 ?
|
|
|
| |
|
Guten Morgen!
> Genügt es nicht einfach die Ergebnisse aus der Formel mit
> denen aus der expliziten Form zu überprüfen?
Ja, das genügt.
> Du hast
> vorhin noch erwähnt ich muss Überlegungen für die
> folgende Formel finden: m(n+1)=2(n+1)*m(n)
Oh, war ich das? So ist die Formel falsch. Es muss heißen:
$ [mm] m(n+1)=\blue{(2n+1)}*m(n) [/mm] $
> Wenn ich jedoch für n gleich 1 setz, steht auf der linken
> Seite 3 und auf der rechten Seite 4 ?
In der korrigierten Form nicht mehr.
Es ist ja m(1)=1. Das muss man separat bestimmen, als Rekursionsanfang.
Ab da gilt die Formel aber: $ m(1+1)=(2*1+1)*m(1)=3*1 $, also m(2)=3
Grüße
rev
|
|
|
|
