www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 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
Weitere Fächer:

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

Teilmengenanzahl: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 ..

        
Bezug
Teilmengenanzahl: Antwort
Status: (Antwort) fertig Status 
Datum: 03:11 Mo 28.11.2011
Autor: reverend

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 ..


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


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]