Lingua e parole

herbrand · Messaggio da **herbrand** » 11 gen 2006, 11:56

In una strana lingua ci sono n lettere diverse.Una sequenza (chiamatela stringa) di lettere è una parola se e solo se tra tra qualsiasi coppia di lettere uguali non ci sono altre due lettere uguali,cioè sequenze come la seguente
...A...B...B...A...
sono vietate, dove A e B sono due lettere ( non necessariamente differenti della strana lingua)
1) qual è la massima lunghezza di una parola della strana lingua?
2)quante sono le parole di quella lunghezza?
Buon lavoro

xxalenicxx · Messaggio da **xxalenicxx** » 20 gen 2006, 19:35

Se non ho sbagliato i conti dovrebbe essere, la max lunghezza (3*n) e tutte le possibili parole $ 2^{n-1}\cdot n! $

herbrand · Messaggio da **herbrand** » 21 gen 2006, 18:10

Corretto! Molto bene

NEONEO · Messaggio da **NEONEO** » 22 gen 2006, 16:18

C

ome hai fatto?

NEONEO · Messaggio da **NEONEO** » 22 gen 2006, 16:34

A, no, aspetta, ho capito, in effetti un metodo ipotetico è quello di inixiare con la lettera X1 e ripeterla tre volte passando poi alla lettera X2 e così via fino alla lettera Xn. In effetti questo è l'unico modo massimizzante, perchè se ne accosti quattro uguali il gioco è finito. Poi per trovare il numero di parole consideri prima di tutto che puoi poermutare le triplette perciò diventa il fattoriale di n, ma poi devi moltiplicarlo per le trasposizioni dei termini finali ed iniziali di ogni tripletta, che sono (n-1) perciò diventerà come hai scritto 2^(n-1)