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

259

    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. Ranskan vasemmistojohtaja: "Kyllä, meneillään on suuri väestönvaihto!"

      Ranskan vasemmistojohtaja Jean-Luc Mélenchon järkytti myöntämällä avoimesti sen, mitä tiedotusvälineet ovat pitkään pitä
      Maailman menoa
      75
      2316
    2. Valion maitotehtaalla kapina

      Ilmastonmuutoksesta, eläinten hyvinvoinnista ja ympäristön saastumisesta huolestuneet eläinkapinalliset estävät panssa
      Maailman menoa
      50
      2229
    3. SDP haluaa tappaa maaseudun - bensan hinta mahdollisimman korkealle

      Maaseudulla auto on välttämätön asia, ja lähes kaikilla on bensa-autot. Kuinka tyhmä pitää olla jos äänestää demareita?
      Maailman menoa
      162
      2035
    4. Päivän Riikka: polttoöljyn hinta räjähti

      Näyttää tuo putinismi ilmenevän persuissa myös Suomen yrittäjien kampittamisena. Polttoöljy on se katalyytti, joka pitää
      Maailman menoa
      17
      1811
    5. Helsingin yllä valopalloja

      https://www.iltalehti.fi/kotimaa/a/1508be00-28c9-4156-83dc-0be5e7aa3066 "Helsingin taivaalla lensi lauantaina puolen yön
      Sinkut
      86
      1261
    6. Kovasti on hävittäjiä ilmassa. Nytkö se alkoi?

      Onko nyt sota ?? `Vai harjoituksiako vain? Hävittäjät pörrää kovasti.
      Kouvola
      74
      1153
    7. HÄLYYTYS!!

      Ukraina se hyökkää jo Suomen maaperälle. https://www.iltalehti.fi/kotimaa/a/645b83ce-e074-4f00-8b99-245d01b38a36
      NATO
      302
      1043
    8. Jumalauta! Ukraina hyökkää jo Suomeenkin!

      Ukrainan drooneja tullut Suomeen ainakin kolme, ehkä enemmäkin! Syvälle Suomeen! Nyt on klovnipressa hukkapätkä mennyt T
      Maailman menoa
      324
      970
    9. Helsingin yllä lensi yöllä jotain outoa puolen yön aikaan valopalloja

      Poliisi on saanut tapauksesta yhden havaintoilmoituksen. Valopalloja oli noin parikymmentä ILtalehdessä on video tapah
      Maailman menoa
      100
      943
    10. Mitä kaikkia vikoja

      On kaivatussasi?
      Ikävä
      64
      896
    Aihe