Forums Neueste Beiträge
 

Anzahl von Teilmengen ...

07/01/2008 - 12:13 von Konrad Mühler | Report spam
Hallo,

ich habe ein Problem bei der Berechnung der Anzahl von k-elementigen
Teilmengen einer n-elementigen Menge.

Für ein bestimmtes k ergibt sich die Anzahl ja mit Hilfe des
Binomialkoeffizienten (n über k).

Summiere ich dies für alle k im Interval 0...n auf, um die Anzahl aller
möglichen Teilmengen zu erhalten, so làsst sich das mit Hilfe des
Binomischen Satzes zu 2 hoch n vereinfachen.

Soweit, so gut.

Nun würde ich aber gern die Anzahl aller Teilmengen mit maximal 5
Elementen (oder einer andere bekannten Zahl) berechnen.

Wenn ich die Summe dann aufdrösel, komme ich sehr schnell zu ellenlangen
Fakultàtsformeln.

Ist das der einzige Weg? Oder gibt es auch für diese "Zwischenanzahlen"
eine vereinfachte Formel?

Habt tausend Dank
Konrad
 

Lesen sie die antworten

#1 kilian heckrodt
07/01/2008 - 12:46 | Warnen spam
Konrad Mühler wrote:
Hallo,

ich habe ein Problem bei der Berechnung der Anzahl von k-elementigen
Teilmengen einer n-elementigen Menge.

Für ein bestimmtes k ergibt sich die Anzahl ja mit Hilfe des
Binomialkoeffizienten (n über k).

Summiere ich dies für alle k im Interval 0...n auf, um die Anzahl aller
möglichen Teilmengen zu erhalten, so làsst sich das mit Hilfe des
Binomischen Satzes zu 2 hoch n vereinfachen.

Soweit, so gut.

Nun würde ich aber gern die Anzahl aller Teilmengen mit maximal 5
Elementen (oder einer andere bekannten Zahl) berechnen.

Wenn ich die Summe dann aufdrösel, komme ich sehr schnell zu ellenlangen
Fakultàtsformeln.

Ist das der einzige Weg? Oder gibt es auch für diese "Zwischenanzahlen"
eine vereinfachte Formel?

Habt tausend Dank
Konrad




Mir ist nicht ganz klar, ob du die konkrete Berechnung von Fakultaeten
(wegen des Aufwands) verhindern moechtest oder ob die eine "elegante"
Formel suchst, die die Summe ersetzt.

Fuer Ersteres kannst du einfach auf eine Darstellung ohne Fakultaet
verwenden, d.h. C(n,k)= (n-k+1)/1*..*n/k (k brueche multiplizieren)
anstatt C(n,k)=n!(n-k)!/k!.
Fuer letzteres (die elegante Formel) ist mir keine Loesung bekannt (fuer
ein beliebiges k(=5)),allerdings kannst du ja mal hier dein Glueck
versuchen:

http://binomial.csuhayward.edu/index.html

Ähnliche fragen