Etäisyyksien tulo on 1

Olkoon pisteet $A=(1,0)$ , $B=(\cos \alpha, \sin \alpha)$ ja $C=(\cos \alpha, -\sin \alpha)$ . Määritellään funktio $f:\mathbb{R}^2 \to [0, \infty), f(Z) =$ tulo pisteen $Z$ etäisyyksistä pisteisiin $A, B$ ja $C$ .

Funktion f tasa-arvo käyrä {f=1} sivuaa ympyrää pisteessä D.

Selvitä parametrin $\alpha$ arvo, jolla yo. kuvan tilanne toteutuu eli $f$ :n tasa-arvo käyrä $\{f=1\}$ sivuaa yksikköympyrää oikeassa puolitasossa.

Ratkaisu

Tulkitaan taso kompleksitasoksi, jolloin $A=1$ , $B=e^{i\alpha}$ ja $C=\bar B = e^{-i \alpha}$ . Tutkitaan funktiota $g(t) = |f(e^{it})|^2-1, t\in (0, \alpha)$ . (Huom: etäisyyden neliö on 1 joss etäisyys on 1.) Jotta sivuaminen tapahtuu pisteessä $e^{it_0}$ , täytyy arvon $t_0 \in (0, \alpha)$ olla funktion $g$ lokaali maksimi ja $g(t_0)=0$ sekä $g'(t_0)=0$ . Selvitetään ensin funktion $g$ lauseke:

$g(t) + 1\\= |e^{it}-1|^2 |(e^{it}-e^{i\alpha})(e^{it}-e^{-i\alpha})|^2 \\= (\sin^2 t + (1-\cos t)^2)|e^{2it}-2e^{it}(e^{i\alpha}+e^{-i\alpha})+e^{i\alpha}e^{-i\alpha}|^2 \\= 2(1-\cos t)|e^{2it}-2e^{it}\cos(\alpha)+1|^2 \\= 2(1-\cos t)|e^{it}(e^{it}-2\cos(\alpha)+e^{-it})|^2 \\= 2(1-\cos t)|2\Re(e^{it})-2\cos(\alpha)|^2 \\= 8(1-\cos t)(\cos t - \cos(\alpha))^2$

Merkitään $a = \cos \alpha$ . Nyt voidaan derivoida

$g'(t) = \sin t (\cos t - a)(\cos t - a - 2(1-\cos t))$

Koska $t_0 \in (0, \alpha)$ , on $a = 3\cos t_0 - 2$ , joka sijoitettuna yhtälöön $g(t_0) = 0$ antaa

$(1-\cos t_0)(2-2\cos t_0)^2 - \frac{1}{8} = 0$

jonka ratkaisuna saadaan $\cos t_0 = 1-2^{-5/3}$ ja näin ollen $a = 1-\frac{3}{2 \sqrt[^3]{4} }$ .

Siis $\cos \alpha = 1-\frac{3}{2 \sqrt[^3]{4} } \approx 0.055$ ja $\sin \alpha = \sqrt {\frac{3}{\sqrt[^3]{4}} - \frac{9}{8\sqrt[^3]{2}}} \approx 0.998$ .

Tehtäviä

Yleistys useammalle pisteelle. Kuinka parametri-pisteet täytyy valita? Tasavälein valinta ei toimi, kuten ao. kuvasta neljälle pisteelle nähdään.
Osoita, että valittiinpa kuinka monta pistettä tahansa (äärellisen monta kuitenkin) ja asetettiinpa ne kuinka tahansa, niin ympyrän kehältä löytyy aina piste, jossa $f>1$ . (Määritelmässä otetaan tietenkin tulo kaikkien parametri-pisteiden yli.)
Kuinka suuri osa ympyrän kehästä voi korkeintaan olla joukon $\{f \leq 1\}$ sisällä ja millä parametri-pisteiden ( $n$ kpl) asettelulla tämä saavutetaan? Onko kolmelle pisteelle alkuperäisessä tehtävässä ratkaistu tapaus optimaalinen?

Kahden vääntyneen kolikon peli

Pelissä on kaksi kolikkoa, kutsutaan niitä ensimmäinen ja toinen kolikko. Todennäköisyydet että näillä tulee kruuna (H) ovat vastaavasti $x$ ja $y$ .

Peli etenee seuraavasti: Pelaaja heittää kolikkoja toistuvasti ja pistää merkille minkä tuloksen hän sai (HT, TH, HH tai TT). Jos hän jossain vaiheessa saa kaksi kertaa putkeen tuloksen HH tai kaksi kertaa putkeen tuloksen TT, niin peli päättyy. Jos taas hänen viime tuloksensa on HH ja hän saa heti tämän jälkeen tuloksen TT, niin hän pääsee bonuspeliin. Bonuspelissä hän heittää molempia kolikkoja (erikseen) kaksi kertaa. Jos ensimmäisellä kolikolla tulee ensimmäisellä heitolla H, pelaaja voittaa 5 pistettä, mutta jos tämän jälkeen toisella heitolla tulee H, pelaaja menettää 3 pistettä (eli voittaa vain 2 pistettä yhteensä). Mikäli ensimmäisellä heitolla tulee T, pelaaja ei voita eikä häviä mitään. Vastaavat luvut toiselle kolikolle ovat 3 ja -4 eli HT antaa 3 pistettä ja HH 3-4 = -1 pistettä. Bonuspelin jälkeen peli jatkuu normaalisti (bonuspelin heittoja ei rekisteröidä, eli pelissä viimeksi on tullut TT).

Miten vääntyneet kolikot peliin kannattaa ottaa (eli kuinka muuttujat $x$ ja $y$ väliltä $[0, 1]$ valita), kun halutaan maksimoida pelaajan voittojen odotusarvo?

Ratkaisu

Lasketaan todennäköisyydet

$a = \mathbb{P}(HT \wedge TH) = x+y-2xy$
$b = \mathbb{P}(HH) = xy$
$c = \mathbb{P}(TT) = 1-x-y+xy$

Muodostetaan Markovin ketju tiloina ”HT tai TH”, ”HH”, ”TT” ja ”End”.

Pelin Markovin ketju, sen siirtymätodennäköisyysmatriisi ja fundamentaalimatriisi. Olemme kiinnostuneet fundamentaalimatriisin ensimmäisen rivin toisesta alkiosta, joka kertoo odotusarvon kuinka monta kertaa ketju käy tilassa HH ennen absorboitumista, kun se alkaa tilasta ”HT tai TH”. (Aloitetaan tästä tilasta, koska silloin ei ole väliä mitä on tullut viimeksi.)

Siirtymätodennäköisyydet ovat muuten tilasta riippumattomat, paitsi tiloista ”HH” ja ”TT” ei mennäkkään vastaavilla heitoilla niihin itseihinsä vaan tilaan ”End”. Tila ”End” on absorboiva.

Pelin voiton odotusarvo saadaan (iteroidun odotusarvon kaavan nojalla) kertomalla yhden bonuspelin voiton odotusarvo ( $5x -3x^2 + 3y - 4y^2$ ) sillä kuinka monta kertaa siihen odotusarvoisesti päästään. Tämä odotusarvo taas saadaan kertomalla tilassa ”HH” vierailujen odotusarvo siirtymätodennäköisyydellä ”HH” -> ”TT”, joka on $c$ . Näin ollen pelin voiton odotusarvo on

$\begin{aligned} \frac{( 5x -3x^2 + 3y - 4y^2 )cb(c+1)}{1-a(b+1)(c+1)-bc} = \frac{ (5x -3x^2 + 3y - 4y^2)xy(1-x-y+xy)(2-x-y+xy) }{1-(x+y-2xy)(1+xy)(2-x-y+xy)-xy(1-x-y+xy)} \end{aligned}$

Kuvasta nähdään, että tämän maksimikohta joukossa $[0,1]^2$ on jossain $(0.7, 0.3)$ :n kohdilla:

Odotusarvo riippuu muuttujista $x$ ja $y$ . Kuvaaja ja tasa-arvo käyrä-kuvaaja.

Tässä javascript-funktiot odotusarvon ja sen gradientin laskemiseksi:

/*
(x(5x - 3x^2 + 3y-4y^2)y(1 - x - y + xy)(2 - x - y + xy))
/
(1 - xy(1 - x - y + xy)
- (x + y - 2xy) (1 + xy) (2 - x - y + xy))
, x\in[0,1], y\in [0,1]
*/

const f = (x, y) => {
    let g = 5*x - 3*x**2 + 3*y-4*y**2;
    let num = g*x*y*(1 - x - y + x*y)*(2 - x - y + x*y);
    let denom = 1 - x*y*(1 - x - y + x*y)
        - (x + y - 2*x*y)*(1 + x*y)*(2 - x - y + x*y);
    
    return num/denom;
};

const gradF = (x, y) => {
    let p1 = 5*x - 3*x**2 + 3*y-4*y**2;
    let p2 = x*y*(1-x-y+x*y); //= xy - x^2y - xy^2 + x^2y^2
    let p3 = 2 - x - y + x*y;
    let num = p1*p2*p3;
    let denom = 1 - x*y*(1 - x - y + x*y)
            - (x + y - 2*x*y)*(1 + x*y)*(2 - x - y + x*y);
    
    let dxp1 = 5 - 6*x;
    let dxp2 = y - 2*x*y - y**2 + 2*x*y**2;
    let dxp3 = -1+y;
    let dxnum = dxp1*p2*p3 + p1*dxp2*p3 + p1*p2*dxp3;
    let dxdenom = (y-2)*(y-1)**2 + 3*x**2*y*(1-3*y+2*y**2)
                + x*(2-8*y+14*y**2-6*y**3);
    
    let dyp1 = 3-8*y;
    let dyp2 = x - x**2 - 2*x*y + 2*x**2*y;
    let dyp3 = -1 + x;
    let dynum = dyp1*p2*p3 + p1*dyp2*p3 + p1*p2*dyp3;
    let dydenom = 2*(y-1) + x**2*(-4+14*y-9*y**2)
                + x*(5-8*y+3*y**2) + x**3*(1-6*y+6*y**2)
    
    return [
        (dxnum*denom-num*dxdenom)/denom**2,
        (dynum*denom-num*dydenom)/denom**2
    ];
    
};

Jyrkimmän nousun menetelmällä (gradient descent) tai muuten löydetään maksimi

$(x,y) = (0.71046, 0.28314)$

ja odotusarvo

$1.2863$ .

Eräs noppapeli

Pelaaja saa aluksi yhden nopan. Joka kierros pelaaja heittää kaikki noppansa ja menettää ne joiden osoittamaa arvoa tuli useampi kuin yksi. Kierroksen päätteeksi pelaaja saa aina yhden uuden nopan. Tavoite on saada seitsemän noppaa (tai yleisemmin $d+1$ noppaa, kun nopassa on $d$ tahkoa). Toisin sanoen peli päättyy, kun pelaajalla on kuusi noppaa ja niillä tulee jokaisella eri arvo. Mikä on yhden pelin kierrosten määrän ( $N$ ) odotusarvo?

Ratkaisu

Peli on Markovin ketju, jossa tilat ovat noppien määrät $1, 2, \dots, d+1$ . Meidän täytyy selvittää siirtymätodennäköisyydet näiden välillä. Pienille arvoille, kuten $d = 6$ , tämä voidaan tehdä tutkimalla kaikki mahdolliset heitot ja kirjaamalla kuinka moni niistä säilyttää kuinkakin monta noppaa. Seuraava Sage-koodi tekee tämän:

from itertools import product
from collections import Counter

def getTransitionsProbsBrute1(diceAmounts, dieFaces):
    n = dieFaces+1
    ret = [0]*n
    for dice in product(range(dieFaces), repeat=diceAmounts):
        keep = sum(x for x in Counter(dice).values() if x==1)
        #we're adding 1 die after round, but 1 is the
        #first state, so keep is the correct index
        ret[keep] += 1
    tot = dieFaces**diceAmounts
    return [x/tot for x in ret]

Laskentaa voidaan hieman nopeuttaa käyttämällä kombinaatioita (takaisin panolla):

from itertools import combinations_with_replacement as cmb_rep
from collections import Counter

def getType(dice):
    return list(Counter(dice).values())

def getTransitionsProbsBrute2(diceAmount, dieFaces):
    n = dieFaces+1
    ret = [0]*n
    for dice in cmb_rep(range(dieFaces), r=diceAmount):
        keep = sum(x for x in Counter(dice).values() if x==1)
        #multinomial of the type gives the amount
        #of orderings this corresponds to when account for all
        weight = multinomial(getType(dice))
        ret[keep] += weight
    tot = dieFaces**diceAmount
    return [x/tot for x in ret]

Tässä tarvittiin tietää kombinaatiosta sen tyyppi eli siinä esiintyvien lukujen esiintymien lukumäärät (koottuna vektoriksi).

Nyt voidaan muodostaa siirtymämatriisi ja käyttää tavanomaisia keinoja $\mathbb{E}[N]$ :n selvittämiseen:

def getTransitionMatrixBrute(dieFaces):
    arr = [getTransitionsProbsBrute2(i, dieFaces)
           for i in range(1, dieFaces+2)]
    return Matrix(arr)

def getFundamentalMatrix(pMat):
    n = pMat.dimensions()[0]-1
    arr = [[(1 if i==j else 0)-pMat[i][j]
            for j in range(n)]
           for i in range(n)]
    return Matrix(arr)**-1

def getExpectedGameLen(dieFaces):
    P = getTransitionMatrixBrute(dieFaces)
    fundMat = getFundamentalMatrix(P)
    return sum(fundMat[0])


print (getExpectedGameLen(6))

Ja näin saadaan tulos

$\begin{aligned} \mathbb{E}[N] = \frac{133191861}{12500} = 10655.34888 \end{aligned}$

Kombinaatioiden (eritoteen takaisinpanon kanssa) määrä kuitenkin kasvaa melko nopeasti, kun $d$ kasvaa. Edellä jo mainittua tyyppi-ideaa voidaan jatkojalostaa: se kuinka monta noppaa heittotuloksesta menetetään riippuu vain tyypistä (kaikki, joiden arvoa yli yksi kappale menetetään). Tyypit ovat noppien lukumäärän ositukset (paitsi viimeisen tilan ositus $[1,1,\dots,1]$ ei kelpaa, sillä se tarkoittaa $d+1$ eri arvoa, mutta nopassa on vain $d$ eri arvoa. (Tästä vielä huomio-osioissa.) Nyt täytyy enää laskea kuinka moni noppien heitto vastaa kutakin ositusta. Tätä on selvitetty koodin kommenteissa:

def getFactorOfType(t, dieFaces):
    #first choose a value for each number in the type
    ret = factorial(dieFaces)/factorial(dieFaces-len(t))
    #divide away the orderings in the type
    #(we need the type's type)
    ret /= factorialProd(getType(t))
    #now we can multiply by the total number of orderings
    ret *= multinomial(t)
    return ret

def getTransitionMatrix(dieFaces):
    n = dieFaces+1
    arr = [[0]*n for i in range(n)]
    for i in range(1, n+1):
        for t in Partitions(i):
            if (len(t)>dieFaces): continue
            toState = i-sum(x for x in t if x>1)
            weight = getFactorOfType(t, dieFaces)
            arr[i-1][toState] += weight
    for i in range(n):
        tot = dieFaces**(i+1)
        for j in range(n):
            arr[i][j] /= tot
    return Matrix(arr)

Tässä vielä lopullinen tyypeillä laskeva koodi kokonaisuudessaan ja taulukko tuloksesta muutamilla $d$ :n arvoilla:

from collections import Counter

def getType(dice):
    return list(Counter(dice).values())

def factorialProd(arr):
    return reduce(lambda acc,x: acc*factorial(x), arr, 1)

def getFactorOfType(t, dieFaces):
    ret = factorial(dieFaces)/factorial(dieFaces-len(t))
    ret /= factorialProd(getType(t))
    ret *= multinomial(t)
    return ret

def getTransitionMatrix(dieFaces):
    n = dieFaces+1
    arr = [[0]*n for i in range(n)]
    for i in range(1, n+1):
        for t in Partitions(i):
            if (len(t)>dieFaces): continue
            toState = i-sum(x for x in t if x>1)
            weight = getFactorOfType(t, dieFaces)
            arr[i-1][toState] += weight
    for i in range(n):
        tot = dieFaces**(i+1)
        for j in range(n):
            arr[i][j] /= tot
    return Matrix(arr)

def getFundamentalMatrix(pMat):
    n = pMat.dimensions()[0]-1
    arr = [[(1 if i==j else 0)-pMat[i][j]
            for j in range(n)]
           for i in range(n)]
    return Matrix(arr)**-1

def getExpectedGameLen(dieFaces):
    P = getTransitionMatrix(dieFaces)
    fundMat = getFundamentalMatrix(P)
    return sum(fundMat[0])


res = [[d, float(getExpectedGameLen(Integer(d)))]
      for d in range(1, 21)]
print (res)

d	E[N]
1	1
2	4
3	15
4	80.96296
5	718.61364
6	10655.34888
7	261903.04770
8	10636087.48690
9	713183947.85983
10	7.89467e+10
11	1.44259e+13
12	4.35102e+15
13	2.16594e+18
14	1.77942e+21
15	2.41246e+24
16	5.39710e+27
17	1.99232e+31
18	1.21348e+35
19	1.21944e+39
20	2.02174e+43

Huomioita

Viimeisen tilan siirtymiä ei tarvitsisi laskea (siinä mielessä, että peli jatkuisi) vaan se asetetaan absorboivaksi eikä sitä tarvita odotusarvon laskussa ollenkaan. Itse asiassa sen laskeminen on juuri kaikista matriisin riveistä vaativin, sillä tarvittavia objekteja (permutaatioita takaisinpanolla, kombinaatioita takaisin panolla tai osituksia) on eniten.
Myös ensimmäinen tila on käytännössä turha: yhtä noppaa on turha edes heittää, koska sitä ei voi menettää; ottaa vaan suoraan toisen nopan. Mutta pidetään se mukana yksinkertaisuuden vuoksi ja lasketaan pelin pituuteen mukaan myös nämä deterministiset askeleet.

Tehtäviä

Muokkaa koodia, niin että turhia viimeisen tilan siirtymiä ei lasketa. Aseta viimeiseen tilaan itsesiirtymä todennäköisyydellä 1 tai unohda koko viimeinen tila, sillä sitä ei laskuissa tarvita.
Laske $N$ :n varianssi. Vinkki: katso Wikipedian artikkeli.
Entä jos sovitaan, että pelaaja häviää pelin, mikäli hän jollain kierroksella menettää kaikki noppansa. Mikä on häviämisen todennäköisyys?
Voidaan sopia mitä erilaisimpia sääntöjä siitä miten pelaaja saa lisänopan /-noppia tai menettää niitä riippuen hänen heitostaan. Tutki jotain tällaista muokattua peliä.

Kaksi karsinaa

Kaikkihan tietävät, että ympyrä on paras muoto kun halutaan aidata tietyn suuruinen ala käyttäen mahdollisimman vähän aitaa (ks. isoperimetrinen epäyhtälö). Mutta entäpä, jos onkin tehtävä kaksi karsinaa, jotka voivat käyttää yhteistä aitaa? Entä yleisemmin $n$ karsinaa?

Oletetaan että yhden karsinan ala on $A = 1$ ja yritetään löytää mahdollisimman pieni piirinen aitaus.

Ensimmäinen vaihtoehto, joka tulee mieleen on kaiketi ”tavallinen” suorakaiteen mallinen, jossa on yksi väliaita:

Optimoidaan piiri ja saadaan $x = \frac{\sqrt{3}}{2} = 0.866$ ja $p=2\sqrt{3} + \frac{6}{\sqrt 3} = 6.9282$ .

Mutta onko tämä paras mahdollinen? Koska ympyrä on paras ratkaisu yhdelle karsinalle, niin kokeillaanpa jakaa ympyrä kahtia:

Saadaan $r = \sqrt{\frac{2}{\pi}}$ ja $p = 2\pi r + 2r = 2(\pi+1) \sqrt{\frac{2}{\pi}} = 6.609$ . Siis parempi kuin suorakaide-ratkaisu.

Mutta entäpä jos yhdistettäisiin hieman kumpaakin: laitetaan keskelle suorakaide ja päihin puoliympyrät (ja tietenkin keskelle jakoaita) ja optimoidaan tämä muoto:

Optimiksi saadaan $r = \sqrt{\frac{2}{2+\pi}}=0.6237$ ja $p=2\sqrt{4+2\pi}=6.413$ . Löydettiin siis halkaistua ympyrääkin parempi ratkaisu.

Toinen tapa yrittää käyttää ympyrää olisi ollut tehdä kaksi täysin erillistä ympyräkarsinaa. Tällöin yhdellä on pienempi säde ( $r=\sqrt{\frac{1}{\pi}}$ ) mutta piiri on $p = 2\times 2\pi r = 4\sqrt \pi = 7.089 > 7$ ja $p=7$ saadaan jo siitä (optimoimattomasta) ratkaisusta, että laitetaan kaksi neliötä vierekkäin.

Olemme tähän asti ajatelleet, että aitauksen kuuluisi olla konveksi (~~tietenkin kummankin karsinan pitää olla konveksi~~, mutta että koko rakennelman?!?!?). Eihän sen täydykään: otetaan vain kaksi sopivan kokoista ympyrää ja läimäytetään ne yhteen. Ei keskikohdasta, vaan optimoidaan tämä kohta.

Tämä onkin niinsanottu tuplakupla ratkaisu ja myös todistetusti (tai itseasiassa 2d-versio on tämä) ongelman optimi ratkaisu, joten optimi on $p = 6.3591$ .

Huomioita

Jos karsinat eivät olisikaan samankokoiset, niin tuplakupla ratkaisussa jakoaita ei olekaan jana, vaan ympyrän kaari (ks. tuplakuplan määritelmä), joten karsinatkaan eivät välttämättä ole konvekseja. Jakokaari määräytyy siitä, että kaarien täytyy kohdata toisensa 120 asteen kulmassa eli niiden tangentit jakavat täysikulman kolmeen yhtäsuureen osaan.
Tarkka ratkaisu, joka tästä 120 asteen vaatimuksesta nähdään on $\alpha = \frac{\pi}{3}$ , $r = \frac{1}{\sqrt{\frac{2\pi}{3} + \frac{\sqrt 3}{4}}}$ ja $p=\frac{\frac{8\pi}{3} +\sqrt 3}{ \sqrt { \frac{2\pi}{3} + \frac{\sqrt 3}{4} }}$

Värisuorien todennäköisyyksistä

Jos tavallisesta 52 kortin korttipakasta nostetaan satunnainen 7 kortin käsi, mikä on todennäköisyys, että käsi sisältää (ainakin) $r$ peräkkäistä saman maan korttia?

Merkitään $A_{i, j} =$ ”käsi sisältää kortit $(i, j), (i+1, j), \dots, (i+r-1, j)$ ”, arvoille $i=1,2,\dots, 13-r+1$ ja $j=$ ♠, ♥, ♣, ♦. Merkitään näiden kaikkien tapahtumien joukkoa $\cal{A}$ :lla. Kysytty todennäköisyys on tällöin

$\begin{aligned} \mathbb{P} \left( \bigcup_{A\in\cal{A}} A \right) \end{aligned} .$

Inkluusio-eksluusion periaatteen nojalla tämä voidaan laskea

$\begin{aligned} \mathbb{P} \left( \bigcup_{A\in\cal{A}} A \right) = \sum_{j=1}^{|\cal{A}|} (-1)^{j+1} \sum_{ \substack{ I\subset \cal{A} \\ |I| = j}} \mathbb{P} \left( \bigcap_{A\in I} A \right) \end{aligned}$

Merkitään tapahtumalle $A \in \cal{A}$ symbolilla $\bar {A}$ niiden korttien joukkoa, jotka siinä vaaditaan kädessä esiintymään. Huomataan, että tämä relaatio on siinä mielessä käänteinen, että kun tapahtumia $A$ leikataan, vastaa tämä joukkojen $\bar{A}$ yhdistettä. (Leikkautapahtuma tapahtuu jos ja vain jos käsi sisältää kaikki vaaditut kortit.)

Todennäköisyys $\begin{aligned} \mathbb{P} \left( \bigcap_{A\in I} A \right) \end{aligned}$ riippuu vain vaadittujen korttien unionin koosta $t = \left( \bigcup_{A\in I} \bar{A} \right)$ sillä siinä vaaditaan leikkauksen korttien esiintyvän kädessä eikä sillä ole väliä mitkä kortit ne ovat. Hypergeometrisen jakauman mukaan tämä todennäköisyys on

$p_t := \begin{aligned} \frac{ {{t} \choose {t}} {{52-t} \choose {7-t}} }{ {{52} \choose {7}} } = \frac{ {{52-t} \choose {7-t}} }{ {{52} \choose {7}} } \end{aligned}$

Täytyy siis selvittää kuinka monta $t$ :n kokoista unionia $\bigcup_{I\subset \cal{A}} \bar{A}$ tasolla $|I|=j$ on. Merkitään tätä $c_{j, t}$ .

Koska $p_t = 0$ , kun $t>7$ , niin tarvitaan vain arvot, joissa $t\leq 7$ . Lisäksi, koska tason $j$ unioni koostuu $j$ joukosta ja ensimmäinen tuo $r$ alkiota ja seuraavat jokainen ainakin yhden lisää (joukot $\bar{A}$ ovat pötköjä, jotka menevät maksimissaan $r-1$ :n verran päällekkäin), niin saadaan myös yläraja $j\leq 7-r+1$ .

Lukujen $c_{j, t}$ laskeminen voidaan tehdä brute-forcena. Tapaus $r=2$ on melko raskahko, sillä siinä täytyy laskea arvoon $j=6$ asti ja ${{4\times 12}\choose{6}} = 12 271 512$ . Tapaus $r=2$ on kuitenkin toisella tapaa yksinkertaisempi ja sen voi ratkaista tutkimalla kuinka monella tapaa neljän 13-ketjun graafista voidaan valita aligraafi, joka on kokoelma ketjuja (nämä aliketjujen pituudet vastaavat sitä tyyppiä millainen yhdiste $A$ ’ista muodostuu). Tässä joukot $A$ vastaavat graafin sivuja ja se että joukko on yhdisteessä mukana vastaa sitä, että sivu on aligraafissa mukana.

Saadaan seuraavat tulokset:

r	P(väh. r pituinen värisuora)	approks
2	686898/1194505	0.575
3	1074209/16723070	0.0642
4	151/30940	0.00488
5	407/1454180	0.000280
6	361/33446140	0.0000108
7	1/4778020	2.093e-7

Javascript-koodi:

function binCoeff(n, k) {
    if (k < 0 || k > n) return 0;
    if (k === 0 || k === n) return 1;
    let ret = 1;
    for (let i=0; i<Math.min(k, n-k); i++){
        ret = ret*(n-i)/(i+1);
    }
    return ret;
}

function* generCombinations(arr, r) {
    const result = [];
    result.length = r;
    function* makeThem(len, start) {
        if(len===0) {
            yield result.slice();
        } else {
            for (var i=start; i<=arr.length-len; i++) {
                result[result.length-len] = arr[i];
                yield* makeThem(len-1, i+1);
            }
        }
    }
    yield* makeThem(r, 0);
}

function linkBruteGeneral(j, k, m, linkLen) {
    let ret = {};
    let runStarts = [];
    for (let i=0; i<k; i++) {
        runStarts = [...runStarts,
...new Array(m-(linkLen-1)).fill(null).map((_,z)=>[z, i])];
    }
    for (let comb of generCombinations(runStarts, j)) {
        let cardSet = new Set();
        for (let card of comb) {
            for (let follow=0; follow<linkLen; follow++) {
                cardSet.add((card[0]+follow)+","+card[1]);
            }
        }
        let key = cardSet.size;
        if (!(key in ret)) ret[key] = 0;
        ret[key] += 1;
    }
    return ret;
}

function calcProb(ds) {
    const calcPart = (j) => {
        let s = 0;
        let d = ds[j];
        for (let k in d) {
            if (k>7) continue;
            s += d[k]*binCoeff(52-k, 7-k);
        }
        return s;
    };
    
    let ret = 0;
    for (let i=1; i<=ds.length; i++) {
        ret += (i%2?1:-1)*calcPart(i);
    }
    return ret;
}

function makeTheFormula(ds) {
    const makePart = (j) => {
        let f = "(";
        let d = ds[j];
        let isFirst = true;
        for (let k in d) {
            if (k>7) continue;
            if (isFirst) {
                isFirst = false;
            } else {
                f += "+";
            }
            f += d[k]+`*binomial(${52-k}, ${7-k})`;
        }
        return f+")";
    };
    
    let ret = "";
    for (let i=1; i<=ds.length; i++) {
        ret += (i===1?'':(i%2?'+':'-')) + makePart(i);
    }
    return ret;
}

let testK = 4;
let testM = 13;
let testR = 3;

let maxNeedJ = 7-testR+1;

let ds = [];
for (let j=0; j<=maxNeedJ; j++) {
    ds.push(linkBruteGeneral(j, testK, testM, testR));
}

console.log(calcProb(ds));
console.log(makeTheFormula(ds));

Koodi toiselle tavalle tapauksessa r=2:

/** list of partitions of n to at most maxPartsN parts that are at most maxSize */
function getPartitions(n, maxPartsN, maxSize) {
    if (n===0) return [[]];
    let canMakeMax = maxPartsN*maxSize;
    if (n>canMakeMax) return [];
    if (n===canMakeMax) return [new Array(maxPartsN).fill(maxSize)];
    let ret = [];
    for (let x=Math.min(n, maxSize); x>=0; x--) {
        let toConcat = getPartitions(n-x, maxPartsN-1, x).map(p=>[x].concat(p));
        ret = ret.concat(toConcat);
    }
    return ret
}

function factorial(n) {
    let ret = 1;
    for (let i=2; i<=n; i++) ret *= i;
    return ret;
}

function binCoeff(n, k) {
    if (k < 0 || k > n) return 0;
    if (k === 0 || k === n) return 1;
    let ret = 1;
    for (let i=0; i<Math.min(k, n-k); i++){
        ret = ret*(n-i)/(i+1);
    }
    return ret;
}

/** In how many ways  can subchains be fitted into chains.
* Chain length is the number of edges in it.
*/
const linkageMemo = {};
function countLinkages(chains, subchains) {
    //debugger;
    let memoKey = chains.join(",")+";"+subchains.join(",");
    if (memoKey in linkageMemo) return linkageMemo[memoKey];
    if (subchains.length===0) return 1;
    let s = 0;
    let currSub = subchains[0];
    let restSubs = subchains.slice(1);
    for (let cI=0; cI<chains.length; cI++) {
        let cLen = chains[cI];
        let maxInd = cLen-currSub;
        for (let ind=0; ind<=maxInd; ind++) {
            let restChains = chains.slice(0, cI).concat(chains.slice(cI+1));
            if (ind>1) restChains.push(ind-1);
            if (ind<maxInd-1) restChains.push(maxInd-ind-1);
            restChains.sort((a,b)=>b-a);
            s += countLinkages(restChains, restSubs);
        }
    }
    linkageMemo[memoKey] = s;
    return s;
}


function permuFactor(arr) {
    let counts = {};
    for (let x of arr) {
        if (!(x in counts)) counts[x] = 0;
        counts[x] += 1;
    }
    let ret = 1;
    for (let val of Object.values(counts)) ret *= factorial(val);
    return ret;
}

function countAllLinkages(j, k, m) {
    let chains = new Array(k).fill(m-1);
    let linksN = k*(m-1);
    let partis = getPartitions(j, linksN, linksN);
    let ret = {};
    for (let parti of partis) {
        let key = parti.reduce((a,b)=>a+b+1,0);
        if (!(key in ret)) ret[key] = 0;
        ret[key] += countLinkages(chains, parti)/permuFactor(parti);
    }
    return ret;
}


/* Given the amounts of linkages calculate the numerator of probability of having a 2-run
* ds = [
    {
      "0": 1
     },
     {
      "2": 48
     },
     {
      "3": 44,
      "4": 1084
     },
     {
      "4": 40,
      "5": 1944,
      "6": 15312
     }, ...
]
*/
function calcProb(ds) {
    const calcPart = (j) => {
        let s = 0;
        let d = ds[j];
        for (let k in d) {
            if (k>7) continue;
            s += d[k]*binCoeff(52-k, 7-k);
        }
        return s;
    };
    
    let ret = 0;
    for (let i=1; i<=6; i++) {
        ret += (i%2?1:-1)*calcPart(i);
    }
    return ret;
}

function makeTheFormula(ds) {
    const makePart = (j) => {
        let f = "(";
        let d = ds[j];
        let isFirst = true;
        for (let k in d) {
            if (k>7) continue;
            if (isFirst) {
                isFirst = false;
            } else {
                f += "+";
            }
            f += d[k]+`*binomial(${52-k}, ${7-k})`;
        }
        return f+")";
    };
    
    let ret = "";
    for (let i=1; i<=6; i++) {
        ret += (i===1?'':(i%2?'+':'-')) + makePart(i);
    }
    return ret;
}


let testK = 4;
let testM = 13;
let ds = [];
for (let j=0; j<=6; j++) {
    ds.push((countAllLinkages(j, testK, testM)));
}

console.log(makeTheFormula(ds));
console.log(calcProb(ds));

$\begin{aligned} \end{aligned}$

Ympyrät tasossa

Kysymys

Olkoon tasossa $n$ toisiaan leikkaamatonta $1$ -säteistä ympyrää. (Ympyrällä tarkoitetaan sen kaarta.) Mikä on todennäköisyys, että kun valitaan näiltä piste satunnaisesti, tästä pisteestä ei näy muita ympyröitä?

Ympyrän 2 pisteestä $A$ näkyy kaikki muut ympyrät. Pisteestä $B$ taas ei näy mikään toinen ympyrä, sillä ne ovat kaikki $B$ :hen piirretyn tangenttisuoran ”väärällä” puolella.

Kokeile:

https://Invisible-Circles–minkkilaukku2.repl.co

Ratkaisu

Vastaus on $\begin{aligned} \frac{1}{n} \end{aligned}$ .

Ja tämä siis aivan riippumatta ympyröiden sijainneista (paitsi eivät saa leikata toisiaan, kuten sovittiin).

Todistuksen runko

Ympyröiden konveksiverho $C$ . Kaariosuudet keltaisella ja janaosuudet ruskealla. Vihreät pisteet ympyröillä ovat niiden välisten tangenttijanojen päätepisteitä, ”kaikkein uloimmaiset” tangenttijanat ovat mukana $C$ :ssä.

Olkoon $C_0$ ympyröiden yhdisteen konveksiverho.
Joukon $C_0$ reuna $C$ on janoista ja ympyränkaarista koostuva derivoituva Jordanin käyrä.
Ympyrän piste $P$ kuuluu $C$ :hen täsmälleen silloin, kun se on sellainen piste, josta ei näy mikään muu ympyrä. (Pois lukien äärellisen monta pistettä, jotka ovat $C$ :n janojen päätepisteitä: janat ovat ympyröiden välisiä tangentteja, joten niiden päätepisteet leikkaavat kahta ympyrää, joten niistä on näköyhteys. Näiden joukko on kuitenkin äärellisenä nollamittainen eikä vaikuta todennäköisyyteen.)
Käyrän $C$ kokonaiskaarevuus on $\begin{aligned} \int_{a}^b \kappa (s) ds = 2\pi \end{aligned}$ , sillä kierrosluku on $1$ .
Toisaalta $\begin{aligned} \int_{a}^b \kappa (s) ds \end{aligned}$ on käyrällä $C$ olevien ympyränkaarien yhteenlaskettu mitta, sillä janaosuudella kaarevuus $\kappa = 0$ ja kaariosuudella $\kappa = \frac{1}{1} = 1$ , sillä jokaisen ympyrän säde on $1$ (ks. kaarevuudesta Wikipediassa).
Siis suotuisan osan mitta on $2\pi$ . Kaikkien ympyröiden mitta on $2\pi n$ , joten väite seuraa.

Huomioita

Yleistyy kolmiulotteiseksi: pallot 3D-avaruudessa. Gauss-Bonnet:n lause.
Jos ympyröiden säteet ovat eri suuruisia, ympyröiden paikat vaikuttavat tulokseen. Tämä johtuu siitä, yo. integraalissa kaarevuus ei ole joka ympyrällä vakio vaan tulos riippuu siitä millaisia ympyröitä ulkokaaressa on mukana minkäkin verran. Ks. esimerkkikuva alla.

Erisäteisille ympyröille voi käydä näin. Selvästi jälkimmäisessä tapauksessa suotuisaa mittaa on vähemmän kuin ensimmäisessä.

Hedetniemen matriisisumma

Kaikkihan tietätävät että graafin solmujen välillä olevien $q$ -kävelyjen lukumäärät saadaan korottamalla graafin vierekkäisyysmatriisi potenssiin $q$ . Mutta entä jos matriisissa käytetään kaarien painotuksia ja matriisitulossa rivin ja sarakkeen pistetulon paikalla alkioiden summien minimiä? Tämä on Hedetniemen matriisisumma.

Määritelmä

Matriisien $A$ (kokoa $m\times n$ ) ja $B$ (kokoa $n\times p$ ) Hedetniemen summa $A \ddagger B$ on $m \times p$ -matriisi $C$ , jonka $(i, j)$ -alkio on

$\begin{aligned} c_{ij} = \min_{ k \in \{1, \dots, n\} } a_{ik}+b_{kj} \end{aligned}$

Huom. Sallimme matriisin alkioksi myös plus äärettömän $\infty$ . Määrittelemme $\infty + x = x + \infty = \infty$ ja $\min(\infty, x) = x$ kaikille luvuille $x$ ja myös tapauksessa $x = \infty$ .

Esimerkki

Hedetniemen summan alkion $(3, 4)$ muodostuminen korostettuna. Matriisi $A$ on alla esiintyvän graafin kaarien painomatriisi.

Hedetniemen summan alkion $(3, 4)$ muodostuminen korostettuna. Matriisi $A$ on alla esiintyvän graafin kaarien painomatriisi.

Mihin tätä summaa sitten käytetään? Sen avulla voidaan selvittää lyhyimmät reitit kaikkien solmuparien välillä graafissa, jonka kaarille on annettu ei-negatiiviset painokertoimet (etäisyydet). Muodostetaan graafille $G=(\{v_1, v_2 \dots, v_n\}, E)$ kaarien painomatriisi $A$ , jossa alkio $a_{ij}$ , $i \neq j$ on $v_i$ :n ja $v_j$ :n välisen kaaren paino tai $\infty$ , jos solmujen välillä ei ole kaarta. Diagonaalialkiot $a_{ii}$ asetetaan nollaksi, sillä solmusta itseensä on nollan askeleen reitti, jonka pituus (=sen käyttämien kaarien painojen summa) on nolla. Oletamme että graafi on yksinkertainen eli sillä ei ole kaaria solmusta itseensä eikä useampia kaaria kahden solmun välillä. Tämä on luonnollinen oletus kun haluamme selvittää lyhyimpiä reittejä, sillä luuppia solmusta itseensä ei kannata reitissä ikinä käyttää ja useammasta kaaresta solmujen välillä kannattaa aina valita se, jolla on pienin paino.

Kaaret ajatellaan suunnaatuiksi, mutta suuntaamattomassa tapauksessa ajatellaan, että kaari on kumpaankin suuntaan olemassa (samalla painolla). Suuntaamattomassa tapauksessa matriisi $A$ on siis symmetrinen.

Suuntaamaton graafi ja sen kaarien painomatriisi $A$ . Ensimmäinen rivi ja sarake ovat indeksejä.

Lasketaan matriisin $A$ iteroituja Hedetniemen summia $A, A^2, A^3, \dots$ . Merkitsemme siis $A^2 = A \ddagger A$ (tämä ei sotkeutune tavalliseen matriisituloon, jota ei tässä postauksessa esiinny). Iteraation $A^{t}$ alkio $a_{ij}^t$ kertoo lyhyimmän $t-1$ :n askeleen reitin pituuden solmusta $v_i$ solmuun $v_j$ . Koska graafi on äärellinen, käy jostakin $t$ :n arvosta $t_1$ lähtien niin, että $A^{t_1} = A^{t_1+1} = A^{t_1+2} = \dots$ eli jono stabiloituu. Ylläolevalle esimerkille

Hedetniemen matriisisumma-iteraatiot edellä olleen graafin kaarien painomatriisille. Jono stabiloituu arvosta $t_1 = 7$ lähtien. Kuten voidaan todeta, eniten askelia vievä lyhyin reitti (solmujen $2$ ja $5$ välillä) on 6 askelta: 2-0-1-3-4-6-5 ja sen pituus on $9 (=2+1+2+1+2+1)$ . Se käykin kaikki graafin solmut läpi, joten tämä on maksimitapaus.

Hedetniemen matriisisumma-iteraatiot edellä olleen graafin kaarien painomatriisille. Jono stabiloituu arvosta $t_1 = 7$ lähtien. Kuten voidaan todeta, eniten askelia vievä lyhyin reitti (solmujen $2$ ja $5$ välillä) on 6 askelta: 2-0-1-3-4-6-5 ja sen pituus on $9 (=2+1+2+1+2+1)$ . Se käykin kaikki graafin solmut läpi, joten tämä on maksimitapaus.

Reitin selvitys

Lyhyimmän reitin pituus on luettavissa matriisin $A^{t_1}$ alkiosta, mutta kuinka saamme tiedon mikä tuo reitti on? Se voidaan selvittää solmu kerrallaan lähtemällä päätepisteestä ja ratkaisemalla mikä sitä täytyy reitillä edeltää. Otetaan esimerkiksi edellä olleen graafin solmut $0$ ja $6$ . Matriisista $A^7$ nähdään, että lyhyimmän reitin pituus on $a_{60}^7 = 6$ . Tutkitaan nyt päätepisteen eli solmun $6$ naapureita ( $k= 4, \text{ ja } 5$ ). Se kummasta kutoseen on tultu, täytyy toteuttaa yhtälö, että lyhyin reitti nollasta siihen on $6 - a_{k6}$ . Koska solmusta $4$ tulee 2:n painoinen kaari ja lyhyin reitti nollasta solmuun $4$ on $A^7$ :n mukaan pituudeltaan 4, niin valitaan solmu $4$ . Jatketaan nyt solmusta $4$ ja etsitään sen edeltäjä. Näin jatketaan kunnes päästään alkupisteeseen ja reitti on selvitetty.

Reitin selvityksen kaksi ensimmäistä askelta. Loput menevät vastaavasti.

Huomioita

Jos matriisin jää äärettömyyksiä jonon stabiloiduttua, tarkoittaa se että graafi on epäyhtenäinen: jostain solmusta ei ole mitään reittiä johonkin toiseen solmuun.
Stabiloituminen vie korkeintaan $|V|-1$ askelta, sillä lyhyin reitti ei vieraile missään solmussa kuin korkeintaan kerran.
Pienempiä (ennen stabiloitumista) iterantteja voi käyttää askelten määrän ollessa rajoitettu, sillä ne tosiaan kertovat sen hetkisen lyhyimmän etäisyyden kun käytetään korkeintaan $t$ askelta. (Jos haluaisi käyttää tasan $t$ askelta sen voisi varmaan toteuttaa asettamalla diagonaalialkiot äärettömiksi, jolloin solmussa ei ole luvallista pysyä. ???)
Algoritmin kehittäjä on Stephen Hedetniemi. Lisätietoa historiasta Seuran artikkelissa. Hedetniemen nimissä on myös graafien tensoritulon väritykseen liittyvä konjektuuri, joka ratkesi aivan tässä viime aikoina kielteisesti eli siihen löytyi vastaesimerkki: Yaroslav Shitov, Counterexamples to Hedetniemi’s conjecture.

Ohjelmakoodit (Python)

INFTY = 2**56 #number larger than any other occuring one

def hedetniemiMatrixSum(a, b):
    m = len(a)
    n = len(b)
    p = len(b[0])
    return [[min(a[i][k] + b[k][j] for k in range(n))
             for j in range(p)]
            for i in range(m)]


def findStableHedetniemiSum(a):
    n = len(a)
    prev = a
    b = a
    counter = 0
    while counter<n:
        b = hedetniemiMatrixSum(b, a)
        if b == prev: break
        prev = b
    return b
    

def findPath(start, end, minDMat, a):
    """
       start: index of the start node
       end: index of the target node
       minDMat: the stabilized matrix
                containing the minimum paths lenghts
       a: the weighted adjacency matrix
    """
    n = len(a)
    path = [end]
    dist = minDMat[start][end]
    if dist>=INFTY: return None #no path exists
    curr = end
    def findPrev():
        for i in range(n):
            if i==curr: continue
            if dist-a[i][curr] == minDMat[start][i]: return i
    counter = 0
    while curr != start and counter<n:
        prev = findPrev()
        dist -= a[prev][curr]
        curr = prev
        path.append(curr)
    return path[::-1]

#the example matrix
a = [
    [0,1,2,INFTY,INFTY,8,INFTY],
    [1,0,4,2,INFTY,INFTY,INFTY],
    [2,4,0,INFTY,7,INFTY,INFTY],
    [INFTY,2,INFTY,0,1,INFTY,INFTY],
    [INFTY,INFTY,7,1,0,INFTY,2],
    [8,INFTY,INFTY,INFTY,INFTY,0,1],
    [INFTY,INFTY,INFTY,INFTY,2,1,0]
]
b = findStableHedetniemiSum(a)
print b
print findPath(0, 6, b, a)

Rauhalliset ratsut

Kysymys:

Kuinka monella tavalla voidaan $n\times n$ -laudalle asettaa 4 ratsua, siten että mikään ei uhkaa toista? Kaikki ratsut ovat identtisiä ja vihollisia keskenään.

Ratkaisu:

Merkitään $V = [1..n]^2$ eli kaikkien laudan ruutujen joukko. Kaikki mahdolliset neljän ratsun asettelut ovat nyt joukko

$\begin{aligned} S=\{(v_1, v_2, v_3, v_4) \in V^4 \text{ } | \text{ } v_i \neq v_j \text{, kun } i \neq j \} \end{aligned}.$

Määritellään kaarijoukko $E$ kuvastamaan sitä mihin ruutuun kustakin ruudusta ratsu voi liikkua, eli mitä kaikkia ruutuja se uhkaa. (Huom. ratsuissa on se mukava juttu, että ne eivät välitä laudan muista nappuloista vaan voivat hypätä näiden yli.) Näin saadaan $n\times n$ –ratsun graaf i.

Ratsun liikkumismahdollisuudet ovat 1 ruutu vaakasuunnassa ja 2 ruutua pystysuunnassa, tai kääntäen.

Tehdään tässä välissä sellainen huomio, että ratsun graafilla ei ole kolmioita: mitkään kolme eri ratsua (kun ovat laudalla eri ruuduissa) eivät voi uhata kaikki toisiaan. Tämä johtuu siitä, että ratsu vaihtaa aina liikkuessaan väriä: se liikkuu yhteensä kolme askelta mustalta valkealle / valkealta mustalle. Kolmesta ratsusta vähintään kaksi on samalla värillä, joten ne eivät voi uhata toisiaan. Ratsun graafi on juuri tämän värin vaihtamisen takia kaksijakoinen (valkeat ja mustat ruudut).

Määritellään joukot $\begin{aligned} A_{ij} = \{ (v_1, v_2, v_3, v_4) \in S \text{ } | \text{ } v_i \text{ ja } v_j \text{ uhkaavat toisiaan} \} \end{aligned}$ . Tarvitsemme joukkoja $A_{12}, A_{13}, A_{14}, A_{23}, A_{24}$ ja $A_{34}$ , sillä kysytty lukumäärä on joukon $S \setminus \cup_{ij\in I} A_{ij}$ koko. Indeksijoukko $I := \{ 12, 13, 14, 23, 24, 34\}$ (huom. merkinnät 12,… eivät aiheuta sekaannusta, sillä luvut pysyvät alle kymmenen). Voimme laskea inkluusio-eksluusiolla:

$\begin{aligned} \left |S\setminus \bigcup_{ij\in I} A_{ij} \right | = \sum_{J\subset I} (-1)^{|J|} \left|\bigcap_{ij \in J} A_{ij} \right| \end{aligned},$

missä leikkaus tyhjän joukon yli tarkoittaa koko joukkoa $S$ . Tehtävän ratkaisemiseksi meidän on siis laskettava kaikkien erilaisten leikkausten $\cap_{J} A_{ij}$ koot. Monet näistä ovat symmetrian nojalla samoja ja osa graafin kolmio-vapauden takia mahdottomia. Ne jakautuvat seuraaviin luokkiin:

Erilaiset leikkaustyypit. Solmut ovat indeksejä $i$ ja $j$ , kaari näiden välillä tarkoittaa että $A_{ij}$ on leikkauksessa mukana. Viereen merkitty kuinka monta kutakin leikkaustyyppiä on (symmetria, kuvassa on aina vain esimerkki numerointi solmuille). Taso, eli kuinka monta joukkoa leikkauksessa on, merkitty alle. Huomaa että tason $t$ kaikkinainen lukumäärä on ${{6}\choose{t}}$ : leikkaukseen valitaan $t$ joukkoa kaikista kuudesta. Kolmion sisältävät ovat mahdottomia eli niitä vastaavat leikkaukset ovat tyhjiä.

Merkitään

$\begin{aligned} a_1 =& |A_{12}| = |A_{13}| = \dots = |A_{34}| \\ a_{21} =& |A_{12} \cap A_{13}| = |A_{13} \cap A_{14}| = \dots = |A_{14} \cap A_{24}| \\ a_{22} =& |A_{12} \cap A_{34}| = |A_{13} \cap A_{24}| = |A_{14} \cap A_{23}| \\ a_{31} =& |A_{12} \cap A_{13} \cap A_{14} | = \dots = |A_{14} \cap A_{24} \cap A_{34} | \\ a_{32} =& |A_{12} \cap A_{23} \cap A_{34} | = \dots \\ a_{4} =& |A_{12} \cap A_{23} \cap A_{34} \cap A_{14} | = \dots \end{aligned}$

Siis $a_1 =$ kaaret (ja kaksi muuta saa olla mitä vain muita solmuja), $a_{21} =$ 2-ketjut (ja viimeinen saa olla mikä vain muu solmu), $a_{22} =$ erilliset kaaret, $a_{31} =$ kaikki yhden naapureita, $a_{32} =$ 4-ketjut ja $a_{4} =$ 4-syklit.

Tällöin kysytty lukumäärä on

$\begin{aligned} \frac{1}{24}(n^2(n^2-1)(n^2-2)(n^2-3) - 4a_1 + 12a_{21} + 3a_{22} - 4a_{31} - 12a_{32} + 3a_{4}) \end{aligned}$

Tässä on sijoitettu $|S| = n^2(n^2-1)(n^2-2)(n^2-3)$ ja jakaja $24=4!$ tulee siitä, että ratsujen järjestyksellä ei ole kysymyksessä väliä, mutta me laskimme järjestettyjä nelikoita.

Tällaisten konfiguraatioiden laskemista graafilla käsittelimme viime kertojen postauksissa: Erillisten kaariparien laskeminen ja Graafin naapuruus-polynomeja. Meillä oli apuna graafin naapuruus-polynomit. Koitetaan siis selvittää ne ratsun $n\times n$ -graafille. Laskeminen eri arvoille paljastaa melko nopeasti säännönmukaisuuden, jonka voi sitten kuvaa katsomalla perustella. Polynomi $p_1$ on helppo: nurkilla on jokaisella 2 naapuria, näiden viereisillä ( $8$ :lla) reunaruuduilla 3, muilla ( $4(n-4)$ ):lla reunaruuduilla 4. Toisella rinkulalla käy näin: nurkat: 4, muut reunat ( $4(n-4)$ ): 6. Sitä sisemmillä on kaikilla täydet 8 naapuria. Saamme siis, kun $n\geq 5$

$\begin{aligned} p_1(x) = 4x^2 + 8x^3 + 4(n-3)x^4 + 4(n-4)x^6 + (n-4)^2x^8 \end{aligned}$

Pienemmille $n$ :n arvoille tämä ei toimi, mutta niille koko ongelma voidaan laskea brute-forcena.

Sitten polynomi $p_2$ . Tämä vaatii hieman enemmän pähkäilyä, mutta tapaus $8 \times 8$ oli meillä jo edellisessä postauksessa esimerkkinä. Itse asiassa tuo tapaus on juuri viimeinen, jossa yleinen kaava ei tule vielä käytäntöön. Arvoille $n\geq 9$ pätee

$p_2(y_2, y_3, y_4, y_6, y_8) =\\ 4y_6^2 \text{ } + \text{ } 8y_4y_6y_8 \text{ } + \text{ } 8y_3y_6^2y_8 \text{ } + \text{ } 8y_4y_6y_8^2 \text{ } + \text{ } 4(n-8)y_6^2y_8^2 \text{ } + \text{ } 4y_4^2y_8^2 \text{ } + \text{ } 8y_2y_4^2y_6y_8^2 \text{ } + \text{ } 8y_3y_4y_6y_8^3 \text{ } + \text{ } 4(n-8)y_4^2y_8^4 \text{ } + \text{ } 4y_3^2y_4^2y_6^2y_8^2 \text{ } + \text{ } 8y_4^3y_6^2y_8^3 \text{ } + \text{ } 4(n-8)y_4^2y_6^2y_8^4 \text{ } + \text{ } 4y_6^4y_8^4 \text{ } + \text{ } 4(n-8)y_6^2y_8^6 \text{ } + \text{ } (n-8)^2y_8^8$

Lisäksi tarvitsimme vielä polynomin $p_E$ . Se saadaan, mikäli $n \geq 7$ , kaavalla

$\begin{aligned} p_E(x) = 8 x^6 + 16 x^7 + 8 x^8 + 8(n-5)x^9 + 8x^{10} + 8(n-3)x^{11} + (16(n-6)+8)x^{13} + 4(n-5)(n-6)x^{15} \end{aligned}$

Ainoa tapaus, jota emme $a$ ’itten laskemisesta vielä käsitelleet aimmissa postauksissa on 4-syklit eli $a_4$ . Mutta näiden lukumäärälle löytyy kaava mathworldista: Jos $n\geq 4$ , niin $a_4 = 16(n^2-18n+26)$ , muuten $0$ . (Meidän täytyy kertoa mathworldin kaava $8$ :lla, sillä tutkimme järjestettyjä nelikoita.)

Huomataan, että, kun $n \geq 9$ , laskenta-algoritmit tuottavat $n$ :stä riippuvan, astetta $8$ olevan polynomin, joten sen kertoimet voidaan selvittää laskemalla interpolaatio-polynomi tarpeeksi monelle pisteelle. Saadaan

$\begin{aligned} \frac{1}{24}(n^8 - 54n^6 + 144n^5 + 1019n^4 - 5232n^3 - 2022n^2+51120n - 77184) \end{aligned}$

Huomataan, että tämä kaava toimii itse asiassa, kun $n \geq 6$ . Pienemmät arvot $1 \leq n \leq 5$ eivät noudata tätä kaavaa, mutta niille voidaan keksiä kaava

$\begin{aligned} \frac{1}{6} (723 n^4 - 6869 n^3 + 23187 n^2 - 32317 n + 15276) \end{aligned}.$

ja näin on ratkaisu saatu kahdessa palassa määrättyä.

Huomoita

Yleinen ongelma, josta tämä on esimerkki on graafin riippumattomien joukkojen numerointi.
Tämä kyseinen jono löytyy OEIS:sta. Jonon $n$ :s termi on ratsun $n\times n$ -graafin riippumattomuus polynomin neljännen asteen kerroin.

Tehtäviä

Ratkaise vastaava tehtävä, kun laudalle asetetaan 2 valkeaa ja 2 mustaa ratsua. Nyt sallittuja tilanteita ovat ne, joissa eriväriset eivät uhkaa toisiaan. (Vinkki: valitse tietyt joukot $A_{ij}$ .)
Yleistyksiä: $m\times n$ -laudalle, $k$ :lle ratsulle, $(k_1, k_2,\dots)$ eri väriselle ratsulle. Myös eri nappuloille (huom. rajoituksen että nappi ei voi mennä toisen yli voi unohtaa. Uhkaamattomassa tilanteessa sillä ei ole väliä, koska muiden nappuloiden liikkeet ovat lineaariset ja ne uhkaavat jo edessä olevaa nappulaa, jos joutuisivat kulkemaan sen läpi uhatakseen toista).
Perustele 4-syklien kaava.

Graafin naapuruus-polynomeja

Olkoon $G=(V, E)$ yksinkertainen, suuntaamaton, äärellinen graafi.

Määritellään $G$ :n ensimmäinen naapuruus-polynomi

$\begin{aligned} p_1(x) = \sum_{v\in V} x^{\deg(v)} \end{aligned}.$

Termin $x^k$ kerroin kertoo kuinka monta $k$ -asteista solmua graafissa on eli kuinka monella on (tasan) $k$ naapuria. Esimerkki:

Polynomista $p_1(x) = \sum_{k=0}^{m} a_k x^k$ voidaan laskea graafin kaarien määrä laskemalla $\frac{1}{2} p_1 '(1)$

$\frac{1}{2} \begin{aligned} \sum_{k=1}^m k a_k\end{aligned}$

Tämähän on tuttu kaava, että solmujen asteiden summa on kaksi kertaa kaarien määrä. Polynomi kuitenkin ryhmittelee solmut asteen mukaan, joten se on kätevä laskuissa. Esimerkin graafissa lasku on $(4 + 3\times 3 + 2 \times 3 + 1)/2 = 10.$

Mielenkiintoisempi ja enemmän graafista tietoa antava polynomi on toinen naapuruus-polynomi $p_2(y_1, y_2, \dots)$ . Muuttujia $y_j$ on mielivaltaisen monta, mutta kuitenkin tietyssä polynomissa aina vain äärellisen monta. Se määritellään seuraavasti.

Tutkitaan jokaiselle solmulle $v$ sen naapureita $w_1, w_2, \dots , w_t$ ja muodostetaan termi $\begin{aligned} \prod_{j=1}^{t} y_{\deg(w_j)} \end{aligned}$ . Nämä summataan yhteen. Esimerkki:

Keltaisella korostetut solmut tuottavat saman termin. Niillä sattuu tässä esimerkissä olemaan täysin samat naapurit, mutta samanlaiset termit voi syntyä muutenkin, riittää että naapuruston ”tyyppi” eli asteiden suurusjärjestykseen järjestetty vektori on sama.

Polynomin $p_2$ avulla voidaan laskea esimerkiksi kolmio-vapaan (ei sisällä 3-sykliä) graafin 4-ketjujen lukumäärä seuraavasti: Olkoon 4-ketju $(x_1, x_2, x_3, x_4)$ . Kiinnitetään $x_2$ . Nyt $x_1$ ja $x_3$ ovat jotkin sen naapurit. Annetaan siis niiden juosta kaikkien naapuri-kaksikkojen $(a_1, a_2)$ , $a_1 \neq a_2$ läpi. Lopuksi $x_4$ täytyy olla jokin $x_3$ :n naapuri. Tässä graafin kolmio-vapaus tulee tarpeeseen: meidän täytyy tietää vain se kuinka monta naapuria $x_3$ :lla on $x_1$ :n lisäksi. Solmu $x_1$ ei voi olla $x_3$ :n naapuri sillä muuten muodostuisi kolmio. Seuraava JavaScript funktio suorittaa tämän laskun, kun sille antaa polynomin $p_2$ objektina, johon termin $\prod_{j=1}^t y_{i_j}$ kerroin on koodattu avaimen ” $i_1, i_2, \dots , i_t$ ” arvoksi (huom. jokainen $i_j$ on siis avaimessa niin monta kertaa kuin se termissä esiintyy eli ”potenssit kirjoitetaan tuloina”).

/** @param p: The second neighbor polynomial of the graph */
function count4PathsInTriangleFreeGraph(p) {
    let s = 0;
    for (let key in p) {
        let a = key.split(",").map(x=>+x);
        for (let k1=0; k1<a.length; k1++) {
            for (let k2=0; k2<a.length; k2++) {
                if (k2===k1) continue;
                //x4 can be any nbr of x3 except x2 (hence -1)
                //x1 can't be a neighbor of x3, since no triangles
                s += p[key]*(a[k2]-1);
            }
        }
    }
    return s;
}

Edellisen esimerkin graafi on kolmio-vapaa, joten funktiota voi käyttää. Parametriksi annettava objekti on:

{"4":1, "2,3,4":2, "3,3":1, "2,3,3":1, "2,3":1, "2,4":1, "1,2,3,3":1}

Koodi antaa tulokseksi 60. Näin pienessä esimerkissä tämän funktion hyödyllisyys ei ehkä tule ilmi; voisimmehan käydä kaikki solmu-nelikot läpi ja tarkastaa kuinka moni niistä on 4-ketju. Sen hyödyt nähdään suuremmille graafeille, joille polynomi $p_2$ on laskettavissa helposti ja sen termien lukumäärä säilyy pienenä (eli niissä on jokin sellainen säännönmukaisuus joka helpottaa laskemista). Esimerkki:

Ratsun graafi 8×8-laudalla. Säännönmukaisuuksia merkitty väreillä. Tässä esimerkissä sitä ei vielä itse asiassa näe, mutta kun laudan koko kasvaa yli 8, keskelle syntyy neliö, jonka kaikki solmut ovat $p_2$ :n mielessä samanlaisia: niillä on 8 naapuria, joilla jokaisella on 8 naapuria. Suurilla n termi $y_8^8$ tulee siis hallitsevaksi: sen kerroin on $(n-8)^2$ .

Ratsun graafi 8×8-laudalla. Säännönmukaisuuksia merkitty väreillä. Tässä esimerkissä sitä ei vielä itse asiassa näe, mutta kun laudan koko kasvaa yli 8, keskelle syntyy neliö, jonka kaikki solmut ovat $p_2$ :n mielessä samanlaisia: niillä on 8 naapuria, joilla jokaisella on 8 naapuria. Suurilla n termi $y_8^8$ tulee siis hallitsevaksi: sen kerroin on $(n-8)^2$ .

Huomioita

Jos polynomissa $p_2$ asettaa $y_j = x$ kaikilla $j$ , niin saadaan polynomi $p_1$ . Tämä johtuu siitä, että $p_2$ jaottelee solmut tarkemmin niiden naapureiden asteiden mukaan, kun $p_1$ vain solmun oman asteen mukaan. Jokainen solmu $v$ tuo $p_2$ :een astetta $\deg(v)$ oleven $y$ -termin, joten asetettassa $y_j = x, \forall j$ , tämä redusoituu $x^{\deg(v)}$ :ksi, kuten $p_1$ :ssä.
Kun edellä puhuttiin 4-ketjuista, tarkoitettiin vain solmu-nelikkoja, joiden välillä on kaaret ensimmäisestä toiseen, toisesta kolmanteen ja kolmannesta neljänteen. Muista kaarista ei välitetä (esim. vaikka neljännestä olisi takaisin ensimmäiseen). Ei siis puhuta indusoiduista ketjuista.
Kolmio-vapaus on oleellinen vaatimus 4-ketjulaskelmassa. Esimerkiksi 3-solmuiselle täydelle graafille $K_3$ , joka on itse kolmio, saadaan $p_2(y) = 3y_2^2$ , joka antaisi tulokseksi 4. Mutta tietenkään siellä ei voi olla yhtään 4-ketjua, kun solmuja on vain 3.
Funktiota count4PathsInTriangleFreeGraph voi yksinkertaistaa jättämällä k1:n iteraation pois ja vain kertomalla sisimmässä silmukassa lisättävän lukumäärän (a.length-1):llä.

Tehtäviä

Laske graafista sellaisten solmu-kolmikkojen $(v_1, v_2, v_3)$ lukumäärä, joille $v_1$ ja $v_2$ ovat rinnakkaiset (eli niitä yhdistää kaari) sekä $v_1$ ja $v_3$ ovat rinnakkaiset.
Entäpä vastaavasti nelikot, jossa kaikki $v_j, j>1$ ovat rinnakkaisia $v_1$ :lle?

Graafin erillisten kaariparien laskeminen

Olkoon $G=(V, E)$ yksinkertainen suuntaamaton, äärellinen graafi. Haluamme laskea kuinka monella tapaa $E$ :stä voidaan valita kaksi kaarta $e_1$ ja $e_2$ siten että näiden päätepisteiden joukot $\{v_{11}, v_{12}\}$ ja $\{v_{21}, v_{22}\}$ ovat pistevieraat. (Suuntaamaton kaarihan itse asiassa on päätepisteidensä joukko, joten asian voisi ilmaista myös niin, että kaaret ovat pistevieraat.)

Halutunlaisten kaariparien laskeminen voidaan tehdä käymällä läpi kaikki kaaret ja summaamalla kullekin kaarelle sen pariksi sopivien kaarien lukumäärä. Tämä lukumäärä kaarelle $e=\{v_1, v_2\}$ on $|E|-\deg(v_1) - \deg(v_2) + 1$ .

Summan sieventämiseksi voidaan yhdistää saman lukumäärän antavat kaaret. Tätä varten muodostetaan graafista polynomi $p_E(x)$ asettamalla jokaista kaarta $e = \{v_1, v_2\} \in E$ vastaamaan termi $x^{\deg(v_1)+\deg(v_2)-1}$ , jossa eksponentti siis laskee kaaren päätepisteisiin liittyvien kaarien lukumäärän. Nämä summataan yhteen. Esimerkki:

Merkitään $p_E(x) = a_m x^m + \dots +a_1 x$ (huom. vakiotermi on $0$ , sillä jokaiseen kaareen liittyy ainakin yksi kaari nimittäin se itse). Nyt haluttu lukumäärä saadaan kätevästi:

$\begin{aligned} \sum_{k=1}^{m} a_k (|E|-k). \end{aligned}$

Ylläolevalle esimerkille saadaan ( $|E|=9$ )

$\begin{aligned} 4(9-5) + 4(9-4) + 1(9-3) = 42. \end{aligned}$

Huomiota

Tämä erillisten kaariparien lukumäärä on itse asiassa verkon ”2-paritusten” lukumäärä https://en.wikipedia.org/wiki/Matching_(graph_theory)
Olisi voitu määritellä myös polynomi $q_E$ , asettamalla jokaiseen kaareen suoraan termi $x^{|E|-\deg(v_1)-\deg(v_2)+1}$ eli siihen liittymättömien kaarien lukumäärä. Tällöin haluttu summa saa helposti ilmaistavan muodon: $q_E' (1)$ .
Ja koska yleensä vielä halutaan että derivaatta pitää ottaa nollassa, olisi voitu tehdä siirto $x\mapsto x+1$ . Tällöin esimerkin polynomi olisi ollut $\begin{aligned} q(x) = 4(x+1)^{9-5} + 4(x+1)^{9-4} + (x+1)^{9-3} = x^6 + 10 x^5 + 39 x^4 + 76 x^3 + 79 x^2 + 42 x + 9 \end{aligned}$ ja kuten huomataan, tämän derivaatta nollassa eli ensimmäisen asteen kerroin on $42$ .