4. Mal wieder das leidige Thema "Kobinatorik"

Mal wieder das leidige Thema "Kobinatorik"

  • ?

    Hallo, ich habe folgendes Kombinatorikproblem:

    Ein Spiel besteht aus 10 Spielsteinen:
    Von jedem Spielstein gibt es 4 Stück (also ein Spiel besteht aus 40 Steinen)

    Wie viele verschiedene(!) Starthände kann man daraus bauen, wenn man am anfang 5 steine zieht
    (also abcde == acedb, Reihenfolge in der Hand ist egal)

    Es ist ja nicht (40 über 5), da wären ja dann einige Kombinationen doppelt drin (zB würde da "aabcd" zweimal vorkommen)
    10 über 5 ist es auch nicht, weil da ja nur je ein spielstein drin wäre

    Es muss also 252 < x < 658008 gelten.

    Im Prinzip müsste man ja nur alle kombinationen zählen, die bei (40 über 5) vorkommen, bei denen es mind. 1 stein mehrfach gibt und diese vom Ergebnis abziehen. Aber wie geht man mathematisch daran?

    0
  • ?

    Ich habs grad mal probiert mit 8 Spielsteinen:
    (8*4) über 5: 201376
    8 über 5: 56
    richtiges Ergebnis (also keine doppelten Hände): 784

    Das hilf mir aber nicht dabei, eine Formel dafür zu entwickeln 😃

    0
  • S

    Geh davon aus, dass die beliebig viele Spielsteine von jeder Sorte zur Verfügung hast. Wieviele mögliche Starthände gibt es jetzt? Das müssten 5+10-1 über 10-1 sein.

    Das sind jetzt aber zu viele. Aber nicht viel. Die einzigen unmöglichen Starthände, die wir so erzeugen, sind die mit 5 gleichen Steinen - also genau 10 Stück.

    0
  • ?

    Ah! Phantastisch!
    Aber kann man die Anzahl der weggelassenen Kombinationen noch weiter verallgemeinern?
    Was ist, wenn ich 13 Steine aus 34 ziehen und es von jedem Stein 4 Stück gibt? Jetzt müssen ja alle Hände abgezogen werden, in denen unter den 13 steinen mind. 1 stein mind.5 mal vorkommt

    0
  • ?

    Ich habe mir nochmal ein paar Gedanken dazu gemacht (scheinen zwar falsch zu sein, aber vielleicht bringen sie jemanden auf eine richtige Idee):

    Nehmen wir an, folgendes Setup:
    Es gibt 4 Spielsteine, die Hand besteht aus 3 Steinen.
    Somit n=4, k=3
    Alle Kombinationen:

    aaa    bbb    ccc    ddd
aab    bbc    ccd
aac    bbd    cdd
aad    bcc
abb    bcd
abc    bdd
abd
acc
acd
add

    Das sind insgesamt $$\binom{n+k-1}{k}$$ Kombinationen (hier = 20).
    Wenn es jetzt von jedem Spielstein 2 gibt, fällt die oberste Reihe weg. Wir haben damit 20 - 4 = 16.
    Wenn es von jedem Spielstein nur 1 gibt, dann fallen zusätzlich alle Kombinationen weg, bei denen es von einem Stein 2 gibt: 20 - 4 - 12 = 4.
    Das hat mich auf folgende Formel gebracht:

    (n+k−1k)−∑i=0k−Anzahl−1(n∗(n−i)i))\binom{n+k-1}{k}-\sum_{i=0}^{k-Anzahl-1}(n*(n-i)^i))

    Das liefert für Anzahl = 1 und Anzahl = 2 tatsächlich ein richtiges Ergebnis (blos für alle anderen Werte nicht 😃 ).

    Hat jemand eine Idee, wie es richtig lauten könnte? 😕

    0
  • ?

    Hat keiner eine Idee? 😞

    0
  • ?

    Meiner Meinung nach müsste die Formel für die Lösung lauten:

    (n+k-1)!
    über
    (n-1)!*k!

    n=4 k=3 Lösung: 20

    PS: Ist meiner erster Beitrag hier - kenne mich mit Formel-"Schreibung" nicht aus 😕

    0
  • ?

    Hm in deiner Formel kommt ja garnicht vor, wie oft ein Stein vorkommt.
    Außerdem wäre für mein letztes Beispiel (34 Steine, jeder Stein 4 mal, 13 Steine in der Hand) das Ergebnis 46! über 33!*13! (und das ist VIEL zu hoch).

    Das kann es also nicht sein 😞

    0
  • ?

    Ziehen von n Steinen aus w verschiedenen, die je 4mal da sind:

    \sum_{k=0}^{n/4}[\binom{4w}{k}*\sum_{a=0}^{(n-4k)/3}(\binom{4w-k}{a}*\sum_{t=0}^{(n-4k-3a)/2}(\binom{4w-k-a}{t}*\binom{4w-k-a-t}{n-4k-3a-2t}))]

    bei n=5, w=8 sind es 784, bei n=13, w=34 sind es 98521596000

    0
  • ?

    Temporary schrieb:

    Ziehen von n Steinen aus w verschiedenen, die je 4mal da sind:

    \sum_{k=0}^{n/4}[\binom{4w}{k}*\sum_{a=0}^{(n-4k)/3}(\binom{4w-k}{a}*\sum_{t=0}^{(n-4k-3a)/2}(\binom{4w-k-a}{t}*\binom{4w-k-a-t}{n-4k-3a-2t}))]

    bei n=5, w=8 sind es 784, bei n=13, w=34 sind es 98521596000

    Genau! Das dachte ich mir auf den ersten Blick auch.

    0
  • ?

    TravisG schrieb:

    Temporary schrieb:

    Ziehen von n Steinen aus w verschiedenen, die je 4mal da sind:

    \sum_{k=0}^{n/4}[\binom{4w}{k}*\sum_{a=0}^{(n-4k)/3}(\binom{4w-k}{a}*\sum_{t=0}^{(n-4k-3a)/2}(\binom{4w-k-a}{t}*\binom{4w-k-a-t}{n-4k-3a-2t}))]

    bei n=5, w=8 sind es 784, bei n=13, w=34 sind es 98521596000

    Genau! Das dachte ich mir auf den ersten Blick auch.

    😛 quelle ist das hier:
    http://www10.plala.or.jp/rascalhp/mjmath.htm
    da hat sich jemand irgendwann mal ziemlich viel arbeit gemacht...

    0
  • ?

    Temporary schrieb:

    TravisG schrieb:

    Temporary schrieb:

    Ziehen von n Steinen aus w verschiedenen, die je 4mal da sind:

    \sum_{k=0}^{n/4}[\binom{4w}{k}*\sum_{a=0}^{(n-4k)/3}(\binom{4w-k}{a}*\sum_{t=0}^{(n-4k-3a)/2}(\binom{4w-k-a}{t}*\binom{4w-k-a-t}{n-4k-3a-2t}))]

    bei n=5, w=8 sind es 784, bei n=13, w=34 sind es 98521596000

    Genau! Das dachte ich mir auf den ersten Blick auch.

    😛 quelle ist das hier:
    http://www10.plala.or.jp/rascalhp/mjmath.htm
    da hat sich jemand irgendwann mal ziemlich viel arbeit gemacht...

    Ahh... ja, was da steht macht Sinn.

    0
  • ?

    Ja, das scheint zu stimmen. War ja einfach... Danke.

    0
  • I

    Raphael1987 schrieb:

    Ja, das scheint zu stimmen. War ja einfach... Danke.

    So, jetzt muss ich doch noch fragen... wie löst du eigentlich solche Aufgaben? Liest du die Aufgabe durch, siehst dir das Resultat an und probierst dann mal aus bis du für ein par Werte das richtige Resultat bekommst?

    Falls nein, dann erklär mir doch jetzt mal diese Formel 😉

    0
  • ?

    Verstehen tue ich die Formel nicht. Aber ich hatte ja in einem meiner Posts ein Beispiel gemacht (5 aus 8 Steinen, wobei jeder Stein 4 mal vorkommt). Für dieses Beispiel bekomme ich das richtige Ergebnis.
    Ein paar andere Beispiele habe ich hier auf meinem Rechner auch gebruteforcet, und da stimmt die Formel auch. Und für mein eigentliches Beispiel (13 aus 34, jeder Stein 4 mal) liefert sie als Einziges ein plausibles Ergebnis...

    0
  • ?

    icarus2 schrieb:

    Raphael1987 schrieb:

    Ja, das scheint zu stimmen. War ja einfach... Danke.

    So, jetzt muss ich doch noch fragen... wie löst du eigentlich solche Aufgaben? Liest du die Aufgabe durch, siehst dir das Resultat an und probierst dann mal aus bis du für ein par Werte das richtige Resultat bekommst?

    Falls nein, dann erklär mir doch jetzt mal diese Formel 😉

    Also, alles was ich aus dem japanischen uebersetzen kann:

    n: 配牌の枚数 (親=14、子=13)
    k: 槓子の数
    a: 刻子の数
    t: 対子の数
    nCr = n!÷((n-r)!×r!)　( n個からr個をとる組合せの数 )
    Σの終値の除算による余りは切り捨てるものとします。

    n: Anzahl an gezogenen Steinen (Dealer=14, Non-Dealer=13) [Those are Mahjong terms]
    k: Anzahl an Vierlingen
    a: Anzahl an Drillingen
    t: Anzahl an Paerchen
    [Das ist eine Erklaerung des Binomial-Koeffizienten]
    Wenn die Summe dividiert wird, wird immer abgerundent.

    Keine garantie auf richtigkeit 😛 Und das erklaert mir auch nicht, wie genau das jetzt funktioniert, das ist alles was dazu steht...

    0
Anmelden zum Antworten