Anzahl der unterschiedlichen Tupel

Question

Aufgabe:

 Wie viele sich in max. 3 stellen unterscheidende Tupel zu (0,0,0,0) gibt es ?

Dabei dürfen die Elemente aus {0,1,2,3,4} gewählt werden

Problem/Ansatz:

Ich hätte folgende Lösung gewählt:

Jede Stelle hat jeweils 5 Möglichkeiten also 5³ verschiedene Tupel. Da die 0 nicht fest ist sind es also  4 * 5³ = 500 Tupel

Das wäre meine Lösung gewesen. Nach etwas nachforschen bin ich auf folgende Lösung gestoßen welche anscheinend die richtige sein soll:

\( \sum\limits_{n=0}^{3}{4 \choose n } * (5-1)^n = 369\)

Kann mir jemand genauer erklären warum dies die richtige Lösung und meine falsch ist? Falls das die richtige Lösung ist.

Comments

Ich glaube eher, dass deine Lösung richtig war.

Answer 1

Es gibt insgesamt 5⁴ 4er-Tupel, deren Elemente aus der vorgegebenen Menge sind. Von diesen enthalten genau 4⁴ keine 0 und die restlichen mindestens eine, oder umständlicher formuliert: sie unterscheiden sich in maximal drei Stellen von (0,0,0,0). So komme ich auf 5⁴ - 4⁴ = 369 Tupel. Bei deinen Überlegungen hast du einige Tupel mehrfach gezählt, nämlich die mit mehr als einer 0. Die andere Lösung habe ich auch so nicht nachvollzogen, da jeglicher Kommentar fehlt.

Comments

Nachtrag: Die andere Lösung zählt die Möglichkeiten, wenn eine Unterscheidung in 0,1,2 oder 3 Stellen vorliegt. Dann stellt sich die Frage, an welchen Stellen sollen die Tupel unterschiedlich sein? Die Anzahl der Möglichkeiten hierfür kann durch den Binomialkoeffizienten ausgedrückt werden. Wenn man die Stelle festgelegt hat, hat man an jeder noch freien Stelle 5 - 1 = 4 Möglichkeiten, daher die Potenz. Und wenn man zu der Summe noch den analogen Summanden für n = 4 ergänzt (der wäre einfach nur 4⁴), erhält man (4+1)⁴ =5⁴ in der ausmultiplizierten Form.

---

Also die Tupel dürfen sich in max. 3 Stellen unterscheiden das heißt es dürfen 0 bis 3 Stellen sich vom 0-Tupel unterscheiden.

Zu der Summenlösung gab es keine genau Erklärung lediglich die Lösung. Die Summe hätte ich auch so verstanden dass jeweils die Anzahl der Tupel gezählt wird die sich in 0 bis 3 Stellen unterscheiden und da die stelle an der sie sich unterscheiden egal ist wird der binom-koeff. Noch drauf multipliziert.

Dass durch 5⁴ - 4⁴ = 369 beschrieben wird leuchtet mir ein.

Dennoch hätte ich mich im Prüfungsfall für meine erste Version entschieden da es egal ist an welcher stelle und an wie vielen stellen ( < 4 ) sich die Tupel unterscheiden, daher sollte man doch getrost über n^k an die Anzahl kommen, oder nicht?

Vielleicht sollte ich die Aufgabe etwas näher erklären: Konkret handelt es sich bei den Tupeln um Wörter aus der Menge {0,1,2,3,4}⁴ und es soll nun die Anzahl der Wörter gezählt werden die den Hammingabstand <= 3 zu dem 0 Tupel besitzen.

---

Bei deiner Rechnung 4*5³ zählst du beispielsweise (0,2,0,3) einmal zu den Tupeln, die vorne eine Null haben und einmal zu denen, die an der dritten Stelle eine 0 haben. Es darf aber nur ein Mal gezählt werden. Wenn du etwas programmieren kannst, lass doch mal einen Computer alle Möglichkeiten durchgehen. Oder löse ein ähnliches Problem mit kleineren Zahlen, wo du per Hand noch die Möglichkeiten durchgehen kannst.