matematikk.net

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?

Hva har du tenkt selv?

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.

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

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

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...

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.