+3 Daumen
2,1k Aufrufe

Aufgabe:


Eine m × n-Matrix ist gegeben bestehend aus m Zeilen und n Spalten mit einem Eintrag aij für alle i ∈ {1,...,m} und j ∈ {1,...,n}.
Gesucht ist die Anzahl an 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 an für n = 1,2 und 3 an.
(b) Finden Sie eine Rekursionsformel für an+1 und begründen Sie Ihre Lösung.
(c) Finden Sie eine explizite Darstellung von an und begründen Sie Ihre Antwort.

Avatar von

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

2 Antworten

0 Daumen

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 a2xn 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...

Avatar von 21 k

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 an+1-an 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 an 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!

 

0 Daumen

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community