Bedingte Kombinatorik

02.03.2016, 14:07

Alive-and-well

Bedingte Kombinatorik

Ich habe das folgende Problem:

"Gesucht wird die Anzahl aller 4-stelligen Zahlen, allerdings darf die Summe von 2 belibigen Ziffern nicht 5 sein"

Beispiele:
1111 ist OK
1233 nicht nicht OK da 2+3 = 5

Zu meinen Überlegungen:
Gegeben ist A={1,2,3,4} die möglichen Zahlen die genutzt werden können.

Für die erste ziffer ist die Wahl einfach, es gibt 4 Möglichkeiten. Zum Beispiel wird "1" gewähl, daraus folgt das aus A die Zahl "4" entfernt werden muss. Also A={1,2,3}.

Für die zweite Ziffer ist die Whal auch noch einfach es gibt 3 Möglichkeiten (Bis jetzt also 4*3 Kombinationen). Allerdings kann jetzt entwerder wieder die Zahl "1" kommen, was zur folge hat das nichts aus A gestrichen wird. Es kann aber auch "2" bzw "3" gewählt werden was eine verkleinerung von A zur folge hätte.

Für die dritte Ziffer gibt es also entwerder 2 oder 3 Möglichkeiten. An dem Punkt komme ich nicht weiter.

Gibt es eine (allgemeine) Möglichkeit ein solches Problem zu berechen, ohen alle Kombinationen erzeugen zu müssen und diese dann zu zählen?

02.03.2016, 14:21

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Alive-and-well
Gegeben ist A={1,2,3,4} die möglichen Zahlen die genutzt werden können.

Wenn ich das richtig verstehe, gehört diese Bedingung mit zur Aufgabenstellung, nicht nur zu den Überlegungen!!! Bei

Zitat:

Original von Alive-and-well
Gesucht wird die Anzahl aller 4-stelligen Zahlen, allerdings darf die Summe von 2 belibigen Ziffern nicht 5 sein

würde ich ansonsten von der vollen Dezimalziffernmenge 0..9 ausgehen, abgesehen von der führenden Ziffer, die nicht 0 sein darf. Augenzwinkern

Also gut, nur Ziffern 1..4 stehen zur Wahl. Dann würde ich so rangehen:

1 und 4 dürfen nicht gleichzeitig drin sein.
2 und 3 dürfen nicht gleichzeitig drin sein.

Damit besteht die Zahl nur aus maximal zwei verschiedenen Ziffern:

a) Genau eine Ziffer: Offenbar sind das die vier Möglichkeiten 1111, 2222, 3333, 4444.

b) Genau zwei verschiedene Ziffern, davon eine (x) aus {1,4} und die andere (y) aus {2,3}, das ergibt $\begin{align*} 2^2=4 \end{align*}$ Möglichkeiten für die Ziffernwahl. An jeder Position hat man nun genau zwei Möglichkeiten zur Wahl, x oder y. Das ergibt $\begin{align*} 2^4=16 \end{align*}$ Möglichkeiten, allerdings dürfen wir die Varianten xxxx und yyyy nicht zählen (das wurde schon in a) getan), also nur 14.

Macht summa summmarum $\begin{align*} 4 + 4\cdot 14 = 60 \end{align*}$ mögliche Zahlen.

02.03.2016, 14:46

Alive-and-well

Auf diesen Beitrag antworten »

Vielen Dank für die schnelle Hilfe!

Mal sehen, ob ich es richtig verstanden habe:

gehen wir von eienr 10 stelligen Zahl aus und A ={0,...9} (Führende 0en sind erlaubt)

Bedingugn zwei Ziffern addiert dürfen nicht 10 sein.

so ergibt sich sich die folgendne Töpfe:

X_1 = {0,9}
X_2 = {1,8}
X_3 = {2,7}
X_4 = {3,6}
X_5 = {4,5}

Nun wird aus jedem Topf eine Zahl ausgefählt $\begin{eqnarray*} 2^5=32 \end{eqnarray*}$ Varianten. Nun ergeben sich $\begin{eqnarray*} 5^{10} \end{eqnarray*}$ Variationen um zahlen zu bilden.

Insgesamt hat man $\begin{eqnarray*} 2^5 * 5^{10} \end{eqnarray*}$ Varianten. Allerdings müssen noch die doppelten entfernt werden. Dies müssten hier 10 sein also folgt: $\begin{eqnarray*} 2^5 * 5^{10} - 10 = 312.499.990 \end{eqnarray*}$

wäre das so korrekt?

02.03.2016, 14:53

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Alive-and-well
so ergibt sich sich die folgendne Töpfe:

X_1 = {0,9}
X_2 = {1,8}
X_3 = {2,7}
X_4 = {3,6}
X_5 = {4,5}

Diese Töpfe passen zur Summe 9, nicht zur Summe 10. unglücklich

Auch sonst passt deine Analogie an mehreren Stellen nicht - weil du nur rein mechanisch überträgst statt nachzudenken, ob diese Übertragung auch inhaltlich statthaft ist. unglücklich

02.03.2016, 15:22

Alive-and-well

Auf diesen Beitrag antworten »

Töpfe:
X_1 = {0,9}
X_2 = {1,8}
X_3 = {2,7}
X_4 = {3,6}
X_5 = {4,5}

Aus den Töpfen ergeben sich $\begin{eqnarray*} 2^5 \end{eqnarray*}$ mögliche Kombiantionen von möglichen Ziffern, die später genutzt werden können (das sollte richtig sein oder ?)

Mit diesen Ziffern lassen sich $\begin{eqnarray*} 5^{10} \end{eqnarray*}$ (10-stellige) Kombinationen bilden.

Bei der zusammenführung muss man daruf achten, dass doppelte weg fallen. Das sind hier
$\begin{eqnarray*} 4^{10} \end{eqnarray*}$ Kombinationen. $\begin{eqnarray*} 4^10 \end{eqnarray*}$ sollten alle dopplungen sein, wenn eine X_n gewählt wird aber nicht in der Zahl vorkommt.

Somit würde sich ergeben $\begin{eqnarray*} 2^5 *(5^{10}-4^{10}) \end{eqnarray*}$ dazu kommen noch die Fälle in denen nur eine zahl vokommen also $\begin{eqnarray*} 2^5 *(5^{10}-4^{10})+10 \end{eqnarray*}$

Ist das näher am Ergebniss dran?

02.03.2016, 15:35

HAL 9000

Auf diesen Beitrag antworten »

Du gehst jetzt also davon aus, dass Summe 9 (statt 10, wie oben noch stand) nicht statthaft ist? Das hättest du ruhig nochmal dazuschreiben bzw. bestätigen können. unglücklich

Angenommen, die Zahl besitzt genau $\begin{align*} k \end{align*}$ verschiedene Ziffern, dann wissen wir nach der Vorüberlegung, dass $\begin{align*} k\leq 5 \end{align*}$ ist.

Dann gibt es zunächst $\begin{align*} \binom{5}{k}\cdot 2^k \end{align*}$ Möglichkeiten der Ziffernwahl von $\begin{align*} k \end{align*}$ verschiedenen Ziffern aus {0,9}, {1,8}, {2,7}, {3,6}, {4,5}. Für jede mögliche solche Ziffernwahl haben wir dann gemäß Siebformel genau $\begin{align*} \sum_{j=0}^{k-1} (-1)^j \binom{k}{j} (k-j)^{10} \end{align*}$ verschiedene 10-stellige Zahlen, die alle diese Ziffern auch wirklich mindestens einmal enthalten. Die Antwort ist damit summa summarum

$\begin{align*} \sum_{k=1}^5 \binom{5}{k}\cdot 2^k \cdot \sum_{j=0}^{k-1} (-1)^j \binom{k}{j} (k-j)^{10} = \sum_{k=1}^5 \binom{5}{k}\cdot (-2)^k\cdot \sum_{i=1}^k (-1)^i \binom{k}{i} i^{10} = 233\,296\,890 \end{align*}$ .

02.03.2016, 15:59

Alive-and-well

Auf diesen Beitrag antworten »

Besten Dank!

02.03.2016, 16:08

HAL 9000

Auf diesen Beitrag antworten »

Mit Summe 10 ist es übrigens erheblich ekliger:

Da gibt es dann die Ziffer 5, die höchstens einmal drin sein darf, und die Ziffer 0 ohne jegliche Beschränkungen der Verwendung.

03.03.2016, 11:14

Alive-and-well

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Mit Summe 10 ist es übrigens erheblich ekliger:

Da gibt es dann die Ziffer 5, die höchstens einmal drin sein darf, und die Ziffer 0 ohne jegliche Beschränkungen der Verwendung.

Das ist mir auch aufgefallen.

Die Bestimmung der möglichen Kombinationen $\begin{align*} \binom{5}{k}\cdot 2^k \end{align*}$ passt dann nicht mehr.

Ich versuche das Problem mal etwas zu vereinfachen und zu erläutern wo ich nicht weiter komme.

Angenommen die Zahlen 9,8,7,6 sind (warum auch immer) verboten.
Also hat man zwei Arzen von Zahlen $\begin{eqnarray*} A = \{0,1,2,3\} \end{eqnarray*}$ , die beliebig vorkommen dürfen und $\begin{eqnarray*} B=\{4, 5\} \end{eqnarray*}$ von denen nur eine Zahl vorkommen darf.

Für den Fall $\begin{eqnarray*} k =1 \end{eqnarray*}$ (es wird also nur eine Zahl ausgewählt)
Offensichtlich gibt es 6 Kombinationen eine Ziffer zu wählen. (1, 2, 3, 4, 5 oder 6)
Die Berechnung gestaltet sich aber schwierig.
Im Vorangegangenen Beispiel hat Binomialkoeffizient die Anzahl der möglichen „Topf Kombinationen“ angegeben und $\begin{eqnarray*} 2^k \end{eqnarray*}$ die Anzahl der möglichen Kombinationen der Elemente der Töpfe.
Das gestaltet sich hier jetzt sehr schwierig (für mich). Selbst wenn ich aus A vier kleine Töpfe mache, weiß ich nicht wie ich die Anzahl der möglichen Kombinationen bestimmen kann.

Es wird wieder eine Zahl (aus 5 Möglichen) ausgewählt (also $\begin{align*} \binom{5}{1} \end{align*}$ )
Wenn jetzt Jeder Topf nur ein bzw. zwei Elemente hätte wäre es einfach 1^1 bzw. 2^1
Wenn ich 2^1 rechnen würde müsste ich die 4 überflüssigen (4 Töpfe haben nur ein Element) wieder abziehen.
Es würde sich ergeben $\begin{align*} \binom{5}{1} \cdot 2^1 - 4 \end{align*}$
Für den allgemeinen Fall (z.B. k =3) weiß ich aber nicht wie diese „-4“ bestimmen könnte.

Wenn man einmal die Anzahl der Kombinationen hat kann ich ja per Siebformel die Anzahl der 10stelligen Zahlen einfach bestimmen (oder?). Wobei k die Anzahl der unterschiedlichen Ziffern in der Zahl ist.

Sorry wenn alles etwas plump wirkt, aber ich hatte nie Kombinatorik in der Hochschule und bin mit dem Problem etwas überfordert unglücklich

03.03.2016, 12:07

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Alive-and-well
Angenommen die Zahlen 9,8,7,6 sind (warum auch immer) verboten.
Also hat man zwei Arzen von Zahlen $\begin{eqnarray*} A = \{0,1,2,3\} \end{eqnarray*}$ , die beliebig vorkommen dürfen und $\begin{eqnarray*} B=\{4, 5\} \end{eqnarray*}$ von denen nur eine Zahl vorkommen darf.

Betrachten wir wieder den Fall, dass die Zahl aus genau $\begin{align*} k \end{align*}$ verschiedenen Ziffern besteht, dann gibt es hinsichtlich der Ziffernauswahl hier zwei mögliche Fälle:

1.Fall: 4,5 sind nicht dabei

Da gibt es $\begin{align*} \binom{4}{k} \end{align*}$ Auswahlmöglichkeiten rein aus Menge A.

2.Fall: 4 oder 5 sind dabei

Da gibt es 2 Möglichkeiten für die Wahl von "4 oder 5" aus B, sowie $\begin{align*} \binom{4}{k-1} \end{align*}$ für die restlichen Ziffern aus A.

Macht summa summarum $\begin{align*} \binom{4}{k}+2\binom{4}{k-1} \end{align*}$ Varianten für die Ziffernwahl, und in jedem dieser Fälle wieder $\begin{align*} \sum_{j=0}^{k-1} (-1)^j \binom{k}{j} (k-j)^{10} \end{align*}$ Zahlen mit genau festgelegten $\begin{align*} k \end{align*}$ Ziffern.

EDIT: Alternativ geht die Berechnung der Ziffernauswahlmöglichkeiten auch so:

Man nimmt alle Auswahlmöglichkeiten von $\begin{align*} k \end{align*}$ aus $\begin{align*} \{0,1,2,3,4,5\} \end{align*}$ abzüglich der, die beide Ziffern 4,5 zugleich enthalten, d.h. $\begin{align*} \binom{6}{k}-\binom{4}{k-2} \end{align*}$ .

Tatsächlich gilt ja auch $\begin{align*} \binom{4}{k}+2\binom{4}{k-1} = \binom{6}{k}-\binom{4}{k-2} \end{align*}$ für alle $\begin{align*} k\geq 2 \end{align*}$ , und eigentlich auch für $\begin{align*} k=1 \end{align*}$ , sofern man mit einer erweiterten Definition des Binomialkoeffizienten $\begin{align*} \binom{4}{-1}=0 \end{align*}$ setzt.

03.03.2016, 14:08

Alive-and-well

Auf diesen Beitrag antworten »

Vielen Dank soweit ich versuche es noch einmal, ob ich es Verstanden habe.

Sei $\begin{eqnarray*} A=\{0,1\} \end{eqnarray*}$ und $\begin{eqnarray*} B_1=\{2,7\} \end{eqnarray*}$ , $\begin{eqnarray*} B_2=\{3,6\} \end{eqnarray*}$ und $\begin{eqnarray*} B_3=\{4,5\} \end{eqnarray*}$

Sei $\begin{eqnarray*} k \leq 5 \end{eqnarray*}$

Es gilt:
F1: (alle Ziffern kommen aus A)
$\begin{eqnarray*} \binom{2}{k} \end{eqnarray*}$

F2: (eine Ziffer kommt aus einem $\begin{eqnarray*} B_i \end{eqnarray*}$ der Rest aus A)
$\begin{eqnarray*} 3*2*\binom{2}{k-1} \end{eqnarray*}$
3 weil aus 3 $\begin{eqnarray*} B_i \end{eqnarray*}$ s gewählt werden kann.
2 weil aus zwei Zahlen in einem $\begin{eqnarray*} B_i \end{eqnarray*}$ vorkommen.

F3: (zwei Ziffern aus den $\begin{eqnarray*} B_i \end{eqnarray*}$ s der Rest aus A)
$\begin{eqnarray*} 3 * 2 * \binom{2}{k-2} \end{eqnarray*}$
(3) weil aus 3 2er Kombinationen $\begin{eqnarray*} B_i \end{eqnarray*}$ s gewählt werden kann. ((a,b )=(b,a).)
2 weil aus zwei Zahlen in einem $\begin{eqnarray*} B_i \end{eqnarray*}$ vorkommen.

F4: (drei Ziffern aus den $\begin{eqnarray*} B_i \end{eqnarray*}$ s der Rest aus A)
$\begin{eqnarray*} (1)*2*\binom{2}{k-3} \end{eqnarray*}$
(1) weil es eine 3er Kombination von $\begin{eqnarray*} B_i \end{eqnarray*}$ s gibt.
2 weil aus zwei Zahlen in einem $\begin{eqnarray*} B_i \end{eqnarray*}$ vorkommen.

Insgesamt also:
$\begin{eqnarray*} \binom{2}{k} + 3*2*\binom{2}{k-1} + 3 * 2 * \binom{2}{k-2} + (1)*2*\binom{2}{k-3} \end{eqnarray*}$

Allgemeiner Fall:
$\begin{eqnarray*} |B| := \cup_{i} B \end{eqnarray*}$

$\begin{eqnarray*} \binom{|A|}{k} + \sum_{i=0}^k \binom{|B|}{i} * 2 * \binom{|A|}{k-i} \end{eqnarray*}$

Passt das so?

03.03.2016, 14:29

HAL 9000

Auf diesen Beitrag antworten »

Wenn wir schon den "allgemeineren Fall" betrachten wollen, dann gleich von Start weg: Analogieübertragungen gehen ja öfter in die Hose, das muss ich nach dem Threadverlauf vielleicht nicht extra betonen.

Also gut, sagen wir es sind nichtnegative ganze Zahlen $\begin{align*} a,b \end{align*}$ gegeben mit $\begin{align*} |A|=a \end{align*}$ sowie $\begin{align*} b \end{align*}$ Zweiermengen $\begin{align*} B_1,\ldots,B_b \end{align*}$ , und man darf beliebig viele Ziffern aus $\begin{align*} A \end{align*}$ sowie aus jeder der Mengen $\begin{align*} B_j \end{align*}$ höchstens eine Ziffer wählen.

Für eine feste Anzahl $\begin{align*} k\leq a+b \end{align*}$ zu wählender Ziffern gibt es also die Kombinationen " $\begin{align*} k-i \end{align*}$ Ziffern aus $\begin{align*} A \end{align*}$ und $\begin{align*} i \end{align*}$ Ziffern aus $\begin{align*} i \end{align*}$ der Mengen $\begin{align*} B_1,\ldots,B_b \end{align*}$ ". Offenbar muss $\begin{align*} i \end{align*}$ verschiedene Bedingungen erfüllen, damit das überhaupt möglich ist, als da wären $\begin{align*} i\leq b,i\leq k, k-i\leq a,i\geq 0 \end{align*}$ . Dies berücksichtigend ergibt sich

$\begin{align*} \sum_{i=\max(k-a,0)}^{\min(b,k)} \binom{a}{k-i}\cdot \binom{b}{i}\cdot 2^i \end{align*}$ .

Neue Frage »

Antworten »

Bedingte Kombinatorik

Verwandte Themen