Kombination von Ziffern

19.09.2016, 23:25

3r47057h3n35

Kombination von Ziffern

Meine Frage:
Hallo,
ich habe eine Zahl mit drei Ziffern.
Die Erste Ziffer hat 2 Möglichkeiten [0-1] die Zweite hat 3 Möglichkeiten [0-2] und die Dritte hat 5 Möglichkeiten [0-4].
Nun möchte ich herausfinden wieviele Kombinationsmöglichkeiten es gibt:
1) mit Reihenfolge
2) ohne Reihenfolge.

Meine Ideen:
1. habe ich schnell gelöst. Es gibt 30 Möglichkeiten (2*3*5 = 30)
Bei 2. weiß ich momentan nicht weiter. Ohne Reihenfolge heißt in dem Fall das z.B. '103' dasselbe wie '013' ist. Wenn ich mich nicht irre müsste als Ergebnis 19 rauskommen (siehe unten). Würde aber gerne wissen wie man das ausrechnet.

1) [000]
2) [001][010][100]
3) [002][020]
4) [003]
5) [004]
6) [011][101][110]
7) [012][021][102][120]
8) [013][103]
9) [014][104]
10) [022]
11) [023]
12) [024]
13) [112][121]
14) [113]
15) [114]
16) [122]
17) [123]
18) [124]
19) [111]

19.09.2016, 23:43

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 3r47057h3n35
Wenn ich mich nicht irre müsste als Ergebnis 19 rauskommen (siehe unten). Würde aber gerne wissen wie man das ausrechnet.

Es gibt dafür keine fertige Formel, die ohne Fallunterscheidung auskommt - das "krumme" Ergebnis Primzahl 19 spricht da schon Bände.

Ein Kompromiss, nicht alles aufschreiben zu müssen, und die Fallunterscheidung "klein" zu halten könnte z.B. so aussehen:

Grundlage sind alle dreimaligen Auswahlen aus [0-2] mit Zurücklegen ohne Reihenfolge, davon gibt es $\begin{align*} \binom{3+3-1}{3} = 10 \end{align*}$ , davon müssen wir [222] weglassen, also nur noch 9 Varianten. Hinzukommen aber noch alle mit einer 3 oder einer 4, gepaart mit 00, 01, 02, 11 oder 12, das macht weitere $\begin{align*} 2\cdot 5=10 \end{align*}$ Varianten.

Klingt immer noch furchtbar, und so ist es auch. Augenzwinkern

20.09.2016, 01:49

3r47057h3n35

Auf diesen Beitrag antworten »

Ok. Vielen Dank für deine Antwort. Ich kam nicht einmal auf die Idee eine Fallunterscheidung zu machen, weil ich dachte, dass es dafür eine "einfache" Formel geben könnte, die ich nur vergessen habe.
Leuchtet mir jetzt ein. Weitere Probleme dieses Typs werde ich jetzt mit Fallunterscheidungen lösen.
Ist nicht so elegant aber für kleinere Ziffernmengen reicht es allemal Freude

20.09.2016, 10:20

HAL 9000

Auf diesen Beitrag antworten »

Das wäre mal ein eigenständiges interessantes Zählproblem: Man bestimme die Anzahl $\begin{align*} N(m_1,\ldots,m_n) \end{align*}$ aller aufsteigend geordneten $\begin{align*} n \end{align*}$ -Tupel $\begin{align*} (k_1,\ldots,k_n) \end{align*}$ mit $\begin{align*} k_i\in\{1,\ldots,m_i\} \end{align*}$ mit vorgegebenen ebenfalls aufsteigend geordneten $\begin{align*} m_1,\ldots,m_n \end{align*}$ , d.h. $\begin{align*} 1\leq m_1\leq \ldots \leq m_n \end{align*}$ .

Deins hier ist dann Spezialfall $\begin{align*} n=3,m_1=2,m_2=3,m_3=5 \end{align*}$ .

Ich erwarte nicht, eine explizite Formel für $\begin{align*} N(m_1,\ldots,m_n) \end{align*}$ zu bekommen - eine "moderat" handhabbare Rekursionsformel wäre schon ein schöner Erfolg. Augenzwinkern

16.10.2016, 00:58

3r47057h3n35

Auf diesen Beitrag antworten »

Ja. Hab mir eine Formel dafür überlegt.
$\begin{eqnarray*} N \end{eqnarray*}$ = Anzahl der Kombinationsmöglichkeiten
$\begin{eqnarray*} n \end{eqnarray*}$ = Anzahl der Ziffern
$\begin{eqnarray*} m_1,...,m_n \end{eqnarray*}$ = Möglichkeiten je Ziffer aufsteigend sortiert (und $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$ )
$\begin{eqnarray*} k_1,...,k_n \end{eqnarray*}$ = Zählindezes

$\begin{eqnarray*} <br /> N = \sum\limits_{k_1=1}^{m_1} (\sum\limits_{k_2=k_1}^{m_2} ( \left(...\right) (\sum\limits_{k_n=k_{n-1}}^{m_n} (1))\left(...\right) ))<br /> \end{eqnarray*}$

Die drei Punkte sollen beim ersten Mal weitere Summenzeichen darstellen und beim zweiten Mal die Klammern, die diese schließen.
Habe leider keinen Rechenweg für die Herleitung der Formel. Hab mir die einfach so gedacht, nachdem ich paar Stichproben/Beispiele
mit Zettel und Stift gemacht habe. Bin kein Mathematikstudent.

Für mein Beispiel wäre, wie du schon sagtest, $\begin{eqnarray*} n=3,m_1=2,m_2=3, m_3=5 \end{eqnarray*}$ .
Damit ergibt sich:
$\begin{eqnarray*} <br /> \sum\limits_{k_1=1}^{2} (\sum\limits_{k_2=k_1}^{3} (\sum\limits_{k_3=k_2}^{5} (1) )) = 19 \medspace\checkmark <br /> \end{eqnarray*}$

Habe es auch für verschiede $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} m_1,...,m_n \end{eqnarray*}$ getestet. Hat immer gestimmt. Habe aber noch 2 kurze Fragen:
1) Kann man das noch weiter zusammenfassen? (scheint nicht so :/)
2) Wie kann ich korrekt schreiben, dass z.B. alle $\begin{eqnarray*} m \in \mathbb N \end{eqnarray*}$ sind und aufwärts sortiert sind?
Mein Versuch wäre etwa: $\begin{eqnarray*} \forall x\in \mathbb N :1\leq x\leq n: (m_x\in \mathbb N) \wedge (m_x\geq m_{x-1}) \end{eqnarray*}$ (kann falsch sein)
Letztere Ungleichung gilt natürlich nicht für $\begin{eqnarray*} x=1 \end{eqnarray*}$ , weil $\begin{eqnarray*} m_0 \end{eqnarray*}$ nicht definiert ist... weiß aber nicht, wie man das ausdrücken soll.

Danke für Deine Zeit Wink

18.10.2016, 12:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 3r47057h3n35
$\begin{eqnarray*} N = \sum\limits_{k_1=1}^{m_1} (\sum\limits_{k_2=k_1}^{m_2} ( \left(...\right) (\sum\limits_{k_n=k_{n-1}}^{m_n} (1))\left(...\right) )) \end{eqnarray*}$

Das ist zweifelsohne richtig. Freude

Obwohl ich es einfacher als $\begin{align*} \sum\limits_{k_1=1}^{m_1} \sum\limits_{k_2=k_1}^{m_2} \ldots \sum\limits_{k_n=k_{n-1}}^{m_n} 1 \end{align*}$ schreiben würde.

Zitat:

Original von 3r47057h3n35
1) Kann man das noch weiter zusammenfassen? (scheint nicht so :/)

Genau das war im Prinzip die Frage in meinem letzten Beitrag, was ich mit dem Wörtchen "handhabbar" andeuten wollte.

Man könnte versuchen, die Summe von innen nach außen schrittweise aufzudröseln:

$\begin{align*} \sum\limits_{k_n=k_{n-1}}^{m_n} 1 = m_n-(k_{n-1}-1) \end{align*}$

$\begin{align*} \sum\limits_{k_{n-1}=k_{n-2}}^{m_{n-1}} \sum\limits_{k_n=k_{n-1}}^{m_n} 1 = \sum\limits_{k_{n-1}=k_{n-2}}^{m_{n-1}} (m_n-(k_{n-1}-1)) = m_n(m_{n-1}-(k_{n-2}-1)) - \frac{m_{n-1}(m_{n-1}-1)}{2} + \frac{(k_{n-2}-1)(k_{n-2}-2)}{2} \end{align*}$

usw. - jede "gelungenen" Summationsstufe spart im übrigen Zeit bei der numerischen Auswertung.

Vielleicht kann man das Chaos in den entstehenden Termen ein wenig in geordnete Bahnen lenken, hab mich da noch nicht ernsthaft mit befasst.

Zitat:

Original von 3r47057h3n35
2) Wie kann ich korrekt schreiben, dass z.B. alle $\begin{eqnarray*} m \in \mathbb N \end{eqnarray*}$ sind und aufwärts sortiert sind?

Mein Versuch wäre etwa: $\begin{eqnarray*} \forall x\in \mathbb N :1\leq x\leq n: (m_x\in \mathbb N) \wedge (m_x\geq m_{x-1}) \end{eqnarray*}$

Letztere Ungleichung gilt natürlich nicht für $\begin{eqnarray*} x=1 \end{eqnarray*}$ , weil $\begin{eqnarray*} m_0 \end{eqnarray*}$ nicht definiert ist... weiß aber nicht, wie man das ausdrücken soll.

Das könntest du natürlich dadurch retten, indem du zusätzlich $\begin{align*} m_0:=0 \end{align*}$ definierst. In dem Sinne haut dann alles hin. Freude

20.10.2016, 21:11

3r47057h3n35

Auf diesen Beitrag antworten »

Danke für deine Hilfe. Werde mich mal weiter damit befassen.
Das mit dem $\begin{eqnarray*} m_0 = 0 \end{eqnarray*}$ erscheint mir jetzt vollkommen logisch...
hätte man selber drauf kommen können Hammer

Neue Frage »

Antworten »

Kombination von Ziffern

Verwandte Themen