Palindrom og sorterte strenger

[Mie]

Hei! Jeg har jobbet med to oppgaver en god stund, og klarer ikke å løse dem... Er det noen som kan hjelpe meg?

Oppgave 1:
Vi sier at en streng er et palindrom dersom resultatet blir det samme om den leses forlenges eller baklengs. For eksempel er abba og 1234321 palindromer. Hvor mange palindromer av lengde m er det over et alfabet med n tegn?

Oppgave 2:
Anta at alfabetet {0, 1, 2} er gitt, og la oss si at en streng er sortert hvis sifrene ikke synker i verdi. For eksempel er 001122 og 002 sorterte, men 221100 og 201 er ikke det.
a) Finn alle sorterte strenger av lengde én, to og tre.
Mitt svar: 0, 1, 2, 00, 01, 02, 11, 12, 22, 000, 001, 011, 012, 022, 002, 111, 112, 122, 222.
b) Hvor mange sorterte strenger av lengde fire og fem finnes det?
Mitt svar: 0000, 0001, 0002, 0011, 0012, 0022, 0111, 0112, 0122, 0222, 1111, 1112, 1122, 1222, 2222 = 15

00000, 00001, 00002, 00011, 00012, 00022, 00111, 00112, 00122, 00222, 01111, 01112, 01122, 01222, 02222, 11111, 11112, 11122, 11222, 12222, 22222 = 21

Herfra står jeg fast...
c) Hvor mange sorterte strenger av lengde m finnes det?

d) Hva er svaret på forrige spørsmål hvis det var n tegn i alfabetet?

[Nebuchadnezzar]

Hva har du tenkt selv?

[Mie]

Jeg har tenkt masse rart, men ikke kommet frem til noe fornuftig. Har funnet ut at oppgave 2 gir de triangulære tallene som svar. Har prøvd å bruke det til å lage en formel, men har ikke kommet frem noe. Så jeg vet rett og slett ikke hvordan jeg skal tenke.

[Nebuchadnezzar]

Ett palindrom er det samme forlengs og baklengs. Dette betyr at det er første halvparten av tallene som er viktige

Si at vi har

$ \hspace{1cm}
123
$

Hvordan kan vi lage ett palindrom av det? Jo vi kan enten legge på 321 på slutten

$ \hspace{1cm}
123\textbf{321}
$

Eller så kan vi legge på ett tall, også speile det

$ \hspace{1cm}
123 \ X \ 321
$

Hvor $X$ kan være ett tall i alfabetet ditt. Dette betyr altså at alle tall av lengde n genererer palindrom av lengde 2n.

$abc$ gir $abccba$, $\&\%$ gir $\&\%\%\&$ osv. Anta først at $m$ er et partall (delelig på 2). Dette betyr at alle ord av lengde $m/2$ genererer palindrom av lengde $m$. Så hvor mange ord av lengde $m/2$ kan vi lage? Vel på første plassen har vi $n$ muligheter på andre plassen har vi $n$ muligheter så totalt har vi

$ \hspace{1cm}
\text{Palindrom av partal lengde } m = \underbrace{n \cdot n \cdot n \cdots n \cdot n}_{m / 2 \ \text{ganger}} = n^{m/2}
$

Om $m$ er odde fungerer ikke akkuratt samme fremgangsmåte men veldig lik. Eneste du må tenke på er hvordan du behandler tallet i midten altså

$ \hspace{1cm}
123 \ X \ 321
$

Men dette gir jeg deg ett forsøk på å finne ut av på egenhånd først

[Mie]

Tusen takk for hjelp! Da skal jeg prøve om jeg får det til

[Mie]

Har kommet frem til at når m er oddetall, blir de første tegnene (m+1)/2. De siste tegnene blir (n-1)/2, som bestemmes av de første (n-1)/2. Hvordan dette videre brukes til å finne ut hvor mange palindromer som kan lages, klarer jeg foreløpig ikke å finne ut av...

[jos]

Antall sorteringer av lengde m når alfabetet har n tegn : den binomiske koeffisienten (m+n-1,m) som altså angir antall måter å plassere m objekter på m+n-1 plaser når rekkefølgen ikke teller.