Sanan osajonojen lukumäärä

Sanan osajono on siitä järjestyksessä poimittujen kirjaimien muodostama sana. Esim. sanalla "KISSA" on osajonot (24 kpl)

['', 'A', 'I', 'IA', 'IS', 'ISA', 'ISS', 'ISSA', 'K', 'KA', 'KI', 'KIA', 'KIS', 'KISA', 'KISS', 'KISSA', 'KS', 'KSA', 'KSS', 'KSSA', 'S', 'SA', 'SS', 'SSA']

Nyt kysytään algoritmiä (tai löytyykö jopa jotain kaavaa) jolla laskea näiden määrä annetulle sanalle.

Tutkitaan sitten tapausta jossa sana on n:n pituinen binäärijono.

Esim. jonolla "01101" on osajonot (18 kpl)

['', '0', '00', '001', '01', '010', '0101', '011', '0110', '01101', '0111', '1', '10', '101', '11', '110', '1101', '111']

Mikä on suurin määrä osajonoja mitä n-binäärijonolla voi olla?
Mikä on keskiarvo?

3

224

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Varmistukseksi että laskut menee oikein, niin mitä saatte seuraavalle?

      "OSAJONOJEN LUKUMÄÄRÄN LASKEMINEN"

      (myös välit lasketaan merkeiksi). Itse saan 1545659216.

    • Ratkaisu: https://membolicsythod.home.blog/2020/02/29/sanan-osajonojen-lukumaara/

      Lisäkysymyksen ensimmäisen kohdan vastaus on f_{n 2} - 1, missä f_k on k:s Fibonacci luku.
      Suurin määrää saadaan selvästikin alternoivalla binäärijonolla, sillä aina kannattaa hypätä lähemmäksi, jotta saadaan enemmän kävelyjä (ja mikäli kaksi samaa merkkiä on peräkkäin aiheuttaa tämä toisen yli hyppäämisen edeltävästä merkistä (ja lähtö on -1 eli tyhjä, niin vaikka se olisi heti alussa, niin haittaa tulee)).
      Alternoivia on kaksi 0101.... ja 1010.... Näille osajonojen määrä, merkataan sitä a(n), on selvästi yhtäsuuri, sillä toinen saadaan toisesta muuttamalla ykköset nolliksi ja nollat ykkösiksi.

      Lasketaan nyt sanan 0101.... (päättyy joko 0 tai 1 riippuen n:n pariteetista) osajonot.
      Induktioaskel kaavan todistuksessa menee samaan tyyliin kuin mikä viimeksikin oli missä ratkaisuun tuli Fibonacci luvut. Jaetaan osajonot kolmeen luokkaan:
      - tyhjä jono
      - 0:lla alkavat
      - 1:llä alkavat

      Jos osajono v alkaa nollalla, niin silloin loppu eli v[1:] on 101... (pituus n-1):n osajono, induktio-oletuksen mukaan näitä on f_{n 1}-1.
      Jos alkaa ykkösellä, niin v[1:] taas on 010... (pituus n-2):n osajono, sillä ensimmäistä nollaa ei ole voitu käyttää, sillä alkoi ykkösellä ja niinkuin tuossa edelläkin se ensimmäinen ykkönen on voitu käyttää tai sitten ei, mutta se loppu on sen lopun osajono joka tapauksessa käytettiin se ensimmäinen ykkönen ekaan paaluun tai myöhemmin. Näitä on f_n - 1.
      Siis yhteensä

      a(n)
      = 1 a_{n-1} a_{n-2}
      = 1 f_{n 1} - 1 f_n - 1
      = f_{n 2} - 1

      • Tämä jono, kun muuten on täällä: https://oeis.org/A000071 ja siellä on yksi muoto, että mistä tuo tulee: "Number of 001-avoiding binary words of length n - 3", niin onko tuo jotenkin kombinatorisesti nähtävissä tuosta suoraan, kun vähän samaltahan tuo kuulostaa, että kahta nollaa ei tule peräkkäin ja sitten ykköstä. Jos merkataan uudella binäärijonolla sitä indeksien osajonoa, josta osajono muodostetaan niin että 0 merkkaa että ei tule mukaan ja 1 että tulee mukaan, niin olisiko se siitä jotenkin nähtävissä?


    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Björn Wahlroos, maataloustuet lakkautettava

      Sanoo pankkimies. Mitäs persut ja muut tukinulliem perskärpäset tähän? "Wahlroos listaa kansallisen maataloustuen. – I
      Maailman menoa
      118
      3120
    2. Persut päättivät hiilivoiman kieltämisestä Suomessa

      Moni on jo unohanut kuka hyväksyi hiilivoimaloiden kieltämisen Suomessa: persut Sukupuolineutraalit liikennemerkitk
      Maailman menoa
      61
      2795
    3. Nalle Wahlroos ei ulise kuten Teemu Selänne sähkölaskuista

      Nalle "hah hah" nauroi saamistaan sähkötuista, kun taas Teemu-poika itkeä tirautti kovasta sähkön hinnasta. Nalle nauro
      Maailman menoa
      35
      2172
    4. Muistattekos kuinka kokoomus ja persut vinkuivat sähkön hinnasta?

      Oppositiossa vuonna 2022, kun sähkön hinta uhkasi nousta 20 senttiin kilowattitunnilta? Nyt ovat hiiren hiljaa, kun pitä
      Maailman menoa
      103
      2098
    5. Mikä aate kaiken pahan takana?

      Se laiskistuttaa kansat, opettaa vaatimaan etuisuuksia, syleilee maailmoja eikä omaa kansaa.
      Maailman menoa
      127
      1952
    6. Vain persut vastustivat hiilivoimaloiden alasajoa

      Persut vastusti jyrkästi hiilen kieltolakia ja on myöhemmin vaatinut hiilivoimaloiden pitämistä käytössä. He perusteliva
      Maailman menoa
      44
      1931
    7. Muistan vuosikymmenten takaa

      Toivottavasti voit hyvin ja jaksat työssäsi. Olet upea ja erinomainen ihminen, toivon kaikkea hyvää.
      Ikävä
      10
      1152
    8. Kristinoppi ja vähäkatekismus:

      Luther Lapsikasteesta: "Mitä kaste antaa eli hyödyttää? Kaste vaikuttaa syntien anteeksiantamuksen, vapauttaa kuolemas
      Luterilaisuus
      67
      974
    9. Päivi Räsäsen seksipaljastus loksauttaa Katja Ståhlin leuat! Elämäni biisi kohujakso tv:ssä!

      Elämäni biisi -suosikkisarjan uusinnat ovat startanneet ja nyt vuorossa on sarjan 2. jakso v. 2019. Sinisille sohville
      Suomalaiset julkkikset
      11
      918
    10. Valtuuston puheenjohtaja ei hallitse kokousta

      Kemijärven kaupunginvaltuuston puheenjohtaja antoi teatterin pyöriä valtuustossa. Sosialidemokraattien Risto Korkalon pu
      Kemijärvi
      77
      880
    Aihe