Teilmengenanzahl < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:42 Mo 28.11.2011 | | Autor: | Physy |
| Aufgabe | | Wie viele Teilmengen von [mm] \{1,2,...,n\} [/mm] existieren, wenn diese keine drei Zahlen enthalten dürfen, die aufeinanderfolgen? Gib eine Rekursion an. |
Hallo,
also ich habe mir einfach mal die Zahlen für die ersten paar rausgeschriebne und komme auf Folgendes
n=0: 0
n=1: 1
n=2: 3
n=3: 6
n=4: 12
n=5: 24
bzw. eins mehr, wenn man die leere Menge mitzählt. Meine Vermutung ist hier, dass für n > 1 gilt, dass A(n) * 2*A(n-1) ist aber ich bin mir da nicht hundertprozentig sicher. Das ist ja auch nur eine Vermutung.
Was ich auf jeden Fall weiß ist, dass A(n) = 2*A(n-2) + x, da das n-te Element ja mit jedem Ergebnis auf A(n-2) nochmal eine Bindung eingehen kann, da hier ja auf keinen Fall zwei Elemente nebeneinanderstehen können. Die Frage ist nun noch, was dieses x ist ..
|
|
| |
|
Hallo Physy,
hübsche Aufgabe und gute Vorarbeit. Leider sind Dir zwei Fehler unterlaufen, die Deine Vermutung zunichte machen.
> Wie viele Teilmengen von [mm]\{1,2,...,n\}[/mm] existieren, wenn
> diese keine drei Zahlen enthalten dürfen, die
> aufeinanderfolgen? Gib eine Rekursion an.
Beachte, dass auch die leere Menge immer eine mögliche Teilmenge ist.
> also ich habe mir einfach mal die Zahlen für die ersten
> paar rausgeschriebne und komme auf Folgendes
>
> n=0: 0
> n=1: 1
> n=2: 3
> n=3: 6
> n=4: 12
> n=5: 24
>
> bzw. eins mehr, wenn man die leere Menge mitzählt.
Ja, s.o.
Das stimmt, bis auf das letzte Ergebnis. Für n=5 gibt es mit leerer Menge 24 Teilmengen, die die Bedingung erfüllen (also ohne: 23).
Hier lohnt es sich, noch ganz wenig weiter zu machen:
Für n=6 gibt es, wieder mit leerer Menge, 44 mögliche Teilmengen.
Also (jeweils [mm] \emptyset [/mm] mitgezählt):
n=0: [mm] a_0=1
[/mm]
n=1: [mm] a_1=2
[/mm]
n=2: [mm] a_2=4
[/mm]
n=3: [mm] a_3=7
[/mm]
n=4: [mm] a_4=13
[/mm]
n=5: [mm] a_5=24
[/mm]
n=6: [mm] a_6=44
[/mm]
...
Da legt sich für [mm] n\ge{3} [/mm] doch eher folgendes nahe:
[mm] a_n=a_{n-1}+a_{n-2}+a_{n-3}
[/mm]
Überprüf doch mal [mm] a_7=81 [/mm] (?) und - sofern es stimmt - such nach einem Grund, warum diese Rekursion zutrifft.
Interessant wird übrigens eigentlich erst wieder n=8, dann n=11,14,17 etc.
Siehst Du, warum?
Grüße
reverend
Meine
> Vermutung ist hier, dass für n > 1 gilt, dass A(n) *
> 2*A(n-1) ist aber ich bin mir da nicht hundertprozentig
> sicher. Das ist ja auch nur eine Vermutung.
>
> Was ich auf jeden Fall weiß ist, dass A(n) = 2*A(n-2) + x,
> da das n-te Element ja mit jedem Ergebnis auf A(n-2)
> nochmal eine Bindung eingehen kann, da hier ja auf keinen
> Fall zwei Elemente nebeneinanderstehen können. Die Frage
> ist nun noch, was dieses x ist ..
|
|
|
|
