Möglichkeiten bei Reihenfolge ohne Wiederholung

06.07.2018, 15:45

komboklaus

Möglichkeiten bei Reihenfolge ohne Wiederholung

Meine Frage:
Hallo Leute,

folgendes Szenario sei gegeben: Ich habe eine Urne vor mir liegen. In dieser Urne sind endlich beliebig viele verschiedene Elemente, jedes Element kann auch endlich beliebig oft vorkommen. Mal ein einfaches Beispiel: Eine Urne mit 3 grünen, 5 roten und 2 gelben Äpfeln.

Ich möchte nun aus dieser Urne eine bestimmte Anzahl von Elementen ziehen mit Ordnung also Reihenfolge ohne Wiederholung und interessiere mich für die verschiedenen Möglichkeiten (KOMBINATORIK).

Meine Ideen:
$\begin{eqnarray*} n \end{eqnarray*}$ sei die Anzahl der Elemente insgesamt
(in unserem Beispiel 10 Äpfel)

$\begin{eqnarray*} m_{i} \end{eqnarray*}$ mit $\begin{eqnarray*} i \in \left\{ 1,2,3,...,l\right\} \end{eqnarray*}$ , wobei $\begin{eqnarray*} l \end{eqnarray*}$ die Anzahl der verschiedenen Arten angibt, sei die Anzahl der jeweils gleichen Elemente.

(In unserem Beispiel $\begin{eqnarray*} m_{1} \end{eqnarray*}$ ist 3, wegen 3 grünen Äpfeln; $\begin{eqnarray*} m_{2} \end{eqnarray*}$ ist 5, wegen 5 roten Äpfeln; $\begin{eqnarray*} m_{3} \end{eqnarray*}$ ist 2, wegen 2 gelben Äpfeln)

$\begin{eqnarray*} k \end{eqnarray*}$ sei die Anzahl der Ziehungen

(In unserem Beispiel möchte ich 3 mal ziehen)

Lautet für dieses Szenario die Formel:
$\begin{eqnarray*} \frac{\frac{n!}{m_{1}!m_{2}!...m_{l}!} }{\left(\frac{n!}{m_{1}!m_{2}! \dots m_{l}!}-k\right)!} \end{eqnarray*}$

Willkommen im Matheboard!

Ich hab Dein LaTeX leicht korrigiert, damit es dargestellt werden kann.

Viele Grüße
Steffen

07.07.2018, 06:38

HAL 9000

Auf diesen Beitrag antworten »

Bei der von dir vorgeschlagenen Formel handelt es sich wohl um einen Scherz - die ist so grotesk falsch, dass jede weitere Kommentierung Zeitverschwendung wäre. Augenzwinkern

-------------------------------------------------------------

Sei $\begin{eqnarray*} f(l;m_1,\ldots,m_l;k) \end{eqnarray*}$ die gesuchte Anzahl. Dann kann man folgendes über diese Anzahl sagen:

a) Klar muss $\begin{eqnarray*} m_1+\ldots+m_l\geq k \end{eqnarray*}$ gelten, sonst sind nicht genug Elemente zur Auswahl da. Das setzen wir also im folgenden voraus.

b) Es ist $\begin{eqnarray*} f(l;m_1,\ldots,m_l;k)\leq l^k \end{eqnarray*}$ , wobei Gleichheit genau dann gilt, wenn $\begin{eqnarray*} m_i\geq k \end{eqnarray*}$ für alle $\begin{eqnarray*} i=1,\ldots,l \end{eqnarray*}$ gilt. Denn in diesem Gleichheitsfall sind von jeder der $\begin{eqnarray*} l \end{eqnarray*}$ Arten genug Elemente vorhanden, dass eine uneingeschränkte Auswahl gemäß "Variationen mit Wiederholung" gewährleistet ist. In allen anderen Fällen, d.h., $\begin{eqnarray*} m_i<k \end{eqnarray*}$ für wenigstens ein $\begin{eqnarray*} i \end{eqnarray*}$ , ist die Anzahl garantiert kleiner.

c) Im Fall $\begin{eqnarray*} k\leq l \end{eqnarray*}$ ist $\begin{eqnarray*} f(l;m_1,\ldots,m_l;k)\geq \frac{l!}{(l-k)!} \end{eqnarray*}$ , wobei hier Gleichheit genau dann gilt, wenn $\begin{eqnarray*} m_1=\ldots=m_l=1 \end{eqnarray*}$ ist. Dieser Gleichheitsfall nun wieder entspricht "Variationen ohne Wiederholung". Eine brauchbare untere Schranke im Fall $\begin{eqnarray*} k>l \end{eqnarray*}$ anzugeben ist übrigens deutlich schwieriger, aber die brauchen wir auch nicht (siehe unten).

d) Eine explizite Formel für den allgemeinen Fall scheint schwierig zu sein, um nicht zu sagen unmöglich. Aber rekursiv ist einiges drin: Es ist

$\begin{eqnarray*} f(l;m_1,\ldots,m_l;k) = \sum_{j=\max(0,k-m_1-\ldots-m_{l-1})}^{\min(k,m_l)} \binom{k}{j} f(l-1;m_1,\ldots,m_{l-1};k-j) \end{eqnarray*}$

unter Beachtung der in a) und b) gegebenen Randwerte, an denen die Rekursion stoppen kann. Dahinter steckt die Idee, dass man genau $\begin{eqnarray*} j \end{eqnarray*}$ Elemente vom Typ $\begin{eqnarray*} l \end{eqnarray*}$ in seine Auswahl aufnimmt. Wegen der Berücksichtigung der Auswahlreihenfolge gibt es $\begin{eqnarray*} \binom{k}{j} \end{eqnarray*}$ Möglichkeiten, wo diese $\begin{eqnarray*} j \end{eqnarray*}$ Elemente innerhalb der $\begin{eqnarray*} k \end{eqnarray*}$ Auswahlpositionen stehen können. Die restlichen $\begin{eqnarray*} k-j \end{eqnarray*}$ Elemente stammen nun von den Typen $\begin{eqnarray*} 1,\ldots,l-1 \end{eqnarray*}$ . Die obere Summationsgrenze dürfte klar sein, denn $\begin{eqnarray*} j \end{eqnarray*}$ darf sowohl $\begin{eqnarray*} k \end{eqnarray*}$ als auch $\begin{eqnarray*} m_l \end{eqnarray*}$ nicht überschreiten. Die untere Summationsgrenze ist womöglich schwerer zu verstehen: Die garantiert $\begin{eqnarray*} k-j \leq m_1+\ldots+m_{l-1} \end{eqnarray*}$ , d.h. die in a) angesprochene Mindestvoraussetzung für die Auswahl der $\begin{eqnarray*} (k-j) \end{eqnarray*}$ Restelemente aus dann nur noch $\begin{eqnarray*} l-1 \end{eqnarray*}$ Typen.

Man kann das auch umindizieren $\begin{eqnarray*} i=k-j \end{eqnarray*}$ und bekommt damit dann

$\begin{eqnarray*} f(l;m_1,\ldots,m_l;k) = \sum_{i=\max(0,k-m_l)}^{\min(k,m_1+\ldots+m_{l-1})} \binom{k}{i} f(l-1;m_1,\ldots,m_{l-1};i)\qquad (*) \end{eqnarray*}$ .

Berechnen wir mal dein Beispiel $\begin{eqnarray*} f(3;5,3,2;k) \end{eqnarray*}$ :

1) Für $\begin{eqnarray*} k\leq 2 \end{eqnarray*}$ haben wir Fall b), also $\begin{eqnarray*} f(3;5,3,2;k) = 3^k \end{eqnarray*}$

2) Für $\begin{eqnarray*} k\geq 3 \end{eqnarray*}$ nutzen wir die Rekursion (*): $\begin{eqnarray*} f(3;5,3,2;k) = \sum_{i=k-2}^{\min(k,8)} \binom{k}{i} f(2;5,3;i) \end{eqnarray*}$ .

2a) Für $\begin{eqnarray*} k=3 \end{eqnarray*}$ bedeutet das $\begin{eqnarray*} f(3;5,3,2;3) = \sum_{i=1}^3 \binom{3}{i} f(2;5,3;i) \stackrel{b)}{=} \sum_{i=1}^3 \binom{3}{i} 2^i = 3\cdot 2 + 3\cdot 2^2 + 1\cdot 2^3 = 26 \end{eqnarray*}$ . Das ist nur Eins unter der Maximalzahl $\begin{eqnarray*} 3^3=27 \end{eqnarray*}$ gemäß b), was auch nicht weiter verwundert: Es sind alle Auswahlen mit Zurücklegen möglich außer "dreimal gelber Apfel". Augenzwinkern

2b) Für $\begin{eqnarray*} k=4 \end{eqnarray*}$ haben wir $\begin{eqnarray*} f(3;5,3,2;4) = \sum_{i=2}^4 \binom{4}{i} f(2;5,3;i) = 6\cdot 2^2 + 4\cdot 2^3 + f(2;5,3;4) = 56 + f(2;5,3;4) \end{eqnarray*}$ . Hier splittet sich die Rechnung weiter auf, gemäß (*) erhalten wir

$\begin{eqnarray*} f(2;5,3;4) = \sum_{i=1}^4 \binom{4}{i} f(1;5;i) \stackrel{b)}{=} \sum_{i=1}^4 \binom{4}{i} 1^i = 15 \end{eqnarray*}$ ,

insgesamt also $\begin{eqnarray*} f(3;5,3,2;4) = 71 \end{eqnarray*}$ .

Formel (*) mit Abbruchkriterium b) kann man rechentechnisch gut umsetzen, das ergibt dann folgende Werte $\begin{eqnarray*} f(3;5,3,2;k) \end{eqnarray*}$ für $\begin{eqnarray*} k=1,2,\ldots,10 \end{eqnarray*}$ :

3 , 9 , 26 , 71 , 181 , 422 , 889 , 1652 , 2520 , 2520

Der letzte Wert (und damit auch der vorletzte) lässt sich auch durch Permutationen mit Wiederholung $\begin{eqnarray*} \frac{10!}{5!3!2!} = 2520 \end{eqnarray*}$ erklären, das ist eben so, wenn alle 10 Äpfel ausgewählt werden müssen und es nur noch auf die Reihenfolge der Auswahl ankommt.

(*) in MuPAD-Code:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

f := proc(m,k)
  local l,ml;
  option remember;
  begin
    l := nops(m) :
    ml :=  m[l] :
    if (k <= ml) then
      return(l^k)
    else
      delete(m[l]) :
      return(_plus(binomial(k,i)*f(m,i) $ i=k-ml..min(k,_plus(op(m)))))
    end_if :
  end_proc :
f([5,3,2],k) $ k=1..10

10.07.2018, 14:50

komboklaus1

Auf diesen Beitrag antworten »

Vielen lieben Dank für deine Bemühungen,

das sieht auf keinen Fall nach einer kurzen und knappen geschlossenen Formel aus. Ich habe mir halt so meine Gedanken für eher untypische Fragestellungen gemacht. Zumindest weiß ich jetzt warum sie untypisch sind. Ich werde mir deine Ausführungen mehrmals durchgehen müssen.

Danke schön

11.07.2018, 08:58

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von komboklaus1
das sieht auf keinen Fall nach einer kurzen und knappen geschlossenen Formel aus.

"Kurz und knapp" kann man sowieso vergessen. Aber wie ich oben befürchtet habe, wird es auch "lang und komplziert" vermutlich nichts mit einer geschlossenen expliziten Formel. Nur in trivialen Spezialfällen wie oben b) oder eben ganz am Ende der Rechnung $\begin{eqnarray*} k=m_1+\ldots+m_l \end{eqnarray*}$ sind relativ einfache Formeln anwendbar, in der "Mitte" sieht es damit hingegen trübe aus. Manchmal muss man sich eben auch mit einer solchen rekursiven Lösung abfinden - immer noch besser und (bei großen Parameterwerten) weitaus schneller, als die Auswahltupel einzeln von Hand abzuzählen. Augenzwinkern

Neue Frage »

Antworten »

Möglichkeiten bei Reihenfolge ohne Wiederholung

Verwandte Themen