Problema di disposizioni
Salve a tutti, sono nuovo del forum ma, purtroppo, ho già un problema da porvi:
"Dato un vocabolario di P lettere dire quante sono tutte le parole di lunghezza T aventi K (con K <= T) lettere ciascuna ripetuta nella parola per almeno N volte".
Ho fatto qualche calcolo fissando dei numeri per P, T, K ed N e, considerando un vocabolario di 10 elementi (0...9), usando parole di lunghezza 6, e cercando fra queste quelle con almeno 2 simboli ripetuti ciascuno almeno 3 volte ho:
P = 10
T = 6
K = 2
N = 3
il che produce 1800 elementi. In questo caso vengono considerati validi tutti gli elementi del tipo: (333222, 323232, 111222, 112212, ecc...).
Vi ringrazio anticipatamente per le risposte.
"Dato un vocabolario di P lettere dire quante sono tutte le parole di lunghezza T aventi K (con K <= T) lettere ciascuna ripetuta nella parola per almeno N volte".
Ho fatto qualche calcolo fissando dei numeri per P, T, K ed N e, considerando un vocabolario di 10 elementi (0...9), usando parole di lunghezza 6, e cercando fra queste quelle con almeno 2 simboli ripetuti ciascuno almeno 3 volte ho:
P = 10
T = 6
K = 2
N = 3
il che produce 1800 elementi. In questo caso vengono considerati validi tutti gli elementi del tipo: (333222, 323232, 111222, 112212, ecc...).
Vi ringrazio anticipatamente per le risposte.
Risposte
Interessante... nessuna idea?
Io partirei dalla considerazione che K lettere ripetute nella parola di lunghezza T per almeno N elementi obbligano ad avere
$T/N>=K$
Io partirei dalla considerazione che K lettere ripetute nella parola di lunghezza T per almeno N elementi obbligano ad avere
$T/N>=K$
forse, ameno di scemenze sempre in agguato: con le NK lettere occupo i primi NK posti(e l'almeno è a posto). Gli anagrammi con queste sono (NK)!/(N!)^k.
Sui T-NK posti rimasti metto chi voglio tra le P lettere, in P^(T-NK) modi diversi, (come 1x2 sulla schedina, 3^13 modi).
Gli anagrammi fatti prima li posso , ora vedi tu , mettere in combinazioni di NK oggetti avendone T, o in disposizione, mah, direi la prima.
alla fine ho ((NK)!/(N!)^k)*P^(T-NK)*le combinazioni di cui sopra, o disposizioni.
(T!)*P^(T-NK)/((N!)^(K) *(T-NK)!......prova con numeri piccoli.
Sui T-NK posti rimasti metto chi voglio tra le P lettere, in P^(T-NK) modi diversi, (come 1x2 sulla schedina, 3^13 modi).
Gli anagrammi fatti prima li posso , ora vedi tu , mettere in combinazioni di NK oggetti avendone T, o in disposizione, mah, direi la prima.
alla fine ho ((NK)!/(N!)^k)*P^(T-NK)*le combinazioni di cui sopra, o disposizioni.
(T!)*P^(T-NK)/((N!)^(K) *(T-NK)!......prova con numeri piccoli.
eh sì,forse una scemenza c'è, ma la sistemi in fretta eventualmente
già è comunque un punto di partenza....
Ciao, ma come ti è venuto il 1800 con i tuoi numeri?
Ho fatto un rapido conto e mi è uscito 900 (la metà del tuo valore). Uno di noi due ha perso un due.
L'idea è (la mia):
parti scegliendo le K lettere dalle P.
A questo punto di devi mettere a permutarle (con un coefficiente multinomiale - o meglio con una somma di coefficienti multinomiali) dove la somma è estesa a tutte le combinazioni di ripetizioni di lettere tale che la somma dellelettere dia T e ciascuna compaia almeno K volte.
@hair: non ho capito bene il tuo ragionamento ma non mi pare corretto.
Ho fatto un rapido conto e mi è uscito 900 (la metà del tuo valore). Uno di noi due ha perso un due.
L'idea è (la mia):
parti scegliendo le K lettere dalle P.
A questo punto di devi mettere a permutarle (con un coefficiente multinomiale - o meglio con una somma di coefficienti multinomiali) dove la somma è estesa a tutte le combinazioni di ripetizioni di lettere tale che la somma dellelettere dia T e ciascuna compaia almeno K volte.
@hair: non ho capito bene il tuo ragionamento ma non mi pare corretto.
il 1800 è figlio di uno script scritto in python che altro non faceva se non permutare le lettere e verificare i casi uno per uno.
voleva essere simile al tuo, ma scemenzando, sai l'età...non scherza, non ho concluso, ma buttato giù ex ab rupto. Grazie per avermi ricordato il multinomiale. oggi tempo e voglia permettendo riguardo. Ciao e... bell'esercizio. ciao deje, ciao etr.
@hair: un saluto anche a te.
@etr: ho visto che hai postato anche su un altro forum ma ancora non mi è chiaro bene il problema. (è comunque leggermente diverso da come lo avevo interpretato).
Cerchiamo un attimo di formalizzarlo:
abbiamo un alfabeto ${A_1,...,A_P}$ di oggetti (lettere) distinti. Da questo costruiamo una parola di lunghezza $T$ che definisco con $(L_1,...,L_T)$, dove le $L$ sono scelte tra le $A$.
Ora creo una distribuzione di frequenze delle lettere distinte nella parola:
chiamo con $D_i$ la lettera i-esima (distinta) che compare nella parola e con $N_i$ quante volte essa si ripete; i scorre tra $1,...,M$ e $sum_{i=1}^MN_i=T$.
Quindi $M$ rappresenta il numero di lettere distinte nella parola. Chiaramente $M<=P$.
Fino a qua dovrebbe essere abbastanza corretto, veniamo alle condizioni che ancora non mi sono bene chiare.
Tu vuoi che tra le $M$ lettere distinte ce ne siano $K$ (uno protrebbe dire le prime distinte ad esempio) che si ripetono almeno $N$ volte (da qua ti viene $K<=M$) e le altre $M-K$ libere (queste "libere" possono ripetersi anche più volte di $N$, e quindi per esempio avere più di $K$ simboli con più di $N$ ripetizioni , o no?).
E' giusto questo? Ovviamente da qua ti si creano dei vincoli sulle variabili in gioco.
Vediamo di tradurre questo nel tuo esempio. Hai 10 simboli, crei una parola di 6 simboli e vuoi che ci siano almeno due simboli che si ripetano almeno 3 volte ciascuno.
Con questo setting tu hai che la tua parola sarà composta da esattamente due simboli che si ripetono ciascuno esattamente 3 volte.
In questo caso le parole sono 900 che calcoli come:
$((10),(2))=45$ scegli i due simboli (in maniera non ordinata) e poi li permuti con il coefficiente multinomiale (in questo caso binomiale) $((6),(3))=20$.
Tornando al problema generale l'idea sarebbe quella di creare strutture incompatibili sulla distribuzione dei $(D_i,N_i)$ lavorare con i coefficienti multinomiali e poi andare a fare un po'di somme. La cosa non è sempice e magari come ti veniva suggerito non si giunge ad una formula chiusa; però magari riesci a costruire un algoritmo (non ovviamente il semplice conteggio) che puoi fare su un programma.
@etr: ho visto che hai postato anche su un altro forum ma ancora non mi è chiaro bene il problema. (è comunque leggermente diverso da come lo avevo interpretato).
Cerchiamo un attimo di formalizzarlo:
abbiamo un alfabeto ${A_1,...,A_P}$ di oggetti (lettere) distinti. Da questo costruiamo una parola di lunghezza $T$ che definisco con $(L_1,...,L_T)$, dove le $L$ sono scelte tra le $A$.
Ora creo una distribuzione di frequenze delle lettere distinte nella parola:
chiamo con $D_i$ la lettera i-esima (distinta) che compare nella parola e con $N_i$ quante volte essa si ripete; i scorre tra $1,...,M$ e $sum_{i=1}^MN_i=T$.
Quindi $M$ rappresenta il numero di lettere distinte nella parola. Chiaramente $M<=P$.
Fino a qua dovrebbe essere abbastanza corretto, veniamo alle condizioni che ancora non mi sono bene chiare.
Tu vuoi che tra le $M$ lettere distinte ce ne siano $K$ (uno protrebbe dire le prime distinte ad esempio) che si ripetono almeno $N$ volte (da qua ti viene $K<=M$) e le altre $M-K$ libere (queste "libere" possono ripetersi anche più volte di $N$, e quindi per esempio avere più di $K$ simboli con più di $N$ ripetizioni , o no?).
E' giusto questo? Ovviamente da qua ti si creano dei vincoli sulle variabili in gioco.
Vediamo di tradurre questo nel tuo esempio. Hai 10 simboli, crei una parola di 6 simboli e vuoi che ci siano almeno due simboli che si ripetano almeno 3 volte ciascuno.
Con questo setting tu hai che la tua parola sarà composta da esattamente due simboli che si ripetono ciascuno esattamente 3 volte.
In questo caso le parole sono 900 che calcoli come:
$((10),(2))=45$ scegli i due simboli (in maniera non ordinata) e poi li permuti con il coefficiente multinomiale (in questo caso binomiale) $((6),(3))=20$.
Tornando al problema generale l'idea sarebbe quella di creare strutture incompatibili sulla distribuzione dei $(D_i,N_i)$ lavorare con i coefficienti multinomiali e poi andare a fare un po'di somme. La cosa non è sempice e magari come ti veniva suggerito non si giunge ad una formula chiusa; però magari riesci a costruire un algoritmo (non ovviamente il semplice conteggio) che puoi fare su un programma.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo