Newsgroup: it.hobby.enigmi
Titolo: numeri palindromi

Oggi all'università abbiamo fatto un programmino per rendere un vettore
qualsiasi, se possibile, in forma palindroma; per chi non lo sapesse
palindromo significa che si può leggere allo stesso modo sia da destra a
sinistra, che da sinistra a destra.
Per es:
123454321 è palindromo
Radar è una parola palindroma.
Ascoltando la lezione mi è venuto in mente questo problemino.
Se prendiamo per es. il numero 1111223, questo numero, così come è scritto,
non è palindromo. Tuttavia lo si può rendere tale in più di un modo:
2113112
1213121
1123211
Generalizzando, mi chiedo (anzi, Vi chiedo), in quanti modi si può rendere
palindromo un numero di n cifre in cui cui ogni cifra si ripete per k volte
(con k non necessariamente uguale per ogni cifra)?
Ciao
--
                  ***Alessandro***

 (con k non necessariamente uguale per ogni cifra)?
In una stringa palindroma ogni carattere è accoppiato col suo simmetrico,
tranne al più quello centrale, se la lunghezza è dispari. Dividiamo quindi
lo studio in due casi, a seconda della parità di n:
A) n = 2*h pari.
Siano n0,n1,..,n9 il numero delle occorrenze delle dieci cifre 0,..,9
Sarà ovviamente n0+n1+..+n9=n e tutti gli n_i saranno pari (n0=2*h0, n1=2*h1
ecc.) o nulli.
La prima metà della stringa conterrà la metà degli zeri, la metà degli uno e
così via, e la seconda metà sarà a specchio. In quanti modi possimo disporre
le h cifre per formare la mezza stringa? In h!/(h0!*h1!*..*h9!) modi.
Es.:
11117788 può dar vita a
4!/(2!*1!*1!) = 12 palindromi
1178 8711
1187 7811
1718 8171
1781 1871
1817 7181
1871 1781
7118 8117
7181 1817
7811 1187
8117 7118
8171 1718
8711 1178
B) n=2*h+1 dispari
Una sola delle cifre può essere presente un numero dispari di volte. Fissato
il pivot centrale, lo si toglie dalla lista e con le rimaneni 2*h cifre si
procede come nel caso A
Ciao, Silv:o)

 le h cifre per formare la mezza stringa? In h!/(h0!*h1!*..*h9!) modi.
[CUT]
Scusa Silvio, ma non riesco a capire come sei arrivato a questa formula.
--
                  ***Alessandro***

 Scusa Silvio, ma non riesco a capire come sei arrivato a questa formula.
E' la formula delle disposizioni con ripetizione, riportata da qualsiasi
manuale di calcolo combinatorio.
Supponiamo di dover disporre n oggetti, di cui k1 di un tipo, k2, di un
secondo tipo e così via (k1+k2+..+km=n).
Se tutti gli oggetti fossero numerati, quindi distinguibil, allora avremmo
n! possibili disposizioni. Se i k1 oggetti del primo tipo li consideriamo
indistinguibili, allora tutte le disposizioni che hanno i k1 oggetti del
primo tipo nelle stesse posizioni, seppur con numeri differenti, vanno
accorpate a formare un'unica occorrenza. Ma dato che, fissate le posizioni,
ci sono k1! diversi modi di piazzare i k1 oggetti in quelle posizioni,
allora bisognerà dividere le n! disposizioni per k1!
Es.: a, eèé, iì, o, u
a e è i ì é o u
a e é i ì è o u
a è e i ì é o u
a è é i ì e o u
a é e i ì é o u
a é è i ì e o u
sono 6 delle 8! possibili disposizioni, ma se non contiamo gli accenti sulle
e queste 6 stringhe vanno contate come una sola. Stessa cosa per le i, che
portano a gruppi di 2 occorrenze diverse solo per gli accenti. Quindi le
possibili stringhe formate da {a,eee,ii,o,u} sono 8!/(3!*2!) = 3360
Ciao, Silv:o)

 ha scritto nel messaggio
news:9045n7$6atq$1...@ID-49224.news.dfncis.de...

Grazie fattoriale,cioè ...
GRAZIE! :)
Tra parentesi statistica e calcolo combinatorio è il corso che farò il
prossimo bimestre. Non vedo l'ora! Ciao
Ale