Matek segítség a világvége ellen

Fórumok

Sziasztok!

Régen volt, akkor sem érdekelt, de most ezt kell megoldanom :-)

Adott 59 db különböző szám, adott 24 db különböző betű. Hányféle módon lehet az 59 db számot a betűkhöz hozzárendelni úgy, hogy minden betűhöz legalább egy szám tartozzon? Természetesen így lesznek betűk, amelyekhez több szám is tartozik majd.

Hogyan kell ezt kiszámolni?

Segítsetek, mert meg kell menteni a világot és csak ez hiányzik hozzá :-)

Üdv, Cz

Hozzászólások

Ahogy nézem, az összes eset számát két részből lehet kiszámolni.

(1) 59!/(24!*(59-24)!), vagyis 59 alatt 24 művelet. Ezzel biztosítjuk, hogy minden betűhöz kerüljön pontosan 1 db egyedi szám.

(2) A megmaradt 35 egyedi számot kell szétosztani 24 egyedi betű között tetszőlegesen. Vagyis a 35 szám kerülhet 1 betűhöz is, de majdnem egyenletesen szétosztható mindegyik.

A (2)-re nem tudom a kiszámítás módját.

De lehet, hogy nem is lehet így kettéválasztani a feladatot?

Valaki?

Mittudomén :)

Az 1. pontodban 59 számból hozzá kell rendelni egyet-egyet a 24 betűhöz. Ez (halvány) emlékem szerint variáció, nem kombináció, így 59!/(59-24)!.

A 2. pontban a maradék 59-24 számot tetszőlegesen el kell osztani a 24 betű között, akár mind mehet ugyanahhoz a betűhöz is, szóval az első mehet 24 helyre, a második szintén 24 helyre, stb, és mivel ezek egymástól függetlenek, így összesen (59-24)*24 lehetőség van.

És mivel a 1. és 2. egymástól függetlenek, ezért szorozni kell őket ahhoz, hogy az összes lehetőség számát megkapjuk.

Szerintem a szorzat második fele így néz ki:

(59-24)^(24)

Ezzel azt számolom hogy az 1. szám ... 35. szám a 24 betű valamelyikéhez társítható. Ha ezt írom: 24^(59-24), akkor az adott betűhöz 1. szám .. 35. szám valamelyike jöhet, csakhogy ez nem kezeli azt a helyzetet, amikor az adott betűhöz nem kerül szám (a második körben, az első körben ugye pont egy kerül).

Így van? Nem így van? :-)

Hány betűhöz társíthatod az első számot? 24.
Hány betűhöz társíthatod a második számot? 24. Az előzővel együtt 24*24.
Hány betűhöz társíthatod a harmadik számot? 24. Az előzőkkel együtt 24*24*24 = 24^3
...
Hány betűhőz társíthatod a (59-24). számot? 24. Az előzőkkel együtt 24^(59-24).

Most itt tartok:

(59!/(59-24)!)*(59-24)^(24)

Az első résznél 59-ből kell kiválasztani 24-et, hogy minden betűhöz biztosan egy db szám kerüljön (variáció). A szorzat második fele pedig a maradék 35 számot helyezi el 24 lehetséges betű között (a maradékok közül az 1. szám mehet 24 hely valamelyikére, a 2. szám is a 2 betű valamelyikére, stb.)

Ez így rendben?

a szorzat első része szerintem is ahogy említed, a második pedig 35!/(35-24)! <- mert egy ismétlés nélküli variációról van szó. A 35 pedig úgy jön ide hogy ennyi a maradék amit szét kell osztani.

valószínűleg nem jó mert régen tanultam már, de nagyon érdekel a megoldás!

Ha jól értem, akkor 59 elemet kell 24 nemüres halmazba csoportosítanod.
Ez ekvivalens a következő problémával:
1. Kiválasztunk 24 elemet a számok halmazából, ezt 59!/(35!*24!)-féleképpen tehetjük meg.
2. A maradék 35 elemű halmazt partícionáljuk, a partíciók száma a 35-ik Bell-szám: https://en.wikipedia.org/wiki/Bell_number. Ezt egy szép rekurzióval lehet definiálni.

A választ pedig e kettő elem szorzata lesz, hiszen bármelyik elemhez bármelyik részhalmaz tartozhat.

Szerk: bocs, hülyeséget mondtam, hiszen a Bell-számok a nemüres particionálást adják meg.

268985222594418623144865380750037815845751903363416223407550814877738598400000000 (2.68 * 10^80)

Nagyságrendi ellenőrzés: Ha a „minden betűhöz legalább egy szám tartozzon” kitétel nem lenne ott, akkor az 59 szám mindegyikéhez egymástól függetlenül 24 betű valamelyikét rendelhetnénk, ami 24^59 ≈ 2.70e81 lehetőség. Ennél „kicsit” kisebb lesz a végeredmény, történetesen kábé a tizede. Érzésre, ha 24 betűt felírsz egy-egy cetlire, és egy játékmenet során 59 alkalommal húzol, mindig visszatéve a cetlit (tehát újra húzhatod), szerintem reális, hogy 10 játékmenetből várhatóan 1-szer fogod mind a 24-et kihúzni legalább egyszer, és 9-szer egy vagy több kimarad.

Itt egy villámgyorsan összetákolt shell szkript, amely kis értékekre egyszerűen végigveszi az összes lehetőséget, és megnézi mindegyikre, hogy jó-e. Nagyobb értékekre ne is álmodj róla hogy lefut épeszű időn belül. Viszont kisebb értékekre használható arra, hogy egy képlet helyességét leellenőrizd.

#!/bin/bash

maxszam=10
maxbetu=c

betuk="{a..$maxbetu}"
minta=""
for i in $(eval echo {1..$maxszam}); do
  minta="$minta$betuk"
done

count=0
for szo in $(eval echo $minta); do
  jo=1
  for betu in $(eval echo $betuk); do
    if [ "$szo" = "${szo#*$betu}" ]; then
      jo=0
      break
    fi
  done
  if [ $jo = 1 ]; then
    count=$((count+1))
  fi
done

echo $count

Ez pedig egy másik tákolmány szkript, amely nagy értékekre (pl. maxszam=59, maxbetu=24) is megmondja a frankót. Helyesebben a kimenetét a bc-be kell pipe-olni.

#!/bin/bash

maxszam=10
maxbetu=3

echo '
define f (x) {
  if (x <= 1) return (1);
  return (f(x-1) * x);
}
define choose (n, k) {
  return (f(n) / f(k) / f(n-k));
}
'

echo -n $maxbetu^$maxszam

k=1
while [ $k -lt $maxbetu ]; do
  if [ $((k % 2)) == 1 ]; then
    echo -n " - "
  else
    echo -n " + "
  fi

  echo -n "choose($maxbetu, $k) * ( ($maxbetu-$k)^$maxszam )"

  k=$((k+1))
done
echo

A képlet a logikai szita gondolatmenetét alkalmazza.

Ha nincs ott a kitétel, hogy mindegyik betűnek szerepelnie kell, akkor 24^59.

De sajnos így számoltuk azokat is, amelyekben csak 23 betű fordult elő. Számoljuk meg tehát, hányféleképpen lehet 23 betűhöz hozzárendelni, és korrigáljunk ennyivel. Ráadásul ne felejtsük, 24 féle képpen választhatjuk meg, hogy melyik 23 betűt engedjük és melyik 1-et nem. Tehát levonunk 24-szer 23^59-et.

De jajj! Akik csak 22 betűt tartalmaznak, azokat is az elején egyszer számoltuk, de most levontuk kétszer is, aszerint hogy melyik az a huszonharmadik betű amit elvileg engedtünk, de mégse szerepelt. Ezeket tehát megint hozzá kell adni. (24 alatt 2) féle képpen lehet kiválasztani, hogy melyik 22 betűről van szó, és 22^59 ilyen hozzárendelés van.

Na de megint túllőttünk a célon a csak 21 betűt tartalmazókkal, ezért újból le kell vonni (24 alatt 3) szor 21^59-et.

És így tovább...

Az sosem volt 100%-ig világos számomra, hogy miért mindig pont eggyel lövünk mellé minden egyes alkalommal a pont épp szóban forgó mennyiségű különböző betűt tartalmazó hozzárendelések megszámolásakor, de valahogy arról van szó, hogy ha a Pascal háromszög adott sorában a binomiális együtthatókat felváltva plusz/mínusz előjellel veszed, akkor a teljes sor összege nulla, azaz az utolsó szám előtt megállva 1. Például számoltad 1-szer, majd levontad 4-szer, majd hozzáadtad 6-szor, majd megint levontad 4-szer, akkor még hozzá kell adni 1-szer, így lesz 0. Olvass utána a logikai szitának, biztos megtalálod részletesen levezetve.

A csatolt második szkript ezt a képletet köpi ki, és kis számokra az eredménye megegyezik az első szkript által adott, simán leszámolt értékkel. Ez remélem eléggé meggyőző :)

Szerkesztve: 2019. 10. 29., k - 16:24

11-nél több szám egy betűhöz sem tartozhat (mert ha 23-hoz 1, a 24. -hez a többi tartozik, akkor a 24.-hez pont 11 fog), ezt kéne képlettel felírni és kivonni az összesből így megkapnánk a maradékot, azaz az eredményt!

tehát 59 ből 24-et 59!/24! azaz 2,2352e56 féleképp lehet kiválasztani ebből kéne kivonni azokat az eseteket ahol több mint 1/minimum 2 szám tartozik egy betűhöz. Itt akadtam el :D