Kein Übungsbeispiel, Kombinatorik

[wolti]

Hallo,

Eine Frage zu der Vorlesung von heute. Nehmen wir an wir haben eine n elementige Menge, bestehenden aus M = {u,v}. Ich setze eine Erzeugendenfunktion an. Ich möchte jetzt wieder die Anzahl der möglichen Teilmenge bestimmen.

A(x) = (1 + ux)
B(x) = (1 + vx)

Bilden wir mal A(x) * B(x) = 1 + (u + v)*x + uv*x^2. Rechnen wir das schnell in einen Potenzreihe rauf, ich erhalte also eine folge <ak> = <1,u+v,uv,0,0,0,...>.
Ich müsste nun über den Koeffizienten von x^n die Teilmenge rausbekommen. Für den Koeffizienten von x^n schreiben wir ja [x^n].

Was mich nun irritiert, der Koeffizient von [x^0] ist die Anzahl der Nullelementigen Teilmenge, und in diesem Fall 1. (Zuerst wieder u=1, v=1 setzen) Damit müsste ansich schon die leere Menge gemeint sein, weil die ist ja auch Teilmenge und damit stimmt ja der 1 wieder. Oder habe ich mich da geirrt ?

Grüße,
wolti

[psycho]

naja das mit 1 wird schon stimmen, weil der binomialkoeffizient von n über 0 ist ja 1, und der baron hat ja gesagt, dass der binomialkoeffizient die anzahl der k-elementigen teilmenge einer n-elementigen menge ist...

naja ich nehm dann auch an, dass das dann wohl die leere menge sein wird

[wolti]

Ja, glaube ich jetzt mittlerweile auch. Aber wenn du es in einem deutschen Satz formulierst klingt es momisch.

"Wiviele Möglichkeiten gibt es 0 Element aus einer n-elementigen Menge zu hohlen" und du gibst als Anwort 1
Wenn man keine als Möglichkeit betrachtet, dann stimmt Sie..

Grüße,
Wolti

[wolti]

Ist erledigt.. Habe heute den Baron vor dem Rep noch gefragt und er hat mir das kurz und bündig erklärt.


Nochwas. Zum letzten Teil der Vorlesung:

Das Beispiel bei den Multimengen (Also wenn wir Vielfachheiten auch
noch betrachten wollen ist mir ja noch klar). Allerdings gehts bei der
Herleitung seiner Formel bei mir ein bisschen drüber. Ich schreibe
das nochmal kurz her.

Kombination von n-Elementen zu k-ten Klasse mit vorgegebenen
erlaubten Wiederhohlungen.

Als erstes Definieren folgendes:

a1 ..... M1 Teilmenge N
.
.
.
an ..... Mn Teilmenge N

__
\
Bi(x) = ) a_i^(j) * x^(j)
/_
j e Mi

Das macht sinn, denn sagen wir mal wie möchten B1(x) und das
Element a1 darf sagen wir 0,2,4 mal vorkommen, dann setzen wir M1
auf {0,2,4} und erhalten
B1(x) = (a_1^0*x^0 + a_1^2*x^2 + a_1^4*x^4}

Jetzt bilden wir das Produkt alle Funktionen von 1 bis n (Siehe wie
wir es in dem Beispiel gemacht haben)

__n_
||
A(X) = B1(x)*B2(x)* ... * Bn(x) = || Bi(x)
||
i=1

[x^k]A(x) liefert uns dann das gewünschte Ergebniss. Die Anzahl der
k-Elementigen Kombinationen.

<-- !!! Hier fängt ein neuer Teil an im Skriptum. Hier wollen wir die Anzahl der Wiederholungen nicht mehr beschränken und schon wird alles klar -->

__ inf
\ 1
) a_i^(j) * x^(j) = ------------- = Bi(aix)
/_ 1 - a_{i}*x
j = 0

1
Bi(x) = -------
1 -x

__n_ ___ inf
|| \
A(X) = || Bi(x) = (1/(1-x))^n = (1-x)^-n = ) ncr(-n,k)*(-1)^k*x^k
|| /__
i=1 k=0



Grüße,
wolti

[Shine]

hm i hätt da eine anschauliche möglichkeit..
was ist wenn du die potenzmenge einer n-elementigen Menge betrachtest, dann ist da ja auch immer die Leere menge drinnen, aber wie wir gelernt haben, gibt es nur EINE leere Menge, folglich gibt es auch nur 1 art von null-ellementigen Mengen...
Klar oda?
Um es fort zu setzen, gibt es ja auch n 1-elementige Teilmengen, n über 2 2-elementige Teilmengen usw...
n n-1elementige Teilmengen und eine n-Elementige.. Ist doch eigentlich klar...
i mein i weiß net ob des zu deinen ausführungen passt, aber es erklärt für mich zumindest, wieso es eine nullelementige Teilmenge gibt...oda?

mfg Shine