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

313

    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. Kuka oli töllöntyön tekijä?

      Ketä on nyt pidätetty? Oliko syy mustasukkaisuus tyttöystävästä tai oliko muita lieventäviä seikkoja? Katuuko tekijä nyt
      Pieksämäki
      36
      3316
    2. Kotikasvatus siitä se lähtee eli missä meni vikaan että lapsesta tuli puukottaja

      Ottakaa muut oppia, normaali kotielämä. Ei liikaa edes hengellisyyttä.
      Pieksämäki
      44
      1636
    3. Kun kohtaat jotain ainutlaatuista

      ja upeaa, johon rakastut ehkä ensimmäistä kertaa ihan tosissaan. Sitten sähläät kaiken omien epävarmuuksien vuoksi. Eikö
      Ikävä
      19
      1001
    4. Mua ahdistaa

      Tämä juttu. Miksi nainen torjuit minut vaikka kiinnostuksen merkkejä oli? Eihän tämän jutun olisi tarvinut johtaa sen pi
      Ikävä
      32
      989
    5. Minkälaisessa asunnossa

      haluaisit kaivattusi kanssa asua?
      Ikävä
      59
      953
    6. Ei tämä enää tervettä oo

      Sydän pamppaillen oon jo tunnin meinannu laittaa sulle viestiä... Sormi tärisee lähetä kuvakkeen kohdalla.
      Ikävä
      22
      948
    7. Tuli vain mieleen

      että etkös sä yritäkin muiden miehiä? Se sun tuttava kertoi. En arvosta tuollaista naista, ihmekös kun oot sinkku. m -
      Ikävä
      37
      860
    8. Perämoottoreiden huolto melkoisen kallista

      Minulla on tuollainen keskikokoinen perämoottori ja yleistä merkkiä. Kyselin sille keväthuoltoa paikallisista liikkeistä
      Savonlinna
      36
      813
    9. Tanskademarit: ilman risusavottaa ei rahaa!

      Näin persuna on pakko ihailla noita Tanskan demareita. Tanskalaisessa sosiaalidemokratiassa ei työtön saa rahaa ellei os
      Maailman menoa
      173
      803
    10. Mikä siinä on että sinkku yrittää varattua?

      Siis ihan aina yrittävät muiden puolisoita.
      Sinkut
      48
      729
    Aihe