Forum: Offtopic Wie heisst diese Berechnung? (Kombinatorik)


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Zipp (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich möchte folgendes Berechnen:

Ich habe n Bits. Wie viele Möglichkeiten gibt es, dass jeweils nur eine 
1 vorkommt, 2, 3, oder n Einsen?

also z.B. bei n=5 00001, 00010, 00100, 01000 und 10000 sind 
"gleichwertig". Wie heisst so ein Ding mathematisch? eine Permutation 
ist es nicht. Aber auch keine Variation und keine Kombination.

Ja, ich weiss, die Frage ist trivial, aber ein sauberer Beweis fehlt 
mir.

: Verschoben durch Moderator
von Sigi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Warum keine Permutation? Du hast n Bits, m davon
'1' (m < n !!) und damit n-m mal die '0'.
Schau mal in Wahrscheinlichkeitstheorie nach
Zufallsexperimenten mit und ohne Zurücklegen
nach.

von Sigi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Und: für m Bits hast du dann n!/(m!*(n-m)!) Lösungen.

von Zipp (Gast)


Bewertung
0 lesenswert
nicht lesenswert
hmm das sehe ich jetzt nicht wirklich :/

vielleicht haben wir uns auch falsch verstanden? Bei 3 Bits gibt es 
diese Kombinationen:

000
001
010
011
100
101
110
111

wenn ich nun das ganze etwas um ordne, dann erhalte ich dies

000
001 010 100
011 101 110
111

wobei ich die "gleichen" Kombinationen auf dieselbe Zeile geschrieben 
habe. Ist das wirklich eine Permutation? Permutation wäre doch 3!=6, und 
das ist hier falsch.

von Sigi (Gast)


Bewertung
0 lesenswert
nicht lesenswert

von Axel S. (a-za-z0-9)


Bewertung
0 lesenswert
nicht lesenswert
Zipp schrieb:
> Ich habe n Bits. Wie viele Möglichkeiten gibt es, dass jeweils nur eine
> 1 vorkommt, 2, 3, oder n Einsen?
...

> Wie heisst so ein Ding mathematisch? eine Permutation
> ist es nicht. Aber auch keine Variation und keine Kombination.

Natürlich ist das eine Kombination. Du mußt von deinen n Bitpositionen k 
auswählen (mit 1 <= k <= n). Und weil die Reihenfolge bei der Auswahl 
keine Rolle spielt, ist es eine Kombination und keine Variation.

https://de.wikipedia.org/wiki/Kombination_(Kombinatorik)

von Dumdi D. (dumdidum)


Bewertung
0 lesenswert
nicht lesenswert
Sigi hat es doch schon richtig geschrieben. Und bei Deinem 3bit 
Beispiel:

3!/0!3! = 1
3!/1!2!= 3
3!/2!1!=3
3!/3!0!=1

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.