Kombinatorik bei Binärelemente < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Für dieses Beispiel gilt: n = 3, m = 2
Erstellen Sie einen Auswahlvektor [mm] y_l [/mm] für den gilt:
[mm]$y_l$
\begin{align}
y_{l} \in \left\{0,1\right\}^{n} , \sum_{l} y_{l} =
\begin{bmatrix}
1 \\ \vdots \\ 1 \\
\end{bmatrix} , 1 \le l \le q, q \le m
\end{align}[/mm]
Bilde Sie nun alle Teilmengen [mm] Y_t [/mm] der Menge
[mm]$Y$
\begin{align}
Y = \left\{ y_{l} ; 1 \leq l \leq 2^{n} \right\}
\end{align}[/mm]
so, dass die Summe aller Vektoren jeder Teilmenge [mm] $Y_{t} [/mm] = [mm] \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$ [/mm] ergibt.
Dabei ist zu beachten, daß jede Teilmenge [mm] Y_t [/mm] höchstens $m$ Elemente besitzen darf. |
Folgenden Weg bin ich gegangen:
Ich habe den Y Vektor aufgebaut:
[mm]
$Y-vektor$
\begin{align}\label{YVektor}
Y &= \left\{y_{1}, \cdots , y_{8}\right\}; \\
\nonumber
y_{1} &= \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} ,
y_{2} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} ,
y_{3} = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} ,
y_{4} = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} ,\\
\nonumber
y_{5} &= \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} ,
y_{6} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} ,
y_{7} = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} ,
y_{8} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}
\end{align}
[/mm]
Dann habe ich die Teilmengen [mm] Y_t [/mm] mit m = 2 Elementen erstellt:
[mm]
$Teilmengen$
\begin{align}\label{YTeilmenge}
Y_{1} = \left\{ y_{1}, y_{8} \right\}\\
Y_{2} = \left\{ y_{2}, y_{7} \right\}\\
Y_{3} = \left\{ y_{3}, y_{6} \right\}\\
Y_{4} = \left\{ y_{4}, y_{5} \right\}
\end{align}
[/mm]
Nun meine Frage:
gibt es eine Formel oder Herleitung mit der ich:
a) die Anzahl Teilmengen berechnen
b) die Elemente generieren kann
Wenn m = 2 ist, erscheint mir die Lösung zu a) einfach: [mm] $\frac{2^n}{2}$
[/mm]
Erweitere ich m auf 3, dann gibt es in diesem Fall eine Kombination mehr $ [mm] Y_{5} [/mm] = [mm] \left\{ y_{2}, y_{3} , y_{5} \right\}$
[/mm]
Betrachte den Fall mit n = 4 und m = 2 ergeben sich wieder der einfache Lösungsweg mit [mm] $\frac{2^n}{2}$. [/mm] Und den 'spiegelbildlichen' Elementen: 1,16 ... 8,9.
Erweitere ich in diesem Fall m auf 3 erhalte ich durch raussuchen 6 zusätzliche Tripels.
Mir will nicht der rechte Ansatz gelingen hoffe aber, bei Euch jemanden zu finden, der gerade nicht den berühmten Balken vor der Stirn hat.
Zu b) fällt mir nur die Möglichkeit ein alle Elemente miteinander zu kombinieren die den Wert [mm] $2^n-1$ [/mm] ergeben.
Ich habe diese Frage in keinem Forum oder auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 So 13.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
