Comporre parole
Si hanno $m$ lettere $A$ e $n$ lettere $B$, con $m \geq n$. In tutto si possono formare $\frac{(m+n)!}{m!n!}$ parole. Quante parole si possono formare in modo che, contando le lettere da sinistra a destra, il conteggio delle $A$ non sia mai minore del conteggio delle $B$?
e.g. Con $3$ lettere $A$ e $3$ lettere $B$, la parola $A B A A B B $ è una parola lecita, la parola $ A A B B B A$ non lo è.
e.g. Con $3$ lettere $A$ e $3$ lettere $B$, la parola $A B A A B B $ è una parola lecita, la parola $ A A B B B A$ non lo è.
Risposte
Allora se il conteggio delle $ A $ non deve essere mai minore del conteggio delle $ B $ segue necessariamente che $ m = n $ .
Inoltre per lo stesso motivo ogni serie di lettere deve iniziare con una $ A $ e finire con una $ B $.
Quindi dato un numero di lettere $ m = n $ puoi ricondurti al caso $ m-1 e n-1 $ e osservare che vanno bene tutte le combinazioni escluse quelle dove vi è dopo la A iniziale un numero $ 2 <= j <= m-1 $ di $ B $ e tutte le loro combinazioni.
Quindi date $ m=n $ lettere il numero di conteggi $ C $ che soddisfano tale condizione è : $ C = ( (m + n -2)! )/ ((m-1)!(n-1)!) - (( m+n-4)!)/((m-3)!(n-1)!) $
Inoltre per lo stesso motivo ogni serie di lettere deve iniziare con una $ A $ e finire con una $ B $.
Quindi dato un numero di lettere $ m = n $ puoi ricondurti al caso $ m-1 e n-1 $ e osservare che vanno bene tutte le combinazioni escluse quelle dove vi è dopo la A iniziale un numero $ 2 <= j <= m-1 $ di $ B $ e tutte le loro combinazioni.
Quindi date $ m=n $ lettere il numero di conteggi $ C $ che soddisfano tale condizione è : $ C = ( (m + n -2)! )/ ((m-1)!(n-1)!) - (( m+n-4)!)/((m-3)!(n-1)!) $
Stai praticamente buttando il caso di parole dispari.
$ABA,A AB,A A A$
Mi sembra sufficiente per confutare
$ABA,A AB,A A A$
Mi sembra sufficiente per confutare
Pensavo che $ m $ fossero le lettere della B , beh per il caso da me esposto la soluzione dovrebbe essere corretta.
A me verrebbe da dire, molto prosaicamente, $((n),(n/2))$ o, in caso di $n$ dispari $((n),((n+1)/2))$. Nel seguito tratto solo il caso di $n$ pari ma per $n$ dispari il procedimento è identico.
Il numero di $A$, nel seguito $n_A$, nella lettura da sinistra a destra deve essere maggiore o uguale in ogni momento a $n_B$, il numero di B nella parola da $n$ lettere, quindi $n_A$ deve essere necessariamente maggiore o uguale a $n/2$. Per un $i$ fissato compreso tra $n/2$ e $n$, per le motivazioni espresse in questo post (facendo corrispondere i movimenti verso est alle $A$ e i movimenti verso nord alle $B$), il numero valido di parole è $((n),(i))-((n),(i+1))$ (in caso di $i=n$, la scrittura $((n),(n+1))$ è da leggersi come zero). Dunque il numero totale di parole è
$\sum_{i=n/2}^{n} ((n),(i))-((n),(i+1))$ che è una telescopica dove sopravvive solo il termine $((n),(n/2))$
Il numero di $A$, nel seguito $n_A$, nella lettura da sinistra a destra deve essere maggiore o uguale in ogni momento a $n_B$, il numero di B nella parola da $n$ lettere, quindi $n_A$ deve essere necessariamente maggiore o uguale a $n/2$. Per un $i$ fissato compreso tra $n/2$ e $n$, per le motivazioni espresse in questo post (facendo corrispondere i movimenti verso est alle $A$ e i movimenti verso nord alle $B$), il numero valido di parole è $((n),(i))-((n),(i+1))$ (in caso di $i=n$, la scrittura $((n),(n+1))$ è da leggersi come zero). Dunque il numero totale di parole è
$\sum_{i=n/2}^{n} ((n),(i))-((n),(i+1))$ che è una telescopica dove sopravvive solo il termine $((n),(n/2))$
Non saprei dimostrarlo, ma componendo veramente le parole ho verificato che per qualsiasi $m>=n$ ed $0<=n<=4$ il numero di parole possibili è
$(m-n+1)((m+n)!)/((m+1)!n!)=((m+n)!)/(m!n!)-((m+n)!)/((m+1)!(n-1)!)$
Mando questa soluzione anche se decisamente incompleta perché forse se ne può ricavare qualche suggerimento.
$(m-n+1)((m+n)!)/((m+1)!n!)=((m+n)!)/(m!n!)-((m+n)!)/((m+1)!(n-1)!)$
Mando questa soluzione anche se decisamente incompleta perché forse se ne può ricavare qualche suggerimento.
Ciao,
la tua soluzione Giammaria dovrebbe essere sempre corretta.
Se chiamiamo $F(m,n)$ il numero di parole si ha che:
$F(m,n)=F(m-1,n)+F(m,n-1)$
(la somma si ottiene contando il numero di lettere che finiscono con $A$ e quelle che finiscono con $B$ )
e $F(m,0)=1$ , $F(0,n)=0$ per $n, m > 1$.
La formula di Giammaria rispetta la ricorrenza e le condizioni al contorno... Non è una vera soluzione nemmeno questa ma almeno ora sappiamo quale deve essere il risultato e forse troviamo una soluzione più convincente
...
ps: se può servire io avevo visto che:
$F(n,k)= \sum_{i=k}^n F(i,k-1)$ ma non ero andato troppo oltre se non trovando la funzione per piccoli valori di $n$ e $k$...
la tua soluzione Giammaria dovrebbe essere sempre corretta.
Se chiamiamo $F(m,n)$ il numero di parole si ha che:
$F(m,n)=F(m-1,n)+F(m,n-1)$
(la somma si ottiene contando il numero di lettere che finiscono con $A$ e quelle che finiscono con $B$ )
e $F(m,0)=1$ , $F(0,n)=0$ per $n, m > 1$.
La formula di Giammaria rispetta la ricorrenza e le condizioni al contorno... Non è una vera soluzione nemmeno questa ma almeno ora sappiamo quale deve essere il risultato e forse troviamo una soluzione più convincente
...ps: se può servire io avevo visto che:
$F(n,k)= \sum_{i=k}^n F(i,k-1)$ ma non ero andato troppo oltre se non trovando la funzione per piccoli valori di $n$ e $k$...
NB: .. le relazioni ricorsive vanno prese cum grano salis... la condizione m maggiore od uguale ad n va' tenuta in considerazione....
"giammaria":
Non saprei dimostrarlo, ma componendo veramente le parole ho verificato che per qualsiasi $m>=n$ ed $0<=n<=4$ il numero di parole possibili è
$(m-n+1)((m+n)!)/((m+1)!n!)=((m+n)!)/(m!n!)-((m+n)!)/((m+1)!(n-1)!)$
Mando questa soluzione anche se decisamente incompleta perché forse se ne può ricavare qualche suggerimento.
Ossia $((m+n),(m))-((m+n),(m+1))$, che è esattamente la formula che ho scritto io (ho semplicemente chiamato $n$ il numero totale di lettere, $i$ il numero di $A$ (sarebbe l'indice della sommatoria) e $n-i$ è di conseguenza il numero di $B$. Se non sai dimostrarlo, ho allegato la dimostrazione postando un link.
Ti ripeto il concetto se non ti è chiaro (lo stesso vale per Thomas a cui forse è sfuggito il mio commento).
$n$=numero di lettere
$i$=numero di $A$
$n-i$=numero di $B$
Per ogni $i>=n-i$ (ossia $i>=n/2$) la formula è quella che ho postato qualche giorno fa, ossia $((n),(i))-((n),(i+1))$.
Ora, $i$ può andare da $n/2$ a $n$.
Dunque il numero di parole ammissibili è
$\sum_{i=n/2}^{n} ((n),(i))-((n),(i+1))$
Ossia
$((n),(n/2))-((n),(n/2+1))+((n),(n/2+1))-((n),(n/2+2))+((n),(n/2+2))...-((n),(n))+((n),(n))-((n),(n+1))$
Tutti i termini si elidono e rimane solo $((n),(n/2))-((n),(n+1))$. L'ultimo termine vale zero (basta pensare alla definizione di coefficiente binomiale come $((n*(n-1)*(n-2)*...(n-k+1))/(k!))$. Ponendo $k=n+1$, il numeratore è uguale al prodotto di tutti gli interi compresi o uguali a $n$ e $n-k+1=n-(n-1)+1=n-n+1-1=0$. Quindi il numeratore si annulla, in quanto zero è un fattore).
Ho controllato per $n=1,2,3,4,5,6$ ($n$ è il numero totale di lettere) e la mia formula funziona.
$P_1=1=((1),(1))$
$P_2=2=((2),(1))$
$P_3=3=((3),(2))$
$P_4=6=((4),(2))$
$P_5=10=((5),(3))$
$P_6=20=((6),(3))$
Scusa consec non avevo visto che avevi scritto una soluzione! Appena posso cerco di seguire bene i tuoi ragionamenti! Scusa ancora 
( Sto leggendo ora e ti ringrazio di avere postato il link del problema collegato! Però next time non cambiare notazione nella scrittura della soluzione rispetto al testo del problema . $n$ a quanto capisco è il numero di lettere totali per te mentre nel testo è il numero di lettere $B$ )
. $n$ a quanto capisco è il numero di lettere totali per te mentre nel testo è il numero di lettere $B$ )
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo