Anzahl Elemente bei gegebener Anzahl echter Teilmengen

Eisflamme

Hi,

die Aufgabe ist diese:
Gegeben sei die Anzahl t echter Teilmengen einer Menge. Geben Sie eine Funktion an, die in Abhängigkeit von t die Anzahl der Elemente n der Menge ermittelt.

Beispielsweise soll man t=15 sagen können und n=4 soll eben rauskommen.

Andersrum habe ich bereits eine simple Formel aufgestellt, die also in Abhängigkeit von n t angibt:
$t(n) = (\sum_{k=0}^n {\frac{n!}{(k!*(n-k)!)}})-1$

Spaßeshalber habe ich Mal versucht das Ding als Gleichung von Derive 6 (ja, ich hab nix andres) für n auflösen zu lassen, aber das klappt natürlich nicht.

Einer eine Idee?

Eisflamme

Ich hab das Mal geplottet und es lässt sich annähernd durch exp(x/1.45) annähern... gibt es zwischen Permutationen und der Exponentialfunktion irgendeinen Zusammenhang? Wär ja lustig.

Ich weiß nicht, ob ich dich richtig verstehe (denke aber schon), aber die Anzahl aller Teilmengen einer Menge M mit |M| = n ist gegeben durch P(M), die Potenzmenge von M, mit |P(M)| = 2^n.
In der Potenzmenge ist aber insbesondere auch M selbst enthalten, d.h. die Menge aller echten Teilmengen ist durch t = 2^n - 1 gegeben.
Daraus folgt natürlich, dass n = log₂ (t + 1), im Beispiel:
n = log₂ (t + 1) = log₂ (15 + 1) = 4.

Übrigens haben Teilmengen nicht sonderlich viel mit Permutationen zu tun, da letztere eine Reihenfolge ändern, Teilmengen aber nur die enthaltenen Elemente bestimmen.

@zweiten Post: Die 1.45 ist eigentlich 1 / ln 2, was einfach eine Umformung ist, denn e^x = 2^x / ln 2^

Bashar

Eisflamme schrieb:

$t(n) = (\sum_{k=0}^n {\frac{n!}{(k!*(n-k)!)}})-1$

*hust*
Glücklicherweise ist $\sum_{k=0}^n \binom{n}{k} = 2^n$ (ich hoff mal dir ist nur \binom nicht eingefallen und deshalb hast du es ausgeschrieben) und alle sind happy.

Eisflamme

Ja, binom kannte ich nicht. Die Umformung ist eigentlich klar... Okay, besten Dank

Öhm, auch auf die Gefahr hin, dass das jetzt trivial ist. Aber wieso ist diese Summe 2^n? Passendes Google-Stichwort ebenso herrlich.

Der Beweis (der Mächtigkeit der Potenzmenge, den du inzwischen wegeditiert hast?) geht recht glatt durch, wenn mans über Induktion macht.
Für n = 0 ist die Sache klar. Eine nullelementige Menge hat gerade die leere Menge als Teilmenge, d.h. für |M| = 0 ist P(M) = {{}} und |{{}}| = 1 = 2⁰.
Sei also die Aussage für ein n bewiesen, dann ist M' := M υ {x}, wobei x nicht in M ist, also |M'| = |M| + 1 = n + 1.
Dann ist anschaulich klar, dass die bisherigen 2ⁿ Teilmengen weiterhin enthalten sind, aber für jedes Element X der 2ⁿ Elemente (lt. Induktionsvoraussetzung) der Potenzmenge kommt nun X υ {x} zur neuen Potenzmenge P(M') hinzu, d.h. P(M') = P(M) υ {X υ {x} | X aus P(M)}. Da die Mengen offensichtlich disjunkt sind, ist |P(M) υ {X υ {x} | X aus P(M)}| = |P(M)| + |{X υ {x} | X aus P(M)}| = 2ⁿ + 2ⁿ = 2*2ⁿ = 2ⁿ⁺¹.

Zum Binomialkoeffizienten:
Anschaulich macht das schon deshalb Sinn, weil $\binom{n}{k}$ ja die Anzahl an k-elementigen Teilmengen einer n-elementigen Menge angibt. Wenn du jetzt über die k summierst kriegst du die Anzahl der nullelementigen Teilmengen plus die Anzahl der einelementigen Teilmengen plus ... plus die Anzahl der n-elementigen Teilmengen, d.h. die Mächtigkeit deiner Potenzmenge.

Beweis geht wieder über Induktion, ist aber durch die Indexverschiebung ein wenig frickelig.

Siehe dazu: http://de.wikipedia.org/wiki/Binomialkoeffizient#Summen_mit_Binomialkoeffizienten. Da ist auch ein einfacherer Beweis angegeben.

Michael E.

Eisflamme schrieb:

Öhm, auch auf die Gefahr hin, dass das jetzt trivial ist. Aber wieso ist diese Summe 2^n? Passendes Google-Stichwort ebenso herrlich.

Kennst du den binomischen Lehrsatz?

\begin{align*} (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}\\ \Rightarrow 2^n = (1+1)^n = \sum_{k=0}^n \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^n \binom{n}{k} \end{align*}

ScottZhang

Eisflamme schrieb:

Ich hab das Mal geplottet und es lässt sich annähernd durch exp(x/1.45) annähern... gibt es zwischen Permutationen und der Exponentialfunktion irgendeinen Zusammenhang? Wär ja lustig.

Stirlingformel