Binäre Matrix Kombinationen ohne Nullzeilen/spalten

Question

Aufgabe:

Eine m × n-Matrix ist gegeben bestehend aus m Zeilen und n Spalten mit einem Eintrag a_ij für alle i ∈ {1,...,m} und j ∈ {1,...,n}.
Gesucht ist die Anzahl a_n binärer (d.h. alle Einträge sind entweder 0 oder 1) 2 × n-Matrizen, die keine Nullzeile und keine Nullspalte enthalten.

(a) Berechnen Sie a_n für n = 1,2 und 3 an.
(b) Finden Sie eine Rekursionsformel für a_n+1 und begründen Sie Ihre Lösung.
(c) Finden Sie eine explizite Darstellung von a_n und begründen Sie Ihre Antwort.

Comments

ah schön zu sehen, dass ich nicht der einzige depp in koblenz bin, der es nicht geschnallt hat :D

Answer 1

Betrachten wir die möglichen Zeilen von a(j)_n

  n=1, klar

n=2	n=3	j=1..2^n-1
$\small a(j)_{n} \, := \, \left(\begin{array}{rr}0&1\\1&0\\1&1\\\end{array}\right)$	$\small a(j)_{n} \, := \, \left(\begin{array}{rrr}0&0&1\\0&1&0\\0&1&1\\1&0&0\\1&0&1\\1&1&0\\1&1&1\\\end{array}\right)$

Stelle a_2xn zusammen

$\small a_{2x2} \, := \, \left\{ \left\{ \left(\begin{array}{rr}0&1\\0&1\\\end{array}\right), \left(\begin{array}{rr}0&1\\1&0\\\end{array}\right), \left(\begin{array}{rr}0&1\\1&1\\\end{array}\right) \right\} , \left\{ \left(\begin{array}{rr}1&0\\0&1\\\end{array}\right), \left(\begin{array}{rr}1&0\\1&0\\\end{array}\right), \left(\begin{array}{rr}1&0\\1&1\\\end{array}\right) \right\} , \left\{ \left(\begin{array}{rr}1&1\\0&1\\\end{array}\right), \left(\begin{array}{rr}1&1\\1&0\\\end{array}\right), \left(\begin{array}{rr}1&1\\1&1\\\end{array}\right) \right\} \right\}$

$\small a_2= \sum{} \left(\begin{array}{rrr}0&1&1\\1&0&1\\1&1&1\\\end{array}\right)$

$\small a_3= \sum{}\left(\begin{array}{rrrrrrr}0&0&0&0&0&1&1\\0&0&0&0&1&0&1\\0&0&0&1&1&1&1\\0&0&1&0&0&0&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\1&1&1&1&1&1&1\\\end{array}\right)$

> Falsche Auflistung entfernt - update Zählmatrix

Ich hoffe ich hab das richtig zusammen geklöppelt...

Comments

Hast du noch eine Idee zu b) und c)?

---

Du hast eigentlich alles was Du brauchst:

Wo für stehen denn die Zeilen der Matrizen?

---

Mögliche Zeilen zum Kombinieren mit anderen Zeilen

---

Das hab ich Dir ja aufgeschrieben - das ist nix neues, aber lies die Tabelle genauer und bedenke, daß die Vorgabe eine binäre Matrix beschreibt...

Was hast Du denn bei a)?

---

n = 1 hat 3 Möglichkeiten

n = 2 hat 7 Möglichkeiten

n = 3 hat 19 Möglichkeiten

---

n = 1

$$\begin{pmatrix} 0\\1 \end{pmatrix}, \begin{pmatrix} 1\\0 \end{pmatrix}, \begin{pmatrix} 1\\1 \end{pmatrix}$$

n = 2

$\begin{pmatrix} 0 & 1\\1 & 0\end{pmatrix}$, $\begin{pmatrix} 1 & 0\\0 & 1\end{pmatrix}$,$\begin{pmatrix} 0 & 1\\1 & 1\end{pmatrix}$, $\begin{pmatrix} 1 & 0\\1 & 1\end{pmatrix}$,$\begin{pmatrix} 1 & 1\\0 & 1\end{pmatrix}$, $\begin{pmatrix} 1 & 1\\1 & 0\end{pmatrix}$, $\begin{pmatrix} 1 & 1\\1 & 1\end{pmatrix}$

---

Habe mir grade eine Formel angenähert:

$\frac{2^{k} - n!}{n}$

Wobei k = Anzahl Felder der Matrix

Damit komme ich auch auf meine auf meine Ergebnisse die ich oben aufgeführt habe.

Außer bei n = 3 kommt 19.3 raus statt glatt 19

Nur weiss ich nun nicht wie ich die Formel Rekursiv und in einer expliziten Darstellung  darstelle.

---

Da musst Du noch üben, was ist so schwierg daran die aufgeführte Matrizenanzahl abzuzählen?

m=Zeilen, n=Spalten (siehe Aufgabenstellung)

m=2, n=1  $a_{2x1} = \, \left\{ \left(\begin{array}{r}1\\1\\\end{array}\right) \right\} ⇒ \; a_1 = 1$

m=2, n=2 siehe oben $a_{2x2} ⇒ \left\{ 3,2,1 \right\} a_2= 6$

m=2, n=3 siehe oben $a_{2x3} ⇒ \left\{7,6,5,4,3,2,1 \right\} a_3= 28$

Übrigens m=2, n=4 $a_4=120$

Die Formel steht zur Hälfte bereits oben in der Tabelle und den Rest findest Du im Nachlass von Gauß...

---

Leider komme ich nicht auf die Rekursive Definition

---

Lass mal sehen, was Du jetzt hast.

Zur rekursiven Darstellung fällt mir nur ein die Differenz von a_n+1-a_n zu addieren...

ups, das mit üben gilt auch fürmich x entschuldige, aber ich hab überlesen, dass es auch keine 0 Spalten geben soll.

ich muss neu auszählen, meine Zählung oben passt nicht auf die Aufgabenstellung...

---

n = 1 hat 1 Möglichkeit

n = 2 hat 7 Möglichkeiten

n = 3 hat 19 Möglichkeiten

Wie oben schon mal nur habe ich n = 1 korrigiert

---

Korrektur: n = 3 hat 25 Möglichkeiten

---

Yep, jetzt hammers denke ich - wenn man die Zeilensummen einzeln auflistet

sieht a_n aus nach

$a_{n} \, := \, \sum_{k=1}^{n} \binom{n}{k} \cdot 2^{k} - 1$

 aber beweisen möcht ich das nicht ;-)

Ich hab in der Antwort die richtige Zählmatrix hinterlegt und die fehlerhafte rausgenommen!

 

Answer 2

Um An+1 rauszufinden muss man sich denken: was kann ich an ein element von An anhängen? Es gibt 3 Möglichkeiten: (1,0 ), (0,1),(1,1), also 3An wenn man alle zusammenaddiert. Zusätzlich kann man noch die beiden Matrizen mit nur Einserzeile und Nullzeile kann man jeweils mit 2 Möglichkeiten erweitern die Reihenfolge von 1 und 0 umgedreht und doppelt die 1. Nach Summenregel haben wir also bei An+1 = 3*An+2+2 = 3An+4.