Newsgroup: it.hobby.enigmi
Titolo: scomposizioni di un'addizione

avevo un problema e ve lo propongo.
ho un mazzo da 52 carte.
si danno 13 carte a testa (4 giocatori quindi)
come si fa a calcolare quante sono le possibili disposizioni dei semi di un
giocatore?
ad esempio, alcune combinazioni possono essere (ogni numero indica il numero
di carte di ciascun seme):
13,0,0,0
4,3,3,3
9,2,2,0
5,4,3,1
.
.
...
etc.
la somma di ogni riga è naturalmente 13.
Io l'ho risolto manualmente. cioè ho creato tutte le combinazioni possibili,
ma sarei curioso di sapere se esiste un modo per calcolarlo senza la
bruteforce.
E quindi generalizzare il tutto per un numero n di carte.
ciao
Ale

 ha scritto nel messaggio
news:Yuxfd.2431$Ni.6...@twister1.libero.it...

dimenticavo di specificare che il numero di addendi era 4.
Nel caso generale,vogliamo trovare il numero di S di scomposizioni possibili
di un numero N>0 in K addendi interi positivi.
A me viene in mente qualcosa di ricorsivo,ma l'ora è tarda quindi ci ripenso
domani.
Ale

 giocatore?
-
.
.
S
P
O
I
L
E
R
.
.
-
In generale il numero di modi di posizionare n oggetti (n=13, le carte di ogni 
giocatore) in k cassetti (k=4, i semi) è dato dalla formula:
     (n+k-1)!
S = --------
     n!(k-1)!
Nel nostro caso S=560
Dade :)

 giocatore?... cut
 > dimenticavo di specificare che il numero di addendi era 4.
 > Nel caso generale,vogliamo trovare il numero di S di scomposizioni > 
 > > possibili
 > di un numero N>0 in K addendi interi positivi.
Volevo aggiungere qualche nota alla soluzione gia' data da Dade.
Stiamo parlando di partizioni. Un problema ben noto in teoria dei numeri.
Occorre fare subito una importande distinzione fra "partizioni ordinate" 
e "partizioni non ordinate"
Prendiamo ad es. 13 carte con 4 semi, per convenzione poniamo l'ordine 
dei semi: Cuori, Quadri, Fiore, Picche,
Se consideriamo come differenti le due seguenti mani:
13,0,0,0 tutte carte di cuori
0,13,0,0 tutte carte di quadri
allora stiamo parlando di partizioni non ordinate, ed il problema e' 
facilmente risolubile.
Nel caso contrario l'argomento diventa alquanto spinoso.
Vedi ad es:
http://mathworld.wolfram.com/PartitionFunctionP.html
.
Parliamo quindi di partizioni non ordinate.
Supponiamo di voler contare le mani possibili di 13 carte nei vari casi.
------Primo caso; sono presenti tutti i 4 semi.
Consideriamo una stringa di 13 "1" come questa:
1 1 1 1 1 1 1 1 1 1 1 1 1
utilizziamo ora 3 barrette spaziatrici, ogni arrangiamento dei 3 
separatori fra i 12 spazi corrisponde ad una partizione.
Ad es.
1 1|1 1|1 1 1 1 1 1 1|1 1 = 2,2,7,2
1|1 1 1|1 1 1 1 1 1|1 1 1 = 1,3,6,3 ecc.
e' chiaro che le 3 barrette nei 12 spazi trovano C(12,3)=220 
combinazioni diverse.
-------Secondo caso; sono presenti solo 3 dei 4 semi.
Per dividere la mia stringa in 3 gruppi, mi bastano 2 separatori:
C(12,2)= 66 casi, questi pero' vanno moltiplicati per 4 (i possibili 
semi esclusi).
  In altre parole la 7,4,2 ad esempio genera
0,7,4,2
7,0,4,2
7,4,0,2
7,4,2,0
Totale 66*4 =264
--------Terzo caso; sono presenti solo 2 semi.
C(12,1)= 12 che vanno moltiplicati per C(4,2)=6 le possibili posizioni 
dei due "0"  Totale 12*6 =72
--------Quarto caso; e' presente un solo seme Totale = 4
In tutto 220 + 264 + 72 + 4 = 560
Nel caso si volessero contare tutte le possibili partizioni ordinate di 
un intero n, e' chiaro dall'esempio visto sopra che in ciascuno degli 
n-1 spazi la barretta spaziatrice "c'e'" oppure "non c'e'"
il totale delle partizioni possibili e'= 2^(n-1)
Es. n=4  ---> 2^3=8
4
3+1
1+3
2+2
2+1+1
1+2+1
1+1+2
1+1+1+1

 ha scritto nel messaggio
news:TQOfd.28175$1q2....@tornado.fastwebnet.it...

Io mi riferivo quindi a partizioni ordinate, cioè senza ripetizione.
Nel caso delle tredici carte, la soluzione  è questa
      COMBINAZIONI     PROBABILITA PROBABIL %
      13-0-0-0 13 0 0 0 2,48E-24 0,0006%
      12-1-0-0 12 1 0 0 3,22E-23 0,0075%
      11-2-0-0 11 2 0 0 1,93E-22 0,0452%
      11-1-1-0 11 1 1 0 2,10E-22 0,0489%
      10-3-0-0 10 3 0 0 7,09E-22 0,1656%
      10-2-1-0 10 2 1 0 8,38E-22 0,1957%
      9-4-0-0 9 4 0 0 1,77E-21 0,4139%
      9-3-1-0 9 3 1 0 2,31E-21 0,5381%
      9-2-2-0 9 2 2 0 2,51E-21 0,5870%
      9-2-1-1 9 2 1 1 2,72E-21 0,6359%
      10-1-1-0 10 1 1 0 2,79E-21 0,6522%
      8-5-0-0 8 5 0 0 3,19E-21 0,7450%
      7-6-0-0 7 6 0 0 4,26E-21 0,9934%
      8-4-1-0 8 4 1 0 4,61E-21 1,0762%
      8-3-2-0 8 3 2 0 5,53E-21 1,2914%
      8-3-1-1 8 3 1 1 5,99E-21 1,3990%
      8-2-2-1 8 2 2 1 6,54E-21 1,5262%
      7-5-1-0 7 5 1 0 6,92E-21 1,6142%
      6-6-1-0 6 6 1 0 7,90E-21 1,8448%
      9-1-1-1 9 1 1 1 9,08E-21 2,1197%
      7-4-2-0 7 4 2 0 9,22E-21 2,1523%
      7-4-1-1 7 4 1 1 9,99E-21 2,3317%
      7-3-3-0 7 3 3 0 1,01E-20 2,3675%
      6-5-2-0 6 5 2 0 1,19E-20 2,7672%
      7-3-2-1 7 3 2 1 1,20E-20 2,7980%
      6-5-1-1 6 5 1 1 1,28E-20 2,9979%
      6-4-3-0 6 4 3 0 1,45E-20 3,3822%
      5-5-3-0 5 5 3 0 1,63E-20 3,8050%
      6-4-2-1 6 4 2 1 1,71E-20 3,9971%
      5-4-4-0 5 4 4 0 1,81E-20 4,2277%
      6-3-3-1 6 3 3 1 1,88E-20 4,3969%
      5-5-2-1 5 5 2 1 1,93E-20 4,4968%
      6-3-2-2 6 3 2 2 2,05E-20 4,7966%
      5-4-3-1 5 4 3 1 2,35E-20 5,4961%
      5-4-2-2 5 4 2 2 2,57E-20 5,9957%
      4-4-4-1 4 4 4 1 2,62E-20 6,1067%
      5-3-3-2 5 3 3 2 2,83E-20 6,5953%
      4-4-3-2 4 4 3 2 3,14E-20 7,3281%
      4-3-3-3 4 3 3 3 3,45E-20 8,0609%
      TOT     4,28E-19 100%
In tutto sono 39 partizioni possibili, ordinate per probabilità di uscita..
Dal calcolo ho scluso le possibili permutazioni, quindi può darsi che i
valori assoluti siano sbagliati, ma quelli percentuali dovrebbero essere
giusti (se qualcuno ha voglia di verificarlo...)
Per comodità, vi copio anche le combinazioni ordinate in ordine decrescente
      13 0 0 0
      12 1 0 0
      11 2 0 0
      11 1 1 0
      10 3 0 0
      10 2 1 0
      10 1 1 0
      9 4 0 0
      9 3 1 0
      9 2 2 0
      9 2 1 1
      9 1 1 1
      8 5 0 0
      8 4 1 0
      8 3 2 0
      8 3 1 1
      8 2 2 1
      7 6 0 0
      7 5 1 0
      7 4 2 0
      7 4 1 1
      7 3 3 0
      7 3 2 1
      6 6 1 0
      6 5 2 0
      6 5 1 1
      6 4 3 0
      6 4 2 1
      6 3 3 1
      6 3 2 2
      5 5 3 0
      5 5 2 1
      5 4 4 0
      5 4 3 1
      5 4 2 2
      5 3 3 2
      4 4 4 1
      4 4 3 2
      4 3 3 3
Ma allora non esiste una formuletta per calcolare queste partizioni
ordinate?

 ordinate?
Non e' cosi' semplice.
C'e' molto materiale a disposizione.
Leggiti i documenti linkati in fondo a questa pagina:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000041
Forse per i tuoi scopi e' piu' agevole adottare un sistema ricorsivo:
http://mathforum.org/library/drmath/view/55885.html
ciao

 ha scritto nel messaggio
news:VOUfd.29179$1q2....@tornado.fastwebnet.it...

grazie :)
a chi interessa,sto progettando un gioco di carte al computer (simile al
bridge) utilizzando tecniche di intelligenza artificiale.
Un lavoro molto ambizioso,ma ci si prova :)

       9-1-1-1 9 1 1 1 9,08E-21 2,1197%
[ecc]
Sta' attento che ci sono combinazioni con 12 carte
K