[viesti Survo-keskustelupalstalla (2001-2013)]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 2.8.2004 10:05 |
Mainitsin viime viestissäni "Kesäpähkinä 2" -säikeeseen
> Yhdistelmä COMB+LINEDEL on kätevä monissa muissakin kombinatoorisissa
> ongelmissa, joissa esiintyy rajoituksia.
ja selitin esimerkin permutaatioista, joissa peräkkäiset numerot eivät
esiinny peräkkäin.
Kun yritin löytää yleisen säännön, miten po. kombinaatioluvut
käyttäytyvät, jouduin turvautumaan mainioon tietopankkiin
http://www.research.att.com/~njas/sequences/index.html
josta tuo sääntö löytyi.
Olen sitten (eräänlaisena kesälomaharrastuksena) yrittänyt keksiä
sellaisen esimerkin, jota ei tuossa tietopankissa tunneta.
Pari ensimmäistä yritystäni johtivat täysin selviin sääntöihin, mutta
sitten näyttää tärpänneen!
Tarkastellaan n-numeroisia kokonaislukuja, jotka merkitään etunollien
kera. Esim. arvolla n=3 luvut ovat
000 001 002 003 004 005 006 007 008 009 010 011 ... 998 999
ja kysytään, paljonko on sellaisia, joisa ei esiinny peräkkäisiä
numeroita. Yllä näkyvistä luvuista 001, 010 ja 011 ovat silloin
kelvottomia, samoin esim. 123, 223, 989.
Merkitään kevollisten n-numeroisten lukujen määrää a(n).
On selvää, että a(1)=10 ja a(2)=91 (luvut 01,12,23,34,45,56,67,78,89
eivät kelpaa). On jo vaikeampi päätellä, että a(3)=828, puhumattakaan
siitä, mikä on yleinen sääntö, jolla a(n) voidaan laskea.
Lasketaan a(4) Survon avulla. Aloitetaan COMB-komennolla riittävän
suuressa toimituskentässä:
COMB N,CUR+1 / N=INTEGERS,4,10
Integers of 4 digits in base 10: N[N]=10000
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
0 0 0 4
...
9 9 9 5
9 9 9 6
9 9 9 7
9 9 9 8
9 9 9 9
Se tuottaa kaikki 4-numeroiset 10-järjestelmän luvut (etunollineen).
Lisätään jokaisen rivin alkuun yksi välilyönti (INSERT-komennolla):
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
0 0 0 4
...
9 9 9 5
9 9 9 6
9 9 9 7
9 9 9 8
9 9 9 9
Ne luvut, joissa esiintyy peräkkäisiä numeroita, karsitaan listasta
seuraavilla, listan eteen kirjoitetuilla komennoilla:
LINEDEL CUR+1,END," 0 1 "
LINEDEL CUR+1,END," 1 2 "
LINEDEL CUR+1,END," 2 3 "
LINEDEL CUR+1,END," 3 4 "
LINEDEL CUR+1,END," 4 5 "
LINEDEL CUR+1,END," 5 6 "
LINEDEL CUR+1,END," 6 7 "
LINEDEL CUR+1,END," 7 8 "
LINEDEL CUR+1,END," 8 9 "
jolloin jäljelle jää 7534 lukua eli a(4)=7534 ja samaan tyyliin
jatkaen saadaan taulukko
n a(n)
1 10
2 91
3 828
4 7534
5 68552
6 623756
Tästä on täysin mahdoton päätellä mitään yleistä varsinkin, kun
luvut kasvavat sangen nopeasti.
Todellisuudessa aloitinkin tarkastelemalla 10-järjestelmän asemasta
n-numeroisia 3-järjestelmän lukuja
Esim. kaikki kolminumeroiset luvut ovat tällöin
000 001 002 010 011 012 020 021 022
100 101 102 110 111 112 120 121 122
200 201 202 210 211 212 220 221 222 (3^3=27 kpl.)
joista "kiellettyjä" ovat
001 010 011 012
101 112 120 121 122
201 212
eli niitä on 11 kpl. Näin 3-järjestelmässä a(3)=27-11=16
Käyttämällä ahkerasti COMB+LINEDEL-yhdistelmää, kantaluvulle 3
syntyy taulukko
n a(n)
1 3
2 7
3 16
4 37
5 86
6 200
7 465
8 1081
9 2513
10 5842
Tämä lukujono tunnetaan tietopankissa ja sille pätee yleinen sääntö
a(n) = 3*a(n-1) -2*a(n-2) +a(n-3),
esim. 3*86-2*37+16=200=a(6).
Tietopankki kertoo useita tilanteita (matemaattisesti aika hankalia),
joissa lukujono vallitsee, mutta ei mitään tässä esitettyyn viittaavaa.
a(n)-lausekkeen muoto vihjailee, että yleisemminkin kyseessä voisi
olla vakiokertoiminen, lineaarinen rekursiokaava.
Siispä yrittämään vastaavaa 4-järjestelmässä, jolloin COMB+LINEDEL-
simputus tuottaa taulukon
n a(n)
1 4
2 13
3 42
4 136
5 440
6 1423
7 4602
8 14883
9 48132
10 155660
Tästä tietopankilla on vain harmaita aavistuksia, mutta se ei osaa
antaa mitään yleistä sääntöä, vaikka määrittelisi jonon alkuun
a(0)=1.
Oli miellyttävä havaita, että Reijo Sundin NTERM toimii
tässä tapauksessa loistavasti, sillä se antaa seuraavan termin ja
säännön:
NTERM 1 4 13 42 136 440 1423 4602 14883 48132 155660
503408 / 4a(n-1)-3a(n-2)+2a(n-3)-a(n-4)
Tämä johtuu siitä, että NTERM käyttää yhtenä etsintäkeinonaan
lineaarista autoregressiota (regressiota viivästetyillä arvoilla).
Rekursiivinen lauseke on hämmästyttävän "kaunis" kertoimineen
+4, -3, +2, -1
ja johdattaa väistämättä ajattelemaan yleisen tuloksen kantaluvulla b
olevan
a(n)=b*a(n-1)-(b-1)*a(n-2)+(b-2)*a(n-3)-...+(-1)^(b-1)*a(n-b).
ja esim. 10-järjestelmän luvuilla
a(n) = 10*a(n-1) - 9*a(n-2) + 8*a(n-3) - 7*a(n-4) + 6*a(n-5)
-5*a(n-6) + 4*a(n-7) - 3*a(n-8) + 2*a(n-9) - 1*a(n-10)
Numeeriset kokeilut vahvistivat uskoani tähän muodostettuani
COMB+LINEDEL-tekniikalla 10-järjestelmälle taulukon
n a(n)
0 1
1 10
2 91
3 828
4 7534
5 68552
6 623756
Nyt piti yrittää todistaa tuon yleisen kaavan paikkansapitävyys.
Se tiesi muutaman tunnin ankaraa pohdiskelua ja Survon avulla
kokeilua ennenkuin päädyin seuraavaan todistusluonnokseen:
(Tämä on ote tietopankkiin lähettämästäni ehdotuksesta, jossa
tarjottuna lukujonona oli 10-järjestelmän mukainen.)
------------------------------------------------------------------------
Sketch of a proof for a general base b=2,3,...:
Let a(n) be number of n-tuples of 0,1,...,b-1 without consecutive digits
and s(n,i) number of them with i (i=0,1,...,b-1) as the last digit.
Then it is clear that s(n,i)=a(n-1)-s(n-1,i-1) since when extending
a valid n-1-tuple by i those ending by i-1 are not valid as n-tuples.
Thus s(n,0)=a(n-1),
s(n,1)=a(n-1)-s(n-1,0)=a(n-1)-a(n-2),
and in general
s(n,i)=a(n-1)-a(n-2)+a(n-3)-...+(-1)^i*a(n-i-1), i=0,1,...,b-1.
Since a(n)=s(n,0)+s(n,1)+...+s(n,b-1),
we get the 'beautiful' recursion formula
a(n)=b*a(n-1)-(b-1)*a(n-2)+(b-2)*a(n-3)-...+(-1)^(b-1)*a(n-b).
------------------------------------------------------------------------
Selventävä esimerkki (b=3, n=4):
Taulukossa on kaikki a(3)=16 sallittua kolmen numeron yhdistelmää, joita
on jatkettu 0:lla (ensimmäinen sarake), 1:llä (toinen sarake) ja
2:lla (kolmas sarake). Näistä on karsittava ne, joissa on peräkkäisiä
numeroita. Niitä voi nyt esiintyä vain kahdessa viimeisessä positiossa.
Sallitut yhdistelmät on merkitty x:llä.
0 0 0 0 x 0 0 0 1 0 0 0 2 x
0 0 2 0 x 0 0 2 1 x 0 0 2 2 x
0 2 0 0 x 0 2 0 1 0 2 0 2 x
0 2 1 0 x 0 2 1 1 x 0 2 1 2
0 2 2 0 x 0 2 2 1 x 0 2 2 2 x
1 0 0 0 x 1 0 0 1 1 0 0 2 x
1 0 2 0 x 1 0 2 1 x 1 0 2 2 x
1 1 0 0 x 1 1 0 1 1 1 0 2 x
1 1 1 0 x 1 1 1 1 x 1 1 1 2
2 0 0 0 x 2 0 0 1 2 0 0 2 x
2 0 2 0 x 2 0 2 1 x 2 0 2 2 x
2 1 0 0 x 2 1 0 1 2 1 0 2 x
2 1 1 0 x 2 1 1 1 x 2 1 1 2
2 2 0 0 x 2 2 0 1 2 2 0 2 x
2 2 1 0 x 2 2 1 1 x 2 2 1 2
2 2 2 0 x 2 2 2 1 x 2 2 2 2 x
s(4,0)=a(3)=16 s(4,1)=a(3)-a(2) s(4,2)=a(3)-a(2)+a(1)
=16-7=9 =16-7+3=12
Kelvollisia on siis a(4)=a(3)+a(3)-a(2)+a(3)-a(2)+a(1)
=3*a(3)-2*a(2)+a(1)
=3*16-2*7+3=37 kpl.
-Seppo
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!