Sanan osajonojen lukumäärä

Sanan osajono on sanasta järjestyksessä poimituista merkeistä muodostettu uusi sana. Esimerkiksi sanalla ’ABBA’ on osajonot (11 kpl) [”, ’A’, ’AA’, ’AB’, ’ABA’, ’ABB’, ’ABBA’, ’B’, ’BA’, ’BB’, ’BBA’]. Huomaa, että esim. ’AB’ saadaan kahdella eri tavalla, mutta lasketaan vain kerran.

Kuinka laskea sanan w osajonojen lukumäärä f(w)? Oletetaan että w:ssä esiintyvien merkkien lukumäärä on jokin ennalta kiinnitetty pienehkö luku. Halutaan löytää lineaariaikainen algoritmi.

Ratkaisu

Olkoon w sana, jonka osajonot halutaan laskea. Olkoon w:n pituus n ja siinä esiintyvät merkit \{c_1, c_2, \dots, c_m\}. Kun samaistetaan jokainen w:n osajono v siihen indeksien osajonoon, josta v löytyy kaikkein aikaisimmin, vastaa jokainen sanan osajono solmusta -1 lähtevää kävelyä suunnatulla graafilla G, jonka solmut ovat V(G) = \{-1, 0,1,\dots, n-1 \} ja solmusta j lähtee kaaret (j, k_c) missä k_c on indeksi, jossa merkki c esiintyy w:ssä seuraavan kerran lukien indeksistä j+1 lähtien (ja jos c ei enää esiinny, niin kaarta ei ole) ja tämä vastaavuus on bijektiivinen.

Esimerkiksi sanalle w = ”ABBA” graafi näyttää seuraavalta

Sanan ”ABBA” graafi. theFolls on dicti, jonka ao Python-koodi antaa, koodissa indeksit ovat siirretty yhdellä ja itse asiassa theFolls antaa seuraavan etsimisen alkaa itse siitä indeksistä missä ollaan.

Olkoon A edellä kuvatun suunnatun graafin vierekkäisyysmatriisi. Osajonojen lukumäärä on tällöin ensimmäisen rivin summa seuraavasta matriisista

\begin{aligned}  \sum_{j=0}^\infty A^j  = \left(I - A \right)^{-1}   \end{aligned}

Huomaa, että edellä summa on itse asiassa vain äärellinen, sillä kaaret vievät aina eteen päin, joten graafin kävely voi olla korkeintaan n:n pituinen ja A^{n+1}=0, joten summan suppenemisen eikä I-A:n kääntyvyyden kanssa tule ongelmia.

Merkitään B=I-A. Mehän tarvitsemme vain sen ensimmäisen rivin summan, joten koko matriisia A ei tarvitse muodostaa, eikä summaa \sum_{j=0}^{n}A^j laskea, vaan riittää ratkaista

B^{T}x = e_1,

missä e_1 on sarakevektori, jonka ensimmäinen komponentti on 1 ja loput nollia. Kun tämä kirjoitetaan Gauss-Jordanin menetelmän vaatimaan muotoon (jossa ei ratkaista koko käänteismatriisia, vain sen ensimmäinen rivi), niin huomataan, että ratkaiseminen on erittäin helppoa, sillä B on alakolmiomatriisi, jossa on ykkösiä diagonaalilla ja jokaisessa sarakkeessa korkeintaan m:ssä paikassa -1 (ja muuten nollia). Näin ollen saadaan seuraava lineaariaikainen algoritmi (Python):

def theFolls(w):
    """map c -> list a where a[j] is the next index of c in w
    when start searching from the index j"""
    alph = list(set(c for c in w))
    n = len(w)
    ret = {c: [n]*n for c in alph}
    prevs = {c: -1 for c in alph}
    for i, c in enumerate(w):
        for j in range(prevs[c]+1, i+1):
            ret[c][j] = i
        prevs[c] = i
    return ret

def countSubsequences(w):
    """How many words can be obtained from w as subsequences"""
    n = len(w)
    folls = theFolls(w)
    edges = [
        [folls[c][i]+1 for c in folls if folls[c][i]<n]
        for i in range(n)
    ]
    ret = 0
    a = [0 for _ in range(n+1)]
    a[0] = 1
    for i in range(n):
        for j in edges[i]:
            a[j] += a[i]
    return sum(a)

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)
dE[N]
11
24
315
480.96296
5718.61364
610655.34888
7261903.04770
810636087.48690
9713183947.85983
107.89467e+10
111.44259e+13
124.35102e+15
132.16594e+18
141.77942e+21
152.41246e+24
165.39710e+27
171.99232e+31
181.21348e+35
191.21944e+39
202.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ä.

Binääriblokit

Väritetään n:n peräkkäisen ruudun rivistä osa mustiksi ja lasketaan millaiset putket väritettyjä tuli. Esim:

n=10, värityksestä muodostuu putket [2, 1, 3]

Yhteensä erilaisia värityksiä on 2^n, sillä jokainen ruutu voidaan joko värittää tai jättää tyhjäksi (vrt. binääriluvut < 2^n), mutta kysymykset koskevat värityksestä muodostuvia putkia. Sanotaan putkien pituuksista koottua vektoria putkityypiksi. Yo. esimerkissä putkityyppi on [2, 1, 3].

  • a) Kuinka monta erilaista putkityyppiä voidaan n:n ruudun rivistä muodostaa?
  • b) Olkoon rivin pituus n. Kuinka moni eri väritys tuottaa putkityypin [k_1, k_2, \dots k_m]?

Mahdolliset väritykset ja putkityypit, n = 1, 2, 3, 4

Ratkaisu

a)

Putkityyppi [k_1, k_2, \dots, k_m] on mahdollinen muodostaa, mikäli se mahtuu n-riviin. Jokaisen putken välissä on oltava vähintään 1 tyhjä ruutu ja välejä on m-1, joten se mahtuu tasan silloin kun

\begin{aligned} m - 1 + \sum_{j=1}^m k_j \leq n \end{aligned}

Määritellään lukujonot a_n ja b_n seuraavasti

\begin{aligned} a_n = \#\{(k_1, k_2, \dots, k_m)   \hspace{.3cm}  |  \hspace{.3cm}   m - 1 + \sum_{j=1}^m k_j \leq n \}   \\ b_n =   \#\{(k_1, k_2, \dots, k_m)  \hspace{.3cm} |  \hspace{.3cm}   m - 1 + \sum_{j=1}^m k_j = n \}  \end{aligned}

eli b_n laskee sellaiset putkityypit, joita ”ei enää voi pidentää” ja a_n on kysytty jono.

Huomataan, että b_n itse asiassa laskee n-pituisia binäärijonoja, joissa ei ole yli yhden pituisia nollaputkia ja jotka alkavat ja päättyvät ykköseen. Näiden lukumäärä voidaan laskea seuraavan graafin n-1 -kävelyjen solmusta A solmuun A määränä.

Solmuja voidaan ajatella tiloina seuraavasti: A=”viimeksi on tullut ykkönen”, B=”viimeksi on tullut nolla”, C=”on tullut kahden nollan putki” . Tila C on hylkäävä, siitä ei pääse enää mihinkään. (Voi myös ajatella, että C:stä on siirtymä vain itseensä; todennäköisyydellä 1, jos graafi mielletään Markovin ketjuksi.) Aloitetaan tilasta A, sillä jonon täytyy alkaa ykkösellä, joten voidaan olettaa, että yksi ykkönen on jo tullut. Kävelyn täytyy myös päättyä tilaan A, sillä viimeinen numero halutaan olevan ykkönen.

Se, että näin todella saadaan haluttu lukumäärä, nähdään esimerkiksi ajattelemalla graafia Markovin ketjuna, jossa tilojen A ja B siirtymät tapahtuvat molemmat todennäköisyydellä \frac{1}{2} ja tilasta C on itsesiirtymä todennäköisyydellä 1. Näin saadaan todennäköisyys, että binäärijono on kysytynlainen (ks. tilojen selitykset kuvatekstissä). Tämä muutetaan lukumääräksi kertomalla kaikkien n-1-pituisten binäärijonojen lukumäärällä eli 2^{n-1}:llä.

Lasketaan siis vierekkäisyysmatriisin n-1:s potenssi diagonalisoimalla

\begin{aligned}     \left[ \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array} \right] ^{n-1}  =      \left[ \begin{array}{ccc} -1 & \frac{1-\sqrt 5}{2} &  \frac{1+\sqrt 5}{2}  \\ * & * & * \\ * & * & * \end{array} \right]   \left[ \begin{array}{ccc} 0 &  &    \\  &  \left( \frac{1-\sqrt 5}{2} \right)^{n-1}  &  \\  &  &  \left( \frac{1+\sqrt 5}{2} \right)^{n-1}  \end{array} \right]    \left[ \begin{array}{ccc} 0 & * & * \\ -\frac{1}{\sqrt 5} & * & * \\   \frac{1}{\sqrt 5} & * & * \end{array} \right]           \end{aligned}

Tämän alkio paikassa (0, 0) antaa luvun b_n. Saadaan

\begin{aligned}  b_n = \frac{1}{\sqrt 5} \left (  \frac{1+\sqrt 5}{2} \right)^n -     \frac{1}{\sqrt 5} \left (  \frac{1-\sqrt 5}{2} \right)^n  \end{aligned}

joten b_n on kuuluisa Fibonaccin lukujono f_n =f_{n-1} + f_{n-2}, f_1=1, f_2 = 1.

Ratkaistaan sitten a_n. Koska n+1-pituiseen riviin mahtuvalle putkityypille (k_1, k_2, \dots, k_m) pätee joko m - 1 + \sum_{j=1}^m k_j \leq n tai m - 1 + \sum_{j=1}^m k_j  = n+1 , niin nähdään rekursio

\begin{aligned}  a_{n+1} = a_n + b_{n+1}  \end{aligned}.

Osoitetaan nyt induktiolla, että a_n = f_{n+2}. Perustapaukset a_0 = 1 ja a_1 = 2 nähdään helposti luetteloimalla. Induktioaskel saadaan suoraan edellä olleesta rekursiosta, sillä, jos oletetaan a_n = f_{n+2}, niin

\begin{aligned}  a_{n+1} = a_n + b_{n+1}  = f_{n+2} + f_{n+1} = f_{n+3}. \end{aligned}

b)

Olkoon putkityyppi [k_1, k_2, \dots k_m]. Merkitään väritettyjen ruutujen määrää S = \sum_{j=1}^m k_j. Kysymys voidaan muotoilla toisin: Asetetaan n-S tyhjää ruutua jonoon ja kysytään kuinka monella tavalla näiden väliköistä (ja päädyistä) voidaan valita m kappaletta, joihin putkityypin putket (järjestyksessä) asetellaan. Välikköjä ja päätyjä on n-S-1 + 2 = n-S+1 kappaletta, joten vastaus on

\begin{aligned}   {n-S+1} \choose {m} \end{aligned}.

Huomioita

  • Jonon b_n voi todeta Fibonacci jonoksi myös huomaamalla rekursioyhtälön b_n = b_{n-1} + b_{n-2} (joko suoraan graafista tai matriisien kertolaskusta).

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}

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 nratsun graafi.

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

Tehtäviä

  1. 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}.)
  2. 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).
  3. 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.

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ä

  1. 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.
  2. 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.