Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Boolesche Matrizen zählen
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich * Boolesche Matrizen zählen
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1508
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-26


Es sei \(A=[a_{ij}]\) eine \(n\!\times\!n\,\)- Matrix mit \(a_{ij}\in\{T,F\}\);   der Einfachheit halber sei erst einmal \(n=3\) gesetzt. Insgesamt gibt es ja \(2^{n\cdot n}\) solche boolesche Matrizen, aber

(1)
wieviele davon haben in jeder Zeile mindestens ein \(T\) und in jeder Spalte mindestens ein \(F\) ?
(2)
wieviele davon haben in jeder Zeile oder Spalte mindestens ein \(T\) als auch mindestens ein \(F\) ?

Ihr dürft die Lösungen \(b_1(n)\) und \(b_2(n)\) direkt hier posten, aber bitte verdeckt.


Natürlich kann man die Anzahl der Matrizen bis zu \(n\le4\) vom Rechner durchzählen lassen, aber für \(n=3\) geht das mit Geduld und Geschick auch von Hand. Falls ich mich nicht verzählt habe, hat (1) eine Lösung der Form \(b_1(3)=6p\)  und (2) die Lösung $b_2$(3)=4p,  wobei \(p\) eine  und dieselbe  Primzahl ist, welche ihr herausfinden dürft.

Leider habe ich keinerlei Formel für den Allgemeinfall, und auch den Fall \(n=4\) nicht durchrechnen lassen. Klar scheint mir nur, dass (a) die Funktionen \(b_i(n)\) nur gerade Werte annehmen, und (b) die Funktionen \(b_i(n)/2^{n\cdot n}\) mit  \(n\) monoton ansteigen und gegen 1 konvergieren.




-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1823
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-24

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
2020-06-26 00:43 - Goswin im Themenstart schreibt:
Klar scheint mir nur, dass (a) die Funktionen \(b_i(n)\) nur gerade Werte annehmen, und (b) die Funktionen \(b_i(n)/2^{n\cdot n}\) mit  \(n\) monoton ansteigen und gegen 1 konvergieren.
Das stimmt nicht ganz. Jedenfalls am Anfang: $b_1(0)=1$ und $b_1(1)=0$.


Ich habe mal brutal zählen lassen. Die Werte von $b_1$ bis zum Argument 5 sind $$1,0,2,174,35714,23703870.$$

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1508
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-08-26


@tactac:

Deine Computerberechnungen für \(b_1(3),b_1(4),b_1(5)\) dürften korrekt sein, da sie mit meiner hand-durchgeführten Berechnung von \(b_1(3)\) überqeinstimmen.

Und sie sind sehr interessant, da sie andeuten, dass \[(2^{n-1}\!-\!1)\,\big|\,b_1(n)\] für alle \(n\ge2\) gilt. So etwas zu beweisen wird freilich nicht unbedingt einfach sein.

Ich schlage vor, dass wir ab nun alle Ergebnisse außer \(b_1(3)\) öffentlich posten, da die Aufgabe schwer genug ist und sich die allgemeine Beteiligung in Grenzen hält.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1823
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-08-26

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
Man könnte $b_1(n)$ mit Hilfe einer Funktion
$$f\colon \mathcal P[n] \to \mathcal M(\mathcal P[n])$$ berechnen, die eine Menge von Spaltenindizes entgegennimmt, und eine Multimenge von Mengen von Spaltenindizes zurückgibt. Die Mengen von Spaltenindizes geben an, in welchen Spalten schon ein F steht. $f$ generiert sozusagen eine nächste Zeile (bzw. alle Möglichkeiten, eine nächste Zeile zu generieren), wobei immer mindestens ein $T$ pro Zeile vorhanden sein muss, und gibt zurück, welche Spalten mit der jeweils neuen Zeile denn danach ein F haben. Für jede solche Ergebnis-Spaltenmenge gibt es u.U. mehrere Zeilen, die zu ihr führen. Daher geben wir eine Multimenge zurück, um die Vielfachheiten zu zählen.
Wir können $f$ dann erweitern zu einem linearen $f^*\colon \mathcal M(\mathcal P[n]) \to \mathcal M(\mathcal P[n])$ und das gewünschte Ergebnis ist die Vielfachheit von $[n]$ in der Multimenge $(f^*)^n(\{\emptyset\})$.
Vermutlich ist es darüberhinaus so, dass wir gar nicht mit den Mengen aus $\mathcal P[n]$ rechnen müssen, sondern ihre Kardinalitäten genug Information beinhalten. Müsste man sich mal genau überlegen.
Dies entspräche dann jedenfalls einer Funktion $g\colon [n+1]\to \mathcal M[n+1]$ bzw. $g^*\colon \mathcal M[n+1]\to \mathcal M[n+1]$ und $b_1(n)$ wäre die Vielfachheit von $n$ in der Multimenge $(g^*)^n(\{0\})$.
$g$ bzw. $g^*$ wären dann auch durch eine $(n+1)\times (n+1)$-Matrix kodierbar, an der man vielleicht 'was nettes sieht.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2370
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-08-26

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Werte von $b_1(n)$ für $0\leq n \leq 10$:

$n$ $b_1(n)$
 0 1
 1 0
 2 2
 3 174
 4 35714
 5 23703870
 6 56327527682
 7 502801766909694
 8 17309462621916229634
 9 2333510107754475674412030
10 1243000319907958180364838481922


Rekursive Berechnung mit dynamischer Programmierung:

Wir ordnen jeder Zeile $i$ einer Matrix $A$ die Menge $S_i$ der Spaltenindizes $j$ zu, an denen $a_{ij} = T$.

Damit in jeder Zeile von $A$ mindestens ein $T$ steht, muss $S_i\not=\emptyset$ für alle $i\in \{1,\ldots, n\} =: [n]$ gelten.

Damit in jeder Spalte mindestens ein $F$ steht, muss $S_1\cap \ldots \cap S_n = \emptyset $ gelten.

Definiere jetzt für $m\geq 1$ und $0\leq k \leq n$:
$$ a_{mk}:= \left|\left\{(S_1,\ldots, S_m)\in \left(\mathcal P([n])\setminus \emptyset\right)^m \,\middle \vert\, k =|\bigcap_{i=1}^m S_i| \right\}\right|.$$
Es gilt dann $b_1(n) = a_{n0}$.

Die $a_{mk}$ kann man rekursiv berechnen:
$a_{1,0} = 0$ und $a_{1k} = \binom nk $ für $k\geq 1$.

Es gilt
$$a_{m+1,0} = \sum_{l=0}^n a_{ml} (2^{n-l}-1)$$ und für $k\geq 1$ gilt:
$$a_{m+1,k} = \sum_{l=k}^n a_{ml}\binom lk 2^{n-l}.$$
Begründung:
Sei $(S_1,\ldots, S_m)\in \left(\mathcal P([n])\setminus \emptyset\right)^m $ mit $ l =|\bigcap_{i=1}^m S_i|$.

Um ein $S_{m+1}\in \mathcal P([n])\setminus \emptyset$ mit $\bigcap_{i=1}^{m+1} S_i = \emptyset$ anzugeben, muss man eine beliebige nichtleere Teilmenge von $[n]\setminus \bigcap_{i=1}^m S_i$ angeben, wofür es $2^{n-l}-1$ Möglichkeiten gibt.

Will man hingegen ein $S_{m+1}\in \mathcal P([n])\setminus \emptyset$ mit $|\bigcap_{i=1}^{m+1} S_i |=k \geq 1$ haben, so muss man $k$ Elemente aus $\bigcap_{i=1}^{m} S_i$ wählen (diese entsprechen dem Schnitt von $S_{m+1}$ mit $\bigcap_{i=1}^{m} S_i$) und eine beliebige Teilmenge aus dem Komplement von  $\bigcap_{i=1}^{m} S_i $ (entspricht den Elementen von $S_i$, die nicht in $\bigcap_{i=1}^{m+1} S_i$ liegen), wofür es $\binom lk 2^{n-l}$ Möglichkeiten gibt.

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wrdlprmpfd
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 24.08.2018
Mitteilungen: 8
Aus: Frankfurt am Main
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-08-26




Ich hatte mich auch mit dem Thema etwas beschäftigt und habe folgende Formel für $b_1(n)$ ermittelt:

$b_1(n)$ = -(2^n)^n + 2*(2^n-1)^n$

Das ergibt dieselben Werte wie die von Nuramon in Beitrag 4 errechneten.


Und für für $b_2(n)$ habe ich:

$(2^n)^n  -2 \cdot (2^n-1)^n  +2 \cdot (2^n-2)^n +2 \cdot  \sum_{r=1}^{n-1} (-1)^{r} \cdot \binom {n} {r} \cdot (2^{n-r}-1)^{n}$


Ich habe leider nur etwas unausgereifte Begründungen für die Formeln. Für $b_1(n)$ könnte ich aber wahrscheinlich bis morgen etwas fundierteres liefern.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1823
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-08-26

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
Ich habe meinen Plan mal präzisiert und durchgeführt. (Und ja, die Kardinalitäten reichen aus.)

Z.B.
$b_1(4) =
\begin{pmatrix}0&0&0&0&1\end{pmatrix}
\begin{pmatrix}
1&0&0&0&0 \\
4&2&0&0&0 \\
6&6&4&0&0 \\
4&6&8&8&0 \\
0&1&3&7&15
\end{pmatrix}^4
\begin{pmatrix}1\\0\\0\\0\\0\end{pmatrix}
= 35714$

Die zu potenzierende Matrix ergibt sich aus

$$g_n(k) = \sum_{i=0}^k \sum_{j=0}^{n-i-1} {k\choose i}{n-k\choose j} e_{k+j}.$$
EDIT: "optimierte" Formel:
$$g_n(k) = (2^k-1)e_n + 2^k\sum_{j=0}^{n-k-1}{n-k \choose j}e_{k+j}.$$


Die Werte von Nuramon kann ich damit bestätigen, und

$$b_1(20) = 2582151373963858678314630586820976731030691960562476760691062904894540807830195051358968528956539623348609347863678287874.$$
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2370
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-08-26

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Tactacs Wert von $b_1(20)$ kann ich bestätigen.

Und wrdlprmpfds Formel für $b_1(n)$ scheint auch zu stimmen. Da bin ich sehr auf den Beweis gespannt.

Mein Verfahren lässt sich denke ich auch für die Berechnung von $b_2(n)$ anpassen. Das muss ich mir aber noch genauer ansehen.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2370
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-08-26

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Vielleicht noch eine Anmerkung zum Unterschied zwischen Tactacs und meinem Ansatz:
Tactacs Ansatz beruht darauf zu einem gegebenen Typ von booleschen $m\times n$-Matrizen alle Typen von $m+1 \times n$-Matrizen zu finden, die man durch Hinzufügen einer weiteren Zeile erhalten kann.
Mein Ansatz beruht darauf für einem gegebenen Typ von $m+1\times n$-Matrizen zu untersuchen, wie viele  Möglichkeiten es gibt $m\times n$-Matrizen zu der $m+1\times n$-Matrix zu ergänzen.

Wenn meine Überlegungen (und meine Implementierung) richtig sind, dann erhalte ich folgende Werte für $b_2(n)$ für $0\leq n\leq 10$:

$n$ $b_2(n)$
0 1
1 0
2 2
3 102
4 22874
5 17633670
6 46959933962
7 451575174961302
8 16271255119687320314
9 2253375946574190518740230
10 1219041140314101911449662059402

Die Behauptung aus dem Themenstart, nach der $b_1(3)/6 = b_2(3)/4$ gelten soll, kann ich also nicht bestätigen.
Meine Berechnungen liefern die gleichen Ergebnisse wie wrdlprmpfds erstaunliche Formel für $b_2(n)$.

Herleitung meiner Werte
Definiere $a_{m,t,f}$ als die Anzahl der booleschen $m\times n$-Matrizen, bei denen
- in jeder Zeile mindestens ein F und mindestens ein T vorkommen
- in genau $t$ Spalten nur T's und in genau $f$ Spalten nur F's vorkommen. Nenne Matrizen, die diese beiden Bedingungen erfüllen $t,f$-Matrizen.

Es gilt dann insbesondere $b_2(n) = a_{n,0,0}$.

Für $m=1$ gilt
$$ a_{m,t,f} = \begin{cases} \binom nt, &\text{falls } t+f = n, t\geq 1 \text{ und } f\geq 1\\
0, &\text{sonst}\end{cases}.$$
Außerdem gilt die Rekursion
$$ a_{m+1,t,f} = \sum_{\tau = t}^n \sum_{\phi  =f}^n a_{m,\tau,\phi}\binom\tau t\binom \phi f \left(2^{n-\tau-\phi}-  1_{t+\phi-f = 0} -  1_{\tau-t+f = 0}\right),$$ wobei $1_{A}$ gleich $1$ oder $0$ ist, je nachdem ob $A$ wahr ist oder nicht.

Begründung:
Die oberen $m$ Zeilen einer $m+1\times n$ $t,f$- Matrix bilden eine $\tau,\phi$-Matrix mit $\tau\geq t$ und $\phi \geq f$.
Um eine $\tau,\phi$-Matrix durch eine neue Zeile zu einer $t,f$-Matrix zu ergänzen, müssen insbesondere in der neuen Zeile in genau $t$ der $\tau$ $T$-Spalten ein $T$ und in den restlichen $\tau -t$ $T$-Spalten ein $F$ stehen. Analog müssen in genau $f$ der $\phi$ $F$-Spalten ein $F$ und in den restlichen $\phi-f$ $F$-Spalten ein $T$ stehen.

Für die Ergänzung in den $T$- bzw. $F$-Spalten gibt es also jeweils $\binom \tau t$ bzw. $\binom \phi f$ Möglichkeiten.
Die Einträge in den restlichen $n-\tau-\phi$ Spalten können beliebig ergänzt werden ($2^{n-\tau-\phi}$ Möglichkeiten), so lange darauf geachtet wird, dass in der Zeile insgesamt mindestens ein $T$ und ein $F$ steht.


Tactacs Ansatz müsste sich auch auf $b_2(n)$ erweitern lassen. Man hat dann vermutlich Basisvektoren der Form $e_{t,f}$.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wrdlprmpfd
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 24.08.2018
Mitteilungen: 8
Aus: Frankfurt am Main
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-08-26




Hier meine Überlegungen zur Ableitung der Formel für $b_1(n)$, die nur elementare kombinatorische Tatsachen benutzen:

Ich bezeichne mit $\mathcal{A}$ die Menge der Matrizen, die die Bedingung der Teilaufgabe 1 erfüllen. Es soll nun deren  Mächtigkeit $\vert \mathcal{A} \vert$ bestimmt werden.

Die Idee ist, eine $\mathcal{A}$ umfassende Menge $\mathcal{M}$ zu finden, deren Mächtigkeit einfach zu berechnen ist, und aus der man geeignete Matrizen weglässt, um wieder $\mathcal{A}$ zu erhalten. Die Anzahl der weggelassenen Matrizen lässt sich dann (hoffentlich) auch relativ einfach berechnen.

Abweichend von der ursprünglichen Fragestellung benutze ich die Werte $0, 1$ anstatt $F, T$.

Die Matrizen aus $\mathcal{M}$ werden durch Nebeinanderstellen von Spaltenvektoren gebildet, die der Spaltenbedingung entsprechen, also mindestens eine $0$ zu enthalten. Nun gibt es $2^n$ voneinander verschiedene Spaltenvektoren, von denen nur einer - nämlich der Vektor, bei dem alle Komponenten $1$ sind -, nicht der Bedingung der Aufgabenstellung entspricht. D.h. man kann auf einen Pool von $2^n-1$ Spaltenvektoren zur Bildung der Matrizen aus $\mathcal{M}$ zurückgreifen. Da es $n$ Spalten gibt, gilt

\[\begin{equation}
\begin{aligned}
\vert \mathcal{M} \vert = (2^n-1)^n
\end{aligned}
\end{equation}
 \]  

Bei dieser Konstruktion ist nicht sichergestellt, dass die Zeilenvektoren der so erzeugten Matrizen mindestens eine $1$ enthalten, d.h. die Zeilenvektoren bestehend nur aus $0$-Komponenten "stören".

Die Anzahl der Matrizen  $\mathcal{S}$ mit störenden Zeilenvektoren wird nun berechnet.

Die Anzahl der Null-Zeilenvektoren bei einer Matrix aus $\mathcal{S}$ kann von 1 bis n laufen.

Bei genau einem Null-Zeilenvektor in irgendeiner Zeile gibt es genau $(2^n-1)^{n-1}$ verschiedene Möglichkeiten, diesen mit anderen Zeilenvektoren zu kombinieren, welche selbst kein Null-Zeilenvektor sind (das Argument ist praktisch dasselbe welches zu Formel (1) geführt hat). Bei $\binom{n}{1}$ verschiedenen Möglichkeiten den Nullvektor zu platzieren, gibt es insgesamt $\binom{n}{1}  \cdot (2^n-1)^{n-1}$ Möglichkeiten für Matrizen mit genau einem Null-Zeilenvektor. Diese Menge wird mit $\mathcal{S}_1$ bezeichnet:


$$\vert \mathcal{S}_1 \vert = \binom{n}{1} \cdot (2^n-1)^{n-1}$$

Bei genau zwei Null-Zeilenvektoren in irgendwelchen Zeilen gibt es dann $(2^n-1)^{n-2}$  verschiedene Möglichkeiten, diese mit anderen Zeilen zu kombinieren, welche selbst kein Null-Zeilenvektor sind. Bei $\binom{n}{2}$ verschiedenen Möglichkeiten die zwei Nullvektoren zu platzieren, ergeben sich hier $\binom{n}{2} \cdot (2^n-1)^{n-2}$ Möglichkeiten. Diese Menge wird mit $\mathcal{S}_2$ bezeichnet:


$$\vert \mathcal{S}_2 \vert = \binom{n}{2} \cdot(2^n-1)^{n-2}$$

Diese Argumentationskette wird fortgeführt, bis man genau $n$ Null-Zeilenvektoren erreicht. Für diese gilt dann entsprechend $\binom{n}{n} \cdot (2^n-1)^{n-n}$.

$$\vert \mathcal{S}_n \vert = \binom{n}{n} \cdot (2^n-1)^{n-n}$$

Offensichtlich gilt


$$\mathcal{S} = \bigcup \limits_{k=1}^{n} \mathcal{S}_i$$

Die Mengen $\mathcal{S}_i$ sind paarweise disjunkt, da sie Matrizen mit unterschiedlicher Anzahl von Null-Zeilenvektoren enthalten. Damit gilt dann auch



\[\begin{equation}
\begin{aligned}
\vert \mathcal{S} \vert &= \vert \bigcup \limits_{k=1}^{n} \mathcal{S}_i \vert = \sum_{k=1}^n \vert \mathcal{S}_i \vert \nonumber \\
 & = \sum_{k=1}^n  \binom{n}{k}  \cdot (2^n-1)^{n-k} = \sum_{k=0}^n \binom{n}{k}  \cdot (2^n-1)^{n-k} - (2^n-1)^n  \nonumber \\
 & = [(2^n -1) +1]^n - (2^n-1)^n = (2^n)^n - (2^n-1)^n  
\end{aligned}
\end{equation}
 \]
Es fehlt jetzt noch der Nachweis, dass


$$\mathcal{A} = \mathcal{M} \setminus \mathcal {S}$$

Das ist aber eigentlich klar: $\mathcal{M}$ enthält alle Matrizen, die der Spaltenbedingung der Aufgabenstellung genügen. Aus denen werden nun alle Matrizen entfernt, die nicht die Zeilenbedingung erfüllen. Die verbleibenden erfüllen sowohl die Zeilen- als auch die Spaltenbedingung. Damit gilt


$$\mathcal{M} \setminus \mathcal {S} \subset \mathcal{A}$$

Nehmen wir nun eine Matrix aus $\mathcal{A}$. Dann ist diese sicherlich auch in $\mathcal{M}$. Sie kann nicht in $\mathcal {S}$ liegen, da sie keine Null-Zeilenvektoren enthält, also:

$$\mathcal{A}  \subset  \mathcal{M} \setminus \mathcal {S}$$

Damit haben wir:

\[\begin{equation}
\begin{aligned}
\vert \mathcal{A} \vert = \vert \mathcal{M} \vert - \vert \mathcal{S} \vert
\end{aligned}
\end{equation} \]
Mit (3), (1) und (2) ergibt sich somit:

\[\begin{equation*}
\begin{aligned}
\vert \mathcal{A} \vert & = (2^n-1)^n  - [ (2^n)^n - (2^n-1)^n ]
 &= -(2^n)^n + 2(2^n-1)^n \nonumber
\end{aligned}
\end{equation*} \]





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1508
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-08-27


Ich bin schwer beeindruckt von den ausführlichen Ergebnissen. (Aber was ist mit \(\cal P(n)\) gemeint?)

Dank der eleganten Formel von 'wrd...d' ist jetzt auch klar, dass  \((2^{\,n-1}\!-\!1)\,\big|\,b_1(n)\)  für alle \(n\ge2\) gilt !


(Ich schreibe "%" für "modulo")

\(
\big[~ b_1(n)/2 ~\big]
~\%(2^{\,n-1}\!\!-\!1) ~=~

\Big[ (2^n-1)^n - 2^{\,n\cdot n-1} \Big]
~\%(2^{\,n-1}\!\!-\!1)\\ \qquad~=~

\Big[ \big(2(2^{n-1}-1)+1\big)^n
- \big( (2^{n-1}-1)+1 \big)^{n+1} \Big]
~\%(2^{\,n-1}\!\!-\!1)\\ \qquad~=~

\Big[ 1^n-1^{n+1} \Big]
~\%(2^{\,n-1}\!\!-\!1)\\[9pt] \qquad~=~

0~\%(2^{\,n-1}\!\!-\!1)
\)


Das ist insofern erstaunlich, als dass es keine (offensichtliche) Weise gibt, die \(b_1(n)\) Matrizen in zusammengehörige \((2^{\,n-1}\!\!-\!1)\)-Gruppen einzuteilen; über Permutationen geht das (anscheinend) nicht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1823
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-08-27

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
2020-08-27 11:08 - Goswin in Beitrag No. 10 schreibt:
(Aber was ist mit \(\cal P(n)\) gemeint?)
In meinem Text steht $\mathcal PX$ für die Potenzmenge von $X$, wobei $X$ irgendeine Menge ist, und für natürliche Zahlen $n$ steht $[n]$ für die Menge $\{0,\dotsc,n-1\}$. $\mathcal Pn$ kommt nicht vor.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2370
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-08-27

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Tactacs Bezeichnung $[n]:=\{0,1,\ldots, n-1\}$ ist glaube ich gebräuchlicher, aber in meinem Beitrag No.4 habe ich $[n]:=\{1,\ldots, n\}$ verwendet. (Ich hatte das aber auch explizit dazugeschrieben. Spielt hier aber eigentlich auch keine Rolle, solange $[n]$ eine Menge mit $n$ Elementen ist.)
$\mathcal P$ steht auch bei mir für den Potenzmengenoperator.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]