Korttipakan ekat kortit, vierekkäiset läheisiä arvoja

Sama brute force koodi kuin edellisessä tehtävässä muuten, paitsi että vertailussa käytetäänkin tätä:

a=a+((abs(List[1]-List[2])<4)*(abs(List[2]-List[3])<4)*(abs(List[3]-List[4])<4)*(abs(List[4]-List[5])<4))

... eli siis viidelle ensimmäiselle kortille kahden vierekkäisen kortin numeroarvot eroavat toisistaan vähemmän kuin 4.

Tuon kun pyöräyttää kymmenellä miljoonalla kierroksella niin tulee osuudeksi
4.518 % (+- 0.007 %)

Ensinnäkin lasketaan, monellako eri tavalla voidaan valita viisi korttia pakasta. Tämä on yhdistelylaskun mukaan 52 yli 5, eli 52! / (5! * (52-5)!), mikä on 2 598 960.

Sitten lasketaan, monellako tavalla voidaan valita viisi korttia siten, että niiden arvot ovat korkeintaan kolmen päässä toisistaan. Tämä voidaan tehdä seuraavasti:

– Mikä tahansa kortti voidaan valita ensimmäiseksi kortiksi. Seuraavaksi valitaan toinen kortti siten, että sen arvo on ensimmäisen kortin arvo ±1 tai ±2 tai ±3, eli yhtä tai kahta yksikköä suurempi tai pienempi. Tällaisia vaihtoehtoja on 7 kappaletta.
– Sama toistetaan kolmannelle, neljännelle ja viidennelle kortille, joten jokaisen kortin valinnan vaihtoehtoja on 7 kappaletta.

Yhteensä siis erilaisia korttikomboja, joissa korttien arvojen väliset erot ovat korkeintaan kolme, on 7^4 eli 2401.

Lopuksi todennäköisyys saada viisi korttia, joiden arvot ovat korkeintaan kolmen päässä toisistaan, on 2401/2598960 ≈ 0,00092530 eli noin 0,093 %.

Tutkitaan tätä n:nnän funktiona (ja pidetään k=4, m=5 ja r=3). Jos n>30, niin todennäköisyys on

(1749568n-8647040) / (4n*(4n-1)(4n-2)(4n-3)(4n-4))

Tämä koodi laskee osoittajan yleisessä tapauksessa: https://www.online-python.com/aYE7cClNk8 . Todennäköisyys saadaan jakamalla ((kn)Pm):llä.

Kaava n:lle saadaan siitä, että jos ensimmäinen kortti on väliltä mr ... n-1-mr, niin näissä tapauksissa ei ole väliä mikä kortti se on koska ollaan tarpeeksi kaukana päätyarvoista.

Nämähän ovat ns. hilapistepolkuja (lattice paths):

https://www.desmos.com/calculator/fik3hkzkwd

Tai siis jokainen polku tuottaa tietyn määrän näitä korttijärjestelmiä riippuen siitä kuinka monta kertaa se vierailee eri tasoilla (voi olla myös 0, jos jollain tasolla yli k vierailua).

Jos lähdetään yleiselle m pohtimaan, niin aluksi kannattanee tutkia tapausta r=1. Silloinhan nämä ovat niinkuin ylhäältä rajoitettuja Motzkin polkuja https://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p8/pdf mutta lähtö- ja loppupiste saa olla mikä vain (väliltä 0...(n-1)). Ja lisäksi ne pitäisi siis enumeroida noiden tasovierailujen mukaan, jotta osataan laskea korttijuttu.

Jos muodostetaan generoiva funktio, jossa x = (x_1, x_2 ,..., x_{n-1}) ja x_j laskee (potenssissaan) kuinka monta kertaa vieraillaan tasolla j:

G_a(x) = sum_{p, |p[j+1]-p[j]|<=r, p[0]=a} prod_{j=0}^{m-1} x_{p[j]},

missä a on polun lähtötaso, niin meillähän on rekursio (kun r=1)

G_a = x_a*(1_{a>0} G_{a-1} + G_a + 1_{a<n-1}G_{a+1}).

Tämä on periaatteessa se miten eo. koodissa laskettiinkin. Mutta onkohan tälle gen. funktiolle olemassa analyyttistä kaavaa.