Stringhe combinatorie

[hamming_burst]

Salve,
vorrei un aiuto.

Sia $w = a_1 · · · a_n$ una stringa, con $n in NN$ e $|w|=n$

Ogni stringa della forma:
- $a_1 · · · a_j$ , con $j in {1, . . . , n}$ è detta un prefisso di $w$
- $a_i · · · a_n$ , con $i in {1, . . . , n}$ è detta un suffisso di $w$
- $a_i · · · a_j$, con $i, j in {1, . . . , n},\ i <= j$ detta una sottostringa di $w$
- $\epsilon$ ($|w|=0$) è sia prefisso che suffisso che sottostringa di $w$

Esercizio:
Sia data una stringa $w$ di lunghezza $|w|=n$. Quanti sono i suoi prefissi, i suoi suffissi e le sue sottostringhe?

il numero di prefissi è uguale al numero di suffissi perciò cerco solo i prefissi e le sottostringhe.

Io mio grosso problema è che c'è di mezzo l'ordinamento, cioè non si può parlare di sottonsiemi, disposizioni ordinate, ecc..
non trovo un appiglio combinatorio, mi sapreste indicarne uno possibile?
Un dubbio: se non conosco l'alfabeto delle stringhe cambia il numero di dei prefissi e delle sottostringhe, io direi proprio di no, visto che è vincolata dalle posizioni.

Ringrazio molto

[cenzo1]

Ciao,

Esercizio:
Sia data una stringa $w$ di lunghezza $|w|=n$. Quanti sono i suoi prefissi, i suoi suffissi e le sue sottostringhe?

mi verrebbe da dire, rispettivamente: $n$, $n$, $(n*(n+1))/2$.

[hamming_burst]

"cenzo":Ciao,

Esercizio:
Sia data una stringa $w$ di lunghezza $|w|=n$. Quanti sono i suoi prefissi, i suoi suffissi e le sue sottostringhe?

mi verrebbe da dire, rispettivamente: $n$, $n$, $(n*(n+1))/2$.

ti ringrazio
per i prefissi, ho ragionato in modo diverso da quello che ho scritto, cioè in modo più "algebrico" utilizzando semplicemente la definizione di prefisso, ed avrei anche trovato il tuo risultato anche banalmente, ma non è il risultato che volevo. (che sarebbe $n+1$ contanto la stringa vuota $\epsilon$)

Vorrei capire se in combinatoria si può riuscire a calcolare ciò, si può parlare di disposizioni, non so, non trovo un nesso.

Se prendiamo che un prefisso è semplicemente l'operazione di togliere simboli in coda alla stringa, cioè: se la stringa $a_1....a_n$ e un suo prefisso è $a_1....a_j$ come da definizione, lo sarà anche $a_1...a_(j-1)$ e così via basta "contare" queste operazioni.
ma ragionando con disposizioni e compagnia come diamine lo risolvo?

[cenzo1]

"hamming_burst":
Se prendiamo che un prefisso è semplicemente l'operazione di togliere simboli in coda alla stringa, cioè: se la stringa $a_1....a_n$ e un suo prefisso è $a_1....a_j$ come da definizione, lo sarà anche $a_1...a_(j-1)$ e così via basta "contare" queste operazioni.
ma ragionando con disposizioni e compagnia come diamine lo risolvo?

Il prefisso inizia sempre nella prima posizione della stringa. Occorre quindi scegliere solo la posizione di fine.
Questa può essere una delle $n$ posizioni disponibili.
In quanti modi possiamo scegliere un oggetto tra n disponibili ?
$((n),(1))=n$ (combinazioni semplici).
Analogamente per il suffisso.

Per la sottostringa devi scegliere 2 posizioni (inizio e fine) tra n disponibili.
Fai attenzione però che puoi anche ripetere lo stesso indice (cioè puoi avere sottostringhe di dimensione uno).
Quindi riconosciamo le combinazioni con ripetizione di n oggetti di classe 2:
$C^r_(n,2)=((n+2-1),(2))=((n+1),(2))=((n+1)*n)/2$