Calcolo combinatorio e combinazioni semplici spiegazione

 

 

Calcolo combinatorio e combinazioni semplici spiegazione

 

Questo sito utilizza cookie, anche di terze parti. Se vuoi saperne di più leggi la nostra Cookie Policy. Scorrendo questa pagina o cliccando qualunque suo elemento acconsenti all’uso dei cookie.I testi seguenti sono di proprietà dei rispettivi autori che ringraziamo per l'opportunità che ci danno di far conoscere gratuitamente a studenti , docenti e agli utenti del web i loro testi per sole finalità illustrative didattiche e scientifiche.

 

 

 

Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).

 

 

 

 

 

Calcolo combinatorio e combinazioni semplici spiegazione

 CALCOLO COMBINATORIO

Il calcolo combinatorio ha per obiettivo la costruzione di raggruppamenti  di oggetti distinti o no, che secondo un determinato criterio, si possono formare con oggetti di un certo insieme.

Esamineremo i seguenti raggruppamenti:

 

  • Permutazioni semplici
  • Disposizioni semplici
  • Combinazioni semplici
  • Permutazioni con ripetizione
  • Disposizioni con ripetizione
  • Combinazioni con ripetizione

 

 

PERMUTAZIONI SEMPLICI

 

Definizione: Si chiamano permutazioni semplici di n oggetti distinti, tutti i raggruppamenti diversi che si possono formare con gli oggetti dati, rispettando le seguenti proprietà:

  • Ciascun raggruppamento contiene n oggetti.
  • Uno stesso oggetto non può figurare più volte in un raggruppamento.
  • Due qualsiasi raggruppamenti sono da considerarsi distinti quando differiscono solo per l’ordine con cui sono disposti gli elementi.

 

La tabella seguente mostra le permutazioni al variare di n

 

Se n = 2:    1 2;  2 1.    

Se n = 3:    1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1.

Se n = 4:    1 2 3 4; 1 2 4 3; 1 3 2 4; 1 3 4 2;1 4 2 3; 1 4 3 2;

                  2 1 3 4; 2 1 4 3; 2 3 1 4; 2 3 4 1; 2 4 1 3; 2 4 3 1;

                  3 1 2 4; 3 1 4 2; 3 2 1 4; 3 2 4 1; 3 4 1 2; 3 4 2 1;

                  4 1 2 3; 4 1 3 2; 4 2 1 3; 4 2 3 1; 4 3 1 2; 4 3 2 1;

                  

Si può notare che il numero delle permutazioni in funzione di n è dato da n!, quindi abbiamo nel caso di n=2, 2 permutazioni, per n=3, 6, e per n=4 , 24 permutazioni

 

L’algoritmo che permette di trovare tutte le permutazioni è espresso dalla funzione permuta().

Ci sono due cicli while perché si fa il confronto tra il successivo e il precedente, ma anche tra il valore corrispondente all’indice i trovato e i valori oltre questo indice fino ad n. Le due istruzioni if permettono di uscire dai cicli se è stata trovata un’altra permutazione. Ci sono anche  due funzioni: scambia() e inverso(). La prima serve a scambiare di posto due elementi in un vettore; la seconda consente di invertire gli elementi in un vettore, solo quando è necessario e a partire dall’indice i.

 

 

 

 

 

 

 

function permuta()

{i=n;segnale=false

 while(i>=2)

 {if(a[i]>a[i-1])

   {j=n

    while(j>=i)

     {if(a[j]>a[i-1])

       {segnale=true

        a=scambia(a,j,i-1)

        a=inverso(a,i)

       }

      if(segnale)

       j=i-1

      else

       j=j-1

     }

   }

   if(segnale)

    {i=1

     segnale=false

    }

   else

    i=i-1

  }

}

 

 

function scambia(v,a,b)

{var t

 t=v[a]

 v[a]=v[b]

 v[b]=t

 return v

}

 

function inverso(aa,k)

{var d,q,t

 d=aa.length-1

 q=(d-k-1)/2

 q=Math.floor(q)

 for (i=0;i<=q;i++)

   {

    t=aa[d-i]

    aa[d-i]=aa[k+i]

    aa[k+i]=t

   }

 return aa

}

 

 

Esempi:

n=3

123 132 213 231 312 321  

n=4         

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

roma roam rmoa rmao raom ramo orma oram omra omar oarm oamr mroa mrao mora moar maro maor arom armo aorm aomr amro amor

 

Per l’immissione dei valori e per la stampa si sono usate degli accorgimenti operativi. Nella funzione immissione vengono inizializzati due vettori: uno (a) che contiene i numeri in progressione e l’altro (s) che contiene i valori effettivamente immessi. Si opera sempre sul vettore a, poi al momento della stampa gli elementi di a saranno gli indici di s.

 

function immissione()

{ p=""

  n=prompt("immetti n","")

  n=Number(n)

  for (i=1;i<=n;i++)

   { a[i]=i

     s[i]=prompt(i,"")

   }

  nperm=fatt(n)

  cont=1

  stampa(n,a)

}

 

function stampa(num,v)

{

  for (i=1;i<=num;i++)

  p=p+s[v[i]]

  p=p+" "

  document.form1.mostra.value=p

}

 

Le funzioni che seguono servono a stampare il numero delle permutazioni, che sappiamo è il fattoriale di n.

 

function fatt()

{var f

 f=1

 for (i=1;i<=n;i++)

 f=f*i

 return f

}

 

 

function stampanumpermutazioni()

{ document.form2.NPermutazioni.value=nperm}

 

Le successive funzioni consentono di eseguire l’algoritmo.

 

function ferma()

{ clearInterval(tempo)

}

 

function calcolaTempo(t)

{

 tempo=setInterval("calcola()",t)

 }

 

function calcola()

{

if (cont==nperm)

   ferma()

 else 

   {cont=cont+1

    permuta()

    stampa(n,a)

   }

 }             

 


Per visualizzare e stampare il programma completo occorre stampare il codice in HTML.

 

            

DISPOSIZIONI SEMPLICI.

 

Definizione : dati n oggetti distinti, e indicato con k un numero intero positivo e minore o uguale a n, si chiamano disposizioni semplici di questi n oggetti, presi a k a k (o di classe k),tutti i raggruppamenti diversi che si possono formare con gli oggetti dati, in modo che valgano le seguenti proprietà:

  1.  ciascun raggruppamento contiene k oggetti;
  2. uno stesso oggetto non può figurare più volte in un raggruppamento;

     3.  due qualsiasi raggruppamenti sono da considerarsi distinti quando uno di essi

    contiene almeno un  oggetto che non figura nell’altro, oppure gli oggetti di un

    raggruppamento sono gli stessi dell’altro ma differiscono per l’ordine con cui sono  

    disposti.

 

Per esempio, le disposizioni di tre oggetti(123) presi a due a due sono: 12; 13; 21; 23; 31; 32. Se facciamo un confronto con le permutazioni di tre oggetti ci si accorge che è possibile ricavare da queste le disposizioni, eliminando gli n-k elementi da ciascuna permutazione cioè:

 

 

 

Permutazioni:  123    132   213   231  312  321

Disposizioni:    12      13     21     23    31    32

 

Allora l’algoritmo per le disposizioni è analogo a quello delle permutazioni con l’accortezza che la stampa verrà fatta solo per i k elementi. Questo algoritmo, però,  va bene se k=n-1, per k<n-1 si hanno dei gruppi ripetuti. Per esempio se n=5 e k =3 alle permutazioni 12345; 12354 corrispondono le disposizioni 123 e 123. Con una funzione che ha il compito di confrontare se due successive disposizioni sono uguali si risolve il problema.

 

function disposizioni()

{i=n;segnale=false

 while(i>=2)

 {if(a[i]>a[i-1])

   {j=n

    while(j>=i)

     {if(a[j]>a[i-1])

       {segnale=true

        a=scambia(a,j,i-1)

        a=inverso(a,i)

       }

      if(segnale)

       j=i-1

      else

       j=j-1

     }

   }

   if(segnale)

    {i=1

     segnale=false

    }

   else

    i=i-1

  }

 

function copia(x,y,kk)

{

 for (c=1;c<=kk;c++)

  if(x[c]!=y[c])

    return false

 return true

 }  

 

La procedura immissione deve essere modificata per consentire l’input della classe k.

 

function immissione()

{ p=""

  n=prompt("immetti n. di elementi","")

  n=Number(n)

  k=prompt("raggruppati a","")

  k=Number(k)

  for (i=1;i<=n;i++)

  { a[i]=i

    s[i]=prompt(i,"")

  }

       ndisp=numeroDisposizioni(n,k)

       cont=1

       stampa(k,a)

}

Permettono di calcolare e stampare il numero delle disposizioni, che è dato dalla formula:

 

Dn,k=n(n-1)(n-2)…(n-k+1).

 

function numeroDisposizioni(n,k)

{var disp

disp=1

 for (i=n-k+1;i<=n;i++)

   disp=disp*i

 return disp

}

 

function stampanumdisposizioni()

{ document.form2.NDisposizioni.value=ndisp}

Permettono di eseguire il programma.

 

function assegna(aa,nn)

 { var bb = new Array()

 for(i=1;i<=nn;i++)

   bb[i]=aa[i]

 return bb 

 }

 

function calcola()

{

if (cont==ndisp)

   ferma()

 else 

   {b=assegna(a,n)

    disposizioni()

    if((copia(a,b,k)==false))

      {cont=cont+1

      stampa(k,a)}

  }

 }             

 

 

Esempi

 

n=4  k=2

12 13 14 21 23 24 31 32 34 41 42 43

 

n=4 k=3

123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432

 

n=4 k=4

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

 

 

 

 

COMBINAZIONI SEMPLICI

 

Definizione : dati n oggetti distinti, e indicato con k un numero intero positivo e minore o uguale a n, si chiamano combinazioni semplici di questi n oggetti, presi a k a k (o di classe k),tutti i raggruppamenti diversi che si possono formare con gli oggetti dati, in modo che valgano le seguenti proprietà:

1.  ciascun raggruppamento contiene k oggetti;

2.  uno stesso oggetto non può figurare più volte in un raggruppamento;

3. l'ordine degli oggetti non ha importanza,e quindi due raggruppamenti sono da  

considerarsi diversi   soltanto quando differiscono tra loro almeno per un oggetto.

 

Per esempio : con n=5 e k=3 si ha:

123; 124; 125; 134; 135; 145; 234; 235; 245; 345.  

 

 Si nota che le combinazioni non sono ordinate in senso decrescente, quindi con la funzione ordinaCrescente si eliminano i raggruppamenti da non considerare.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

function combinazioni()

{i=n;segnale=false

 while(i>=2)

 {if(a[i]>a[i-1])

   {j=n

    while(j>=i)

     {if(a[j]>a[i-1])

       {segnale=true

        a=scambia(a,j,i-1)

        a=inverso(a,i)

       }

      if(segnale)

       j=i-1

      else

       j=j-1

     }

   }

   if(segnale)

    {i=1

     segnale=false

    }

   else

    i=i-1

  }

}

function ordinaCrescente(x,d)

{var i

 for(i=1;i<=d-1;i++)

   if (x[i]>x[i+1])

     return true

 return false

 }   

 

 

Le funzioni seguenti calcolano il numero delle combinazioni, che è dato dalla formula:

 

Cn,k=Dn,k  / k!

 

function numerodisposizioni(n,k)

{var disp

 disp=1

 for (i=n-k+1;i<=n;i++)

  disp=disp*i

 return disp

}

 

function fatt(nn)

{var f

 f=1

 for (i=1;i<=nn;i++)

 f=f*i

 return f

return false 

}

function numerocombinazioni(n,k)

{var comb

 comb=Math.floor(numerodisposizioni(n,k)/fatt(k))

 return comb

}

Questa funzione esegue il programma.

 

function calcola()

{

if (cont==ncomb)

   ferma()

 else 

   {b=assegna(a,n)

    combinazioni()

    if(copia(a,b,k)==false)

       if (ordinaCrescente(a,k)==false)

         {cont=cont+1

          stampa(k,a)

         }

   }

}             

 

 

Esempi:

 

n=4 k=2

12 13 14 23 24 34

 

n=4 k=3

123 124 134 234

 

n=4 k=4

1234

 

 

 

 

PERMUTAZIONI CON RIPETIZIONE

 

Definizione: Dati n oggetti distinti, si chiamano permutazioni con ripetizione tutti i

                   raggruppamenti che si possono formare con gli n oggetti dati, in modo che 

                   valgono le seguenti proprietà:

  • Ogni raggruppamento contiene n oggetti.
  • In ogni raggruppamento uno stesso oggetto può essere ripetuto sino ad un massimo di n volte.
  • Due raggruppamenti sono distinti quando uno di essi contiene almeno un elemento che non compare nell’altro; oppure contengono gli stessi oggetti, ma almeno uno di essi è ripetuto un numero diverso di volte; oppure, pur contenendo gli stessi oggetti e ripetuti lo stesso numero di volte, questi differiscono per l’ordine con cui sono disposti.

 

L’algoritmo che trova le permutazioni è stato costruito cosi:

Si inizia attribuendo ad i il numero massimo degli elementi e se l’elemento corrispondente cioè a[i] è diverso da n allora si incrementa di 1 e si stampa; si continua così finchè l’ultimo elemento non raggiunge il massimo. Quando si verifica questo fatto viene incrementato l’elemento precedente e l’ultimo viene posto ad 1. Si ripete il procedimento.

Notare che nella funzione immissione il vettore a è formato da tutti 1.

 

 

 

 

La funzione è la seguente

 

function permutazioniRip()

{var i,j

 for(i=n;i>=1;i--)

   { if (a[i]!=n)

       {a[i]=a[i]+1

        for(j=i+1;j<=n;j++)

          a[j]=1

        break

        }

    }

 }     

 

Calcola il numero di permutazioni con ripetizione.

La formula è : nn

function numeropermutazioniRip(n,n)

{var permr

 permr=1

 for (i=1;i<=n;i++)

  permr=permr*n

 return permr

}

function stampanumpermutazioniRip()

{ document.form2.NPermutazioniRip.value=nperm}

 

La funzione immissione

 

function immissione()

{ p=""

  n=prompt("immetti n. di elementi","")

  for (i=1;i<=n;i++)

    { a[i]=1

      s[i]=prompt(i,"")}

       nperm=numeropermutazioniRip(n,n)

       cont=1

       stampa(n,a)

}

{

Esegue il programma.

 

function calcola()

{

  if(cont==nperm)

     ferma()

  else  

     {permutazioniRip()

      cont=cont+1

      stampa(n,a)}

 }

 

 

 

 

 

 

 

 

Esempi:

 

N=3

111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333

 

 

DISPOSIZIONI CON RIPETIZIONE

 

Definizione: Dati n oggetti distinti, e indicato con k un numero intero positivo (anche maggiore di n) si chiamano disposizioni  con ripetizione di questi n oggetti presi a k a k tutti i raggruppamenti diversi che si possono formare in modo che valgono le seguenti proprietà:

  • Ogni raggruppamento contiene k oggetti.
  • In ogni raggruppamento uno stesso oggetto può essere ripetuto sino ad un

     massimo di k volte.

  • Due raggruppamenti sono distinti quando uno di essi contiene almeno un elemento

     che non compare nell’altro; oppure contengono gli stessi oggetti, ma almeno uno di

     essi è ripetuto un numero diverso di volte; oppure, pur contenendo gli stessi oggetti

         e ripetuti lo stesso numero di volte, questi differiscono per l’ordine con cui sono

         disposti.

 

 

function disposizioniRip()

{var i,j

 for(i=r;i>=1;i--)

   { if (a[i]!=n)

       {a[i]=a[i]+1

        for(j=i+1;j<=r;j++)

          a[j]=1

        if ((copia(a,b,k)==false))

          break

        }

    }

 }     

Calcola il numero delle disposizioni con ripetizione.

La formula è : nk

function numerodisposizioniRip(n,k)

{var dispr

 dispr=1

 for (i=1;i<=k;i++)

  dispr=dispr*n

 return dispr

}

function stampanumdisposizioniRip()

{ document.form2.NDisposizioniRip.value=ndisp}

 

 

function immissione()

{ p=""

  n=prompt("immetti n. di elementi","")

  n=Number(n)

  k=prompt("raggruppati a","")

  k=Number(k)

  for (i=1;i<=n;i++)

    s[i]=prompt(i,"")

  for (i=1;i<=k;i++)

    a[i]=1

       ndisp=numerodisposizioniRip(n,k)

       cont=1

       stampa(k,a)

}

Esegue il programma

 

function calcola()

{ if (k>n)

    r=k

  else

    r=n 

  if(cont==ndisp)

    ferma()

  else 

     { b=assegna(a,k)

       disposizioniRip()

       cont=cont+1

       stampa(k,a)

     }

 }

 

 

 

Esempi

n=4 k=2

11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44

 

n=3 k=2

11 12 13 21 22 23 31 32 33

 

n=3 k=3

111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333

 

n=2 k=3

111 112 121 122 211 212 221 222

 

 

 

 

COMBINAZIONI CON RIPETIZIONE

 

Definizione: Dati n oggetti distinti, e indicato con k un numero intero positivo (anche maggiore di n) si chiamano disposizioni  con ripetizione di questi n oggetti presi a k a k tutti i raggruppamenti diversi che si possono formare in modo che valgono le seguenti proprietà:

1.   Ogni raggruppamento contiene k oggetti.

2.  In ogni raggruppamento uno stesso oggetto può essere ripetuto sino ad un

     massimo di k volte.

  • Due raggruppamenti sono distinti quando uno di essi contiene almeno un elemento

     che non compare nell’altro; oppure contengono gli stessi oggetti, ma non sono

     ripetuti lo stesso numero di volte. L’ordine non conta.

 

 

 

function combinazioniRip()

{

 for(i=r;i>=1;i--)

   { if (a[i]!=n)

       {a[i]=a[i]+1

        for(j=i+1;j<=r;j++)

          a[j]=1

        if  (copia(a,b,k)==false)

            break

        }

    }

 }  

function ordcomb(aa,m)

{

  for(i=1;i<=m-1;i++)

    if(aa[i]>aa[i+1])

      return false

  return true

  } 

Calcola il numero delle combinazioni con ripetizione.

 

La formula è:((n+k-1)(n+k-2)…(n+1)n) / k!

 

function numerocombinazioniRip(n,k)

{var tt,q,ncombr

 tt=n+k-1

 q=1

 for (i=tt;i>=n;i--)

   q=q*i

 kfatt=1 

 for (i=k;i>=1;i--)

   kfatt=kfatt*i

 ncombr=q/kfatt

 return ncombr

}

function stampanumcombinazioniRip()

{ document.form2.NCombinazioniRip.value=ncomb}

Esegue il programma.

 

function calcola()

{ if (k>n)

    r=k

  else

    r=n 

  if(cont==ncomb)

     ferma()

  else  

    { b=assegna(a,k)

   combinazioniRip()

    if (ordcomb(a,k)==true)

      {cont=cont+1

      stampa(k,a)}

   }

 }

 

     

Esempi

 

n=4 k=2

11 12 13 14 22 23 24 33 34 44

 

n=3 k=2

11 12 13 22 23 33

 

n=3 k=3

111 112 113 122 123 133 222 223 233 333

 

 

Bibliografia

Page-Wilson, La combinatoria computazionale, Muzzio,1980, Padova.

Nicolò Pintacuda, Algoritmi elementari, Muzzio,1986, Padova.

Mario Battelli, Corso di matematica sperimentale e laboratorio, Le Monnier1994, Milano.

 

 

Fonte: http://www.itisavoia.ch.it/giardina/calccomb/CalcoloCombinatorio.doc

Sito web da visitare: http://www.itisavoia.ch.it

Autore del testo: G.Giardina

Nota : se siete l'autore del testo sopra indicato inviateci un e-mail con i vostri dati , dopo le opportune verifiche inseriremo i vostri dati o in base alla vostra eventuale richiesta rimuoveremo il testo.

Parola chiave google : Calcolo combinatorio e combinazioni semplici spiegazione tipo file : doc

 

Calcolo combinatorio e combinazioni semplici spiegazione

 

 

 

Visita la nostra pagina principale

 

Calcolo combinatorio e combinazioni semplici spiegazione

 

Termini d' uso e privacy

 

 

 

 

Calcolo combinatorio e combinazioni semplici spiegazione