Kombinatorik Anzahl Funktionen

Neue Frage »

16.05.2012, 17:25	stromertle	Auf diesen Beitrag antworten »
Kombinatorik Anzahl Funktionen Meine Frage: Wie viele Funktionen $\begin{eqnarray} $f : \{0,1,2\}^n \rightarrow \{0,1\}$ \end{eqnarray}$ gibt es, bei denen der Funktionswert 0 genau k-mal vorkommt? Meine Ideen: Komme bei dieser Frage überhaupt nicht weiter, das einzige was wir haben wäre ein $\begin{eqnarray} Lemma (Potenzregel): "Es\ seien\ A\ und\ B\ endliche\ Mengen\ mit\\ \|\|A\|\| = m\ und\ \|\|B\|\| = n.\\ Dann\ existieren\ genau\ n^m\ Funktionen\ f: A \rightarrow B. \end{eqnarray}$ Zudem wird nur noch kurz das Urnenmodell vorgestellt. Könnte mir jemand bei dieser Aufgabe helfen? Danke im Voraus
16.05.2012, 17:32	Math1986	Auf diesen Beitrag antworten »
RE: Kombinatorik Anzahl Funktionen Rechne die Aufgabe mal für n=1,2,3.. durch und schau dir an, ob du ein Schema erkennst. Weitere Einschränkungen an diese Funktion sind nicht gegeben?
16.05.2012, 18:36	stromertle	Auf diesen Beitrag antworten »
Hallo, nein zu der Funktion sind keine weiteren Einschränkungen gegeben und ich verstehe nicht ganz, wie ich für n = 1,2,3,.... rechnen soll. Ich weiß lediglich, dass die Anzahl der Funktionen insgesamt $\begin{eqnarray} 2^{3^n} \end{eqnarray}$ ist. Aber wie komme ich nun darauf, in wie viele Funktionen k-mal 0 als Funktionswert vorkommt?
16.05.2012, 18:43	Math1986	Auf diesen Beitrag antworten »
Naja, du sollst es mal für festes n rechnen. Fang mal an für n=1: Wie viele Möglichkeiten gibt es da für genau k-mal 0? In diesem Fall hast du ja nur 8 Funktionen zu betrachten, wie viele haben davon 0-mal die 0, wie viele haben 1-mal die 0...?
16.05.2012, 20:47	stromertle	Auf diesen Beitrag antworten »
ok, für n=1 ist das ganze ja klar, da hab ich 0x 0 gibts 1 Fkt. (0->1, 1->1, 2->1) 1x 0 gibts 3 Fkt. (0->0, 1->1, 2->1 \|\| 0->1, 1->0, 2->1 \|\| 0->1, 1->1, 2->0) 2x 0 gibts 3 Fkt. (0->0, 1->0, 2->1 \|\| 0->0, 1->0, 2->1 \|\| 0->1, 1->0, 2->0) 3x 0 gibts 1 Fkt. (0->0, 1->0, 2->0) jetzt hätte ich ja jeweils für n=1 und k=0 => 1 Fkt. k=2 => 3 Fkt.... wie oben beschrieben soweit so gut, aber nun hängt es, wie müsste ich es bei n=2 machen? (tut mir leid, aber ich stehe im mom echt auf dem Schlauch)
16.05.2012, 20:54	HAL 9000	Auf diesen Beitrag antworten »
Der Definitionsbereich umfastt genau $\begin{eqnarray} 3^n \end{eqnarray}$ Elemente. Nun sollen genau $\begin{eqnarray} k \end{eqnarray}$ davon auf den Funktionswert 0 abgebildet werden, der Rest dann auf 1 ... eine einfache kombinatorische Fragestellung.
Anzeige

17.05.2012, 14:39	stromertle	Auf diesen Beitrag antworten »
okay danke, das habe ich (glaube ich) nun verstanden... dabei hab ich nun ein urnenmodell mit $\begin{eqnarray} 3^n \end{eqnarray}$ Kugeln und wähle k-mal die 0 aus $\begin{eqnarray} $\Rightarrow \frac{3^n!}{k!(3^n-k)!} \end{eqnarray}$ natürlich zieht man die Kugeln ohne zurücklegen und die Reihenfolge müsste auch keine Rolle spielen, da ich nicht innerhalb der schwarzen Kugeln unterscheide... stimmt das soweit? Danke für eure Hilfe!
17.05.2012, 14:41	HAL 9000	Auf diesen Beitrag antworten »
Genau. Wobei man es durchaus auch in der Darstellung $\begin{eqnarray} \binom{3^n}{k} \end{eqnarray}$ als Binomialkoeffizient belassen kann.
17.05.2012, 16:36	stromertle	Auf diesen Beitrag antworten »
Danke und nun das nächste problem >.< Wie viele Funktionen $\begin{eqnarray} $f:\{0,1\}^n \rightarrow \{0,1,2\}$ \end{eqnarray}$ gibt es, bei denen der Funktionswert 0 genau k-mal vorkommt? Nun besitze ich $\begin{eqnarray} $2^n$ \end{eqnarray}$ Elemente, die k-mal auf 0 abgebildet werden und der Rest wird entweder auf 1 oder auf 2 oder auf 1 && 2 abgebildet. Für n=1 und k = 1 habe ich 4 Möglichkeiten k = 2 habe ich 1 Möglichkeit k = 0 habe ich wieder 4 Möglichkeiten
17.05.2012, 17:12	Math1986	Auf diesen Beitrag antworten »
Überleg dir zunächst mal, wie viele Möglichkeiten es gibt, mit den $\begin{eqnarray} 2^n \end{eqnarray}$ Elementen k-mal die 0 zu treffen, und wie viele Möglichkeiten es dann noch gibt, die verbleibenden Elemente auf $\begin{eqnarray} \{1,2\} \end{eqnarray}$ abzubilden.
17.05.2012, 18:31	stromertle	Auf diesen Beitrag antworten »
Danke für die Hilfe! das müsste ja dann $\begin{eqnarray} $\frac{2^n!}{k!(2^n-k)!} 2^{2^n-k}$ \end{eqnarray}$ sein, der vordere Teil beschreibt, wo überall k-mal die 0 auftaucht und der hintere teil ist dann wie bei binärzahlen $\begin{eqnarray} $2^{anzahl verbliebener stellen} \end{eqnarray*}$
17.05.2012, 18:37	HAL 9000	Auf diesen Beitrag antworten »
Ja, ist richtig.
17.05.2012, 20:59	stromertle	Auf diesen Beitrag antworten »
so nun die letzte Aufgabe, die mir ein bisschen Kopfzerbrechen bereitet: Wie viele Funktionen $\begin{eqnarray} $f:\{0,1,2\}^n \rightarrow \{0,1,2\} \end{eqnarray}$ gibt es, bei denen die Funktionswere 0,1 und 2 genau gleich oft vorkommt? man könnte ja $\begin{eqnarray} $\frac{3^{n}}{3^{n-1}!(3^n-3^{n-1}} \end{eqnarray}$ berechnen, aber damit hätte ich es ja lediglich für eine ziffer, ohne dass die andern beiden untereinander vertauscht werden...
17.05.2012, 21:10	Math1986	Auf diesen Beitrag antworten »
Ist doch das selbe Verfahren wie in der ersten: Wie viele Elemente musst du denn auf jeden Funktionswert abbilden, wenn jeder gleich oft getroffen werden muss? Danach ist es nur noch Auswählen von Elementen..
17.05.2012, 21:18	stromertle	Auf diesen Beitrag antworten »
ah ok dankeschön... es ist auch bisschen spät und so langsam setzts richtig aus naja nochmal danke für eure tolle hilfe! schönes wochenende

Neue Frage »

Antworten »

Kombinatorik Anzahl Funktionen

Verwandte Themen