Calcolo combinatorio: formule per elementi ripetuti in N

Ciao Eremos,

l'insieme N è l'insieme degli elementi da permutare immagino, puoi definire un po' di notazione? Pr(N) per cosa sta?

Ciao Alpha,

N è l'insieme da permutare, combinare o disporre.

Pr (N) (o P' (N)) è la permutazione di N elementi non tutti diversi (elementi ripetuti in N).

Ad esempio, con N = ABCC  (CC si ripete 2 volte, quindi m=2)

P' (4, 2) = 4!/2! = 12:

ABCC ACBC ACCB BACC BCAC BCCA CABC CACB CBAC CBCA CCAB CCBA

Ciò che mi occorre è una formula analoga per le combinazioni e disposizioni (semplici e con ripetizioni).

Esempi con N = ABCC;   K = 2:

Combinazioni: AB AC BC CC

Combinazioni con ripetizioni: AA AB AC BB BC CC

Disposizioni: AB AC BA BC CA CB CC

Disposizioni con ripetizioni: AA AB AC BA BB BC CA CB CC

Ecco, per questi quattro casi non riesco a trovare la formula per il computo delle sequenze da nessuna parte, né ricavarla in alcun modo. 

Ciao Eremos,

per le disposizioni semplici la fomula è

per le disposizioni con ripetizioni

per le permutazioni semplici

per le permutazioni con ripetizione (m elementi uguali tra loro)

per le combinazioni semplici

e infine per le combinazioni con ripetizione

Namasté - Agente

Namastè, Omega,

grazie ma non è quello che sto cercando. Ho bisogno delle formule come quella per P(m)n, ossia che contemplino la possibilità di m, r, s, .... anche per le altre forme combinatorie (quindi ripetizioni previste negli elementi di N).

Come riporto negli esempi, il numero, ad esempio delle combinazioni per N=4 e K=2, si sa è N! / (k! (N-K!), ossia 6, ma se ho delle ripetizioni in N (e non in K, caso in cui varrebbe la formula C' (n, k)), il risultato è 4: come arrivo a questo risultato?

La differenza tra C (n, k) e C (n, k, m, r, s, ...) è che, essendo N = ABCC genera delle combinazioni uguali che vanno eliminate:

AB AC AC BC BC CC  ----> AB AC BC CC.

Lo so, non è un problema semplice, e in internet non c'è assolutamente nulla a riguardo, solo una infinità di siti che riportano le ben note formule da te anche ricordate.

Problema interessante.

Prova così, nel caso di un solo elemento ripetuto più volte in N.

dove R è il numero di volte che l'elemento ripetuto in N si ripete.

Se non dovesse funzionare, ragioniamoci insieme.

Ho provato anch'io a ricorrere per le combinazioni a qualcosa del genere, e spesso il risultato era corretto, ma appena variavo uno dei tre parametri...

La formula da te suggerita ad es. per n=6 e k=3 dà come risultato = 46 mentre invece quello esatto è 43.

Riporto i valori esatti (combinazioni semplici) per n da 4 a 10, k=3, rip=2-3:

rip = 2:

N ris

 4    3
 5    7
 6  14
 7  25
 8  41
 9  63
10 92

rip = 3:

N  ris.

 4   2
 5   4
 6   8
 7  15
 8  26
 9  42
10 64

Speravo che queste formule fossero riportate in qualche manualone avanzato di matematica, dal momento che se dovessimo partire da zero credo occorrerebbero parecchi mesi prima di mettere a punto queste formule (per tutte le forme combinatorie).

Mi stupirei molto se nessun matematico in passato si sia occupato di questo problema.

Per tale ragione, amico, credo sia meglio rinunciare e sperare che un giorno o si trovi il manualone o si trovi il matematico che decida di dedicare un bel po' di tempo della propria vita tra i numeri fattoriali.

Grazie comunque, lascio aperta la domanda un paio di giorni, non si sa mai...

Finalmente, per le combinazioni semplici con un solo elemento ripetuto p volte, ho ricavato la seguente formula:

C(p)(m, k) = sommatoria per "i=k" a "i=k-p" di C (n-p, i)

Le cose però si complicano se gli elementi ripetuti sono più di uno, e ancor di più se la loro somma è maggiore di k.

Namasté Eremos,

mi sembra opportuno spostare questa conversazione nel Forum. Perchè il problema è interessante e non è standard: più che il risultato, è importante la costruzione. Passiamo a parlarne in pubblica piazza, con il contributo di tutti gli utenti che siano interessati.