Domanda sullo stage della combinatoria

[Olivo3]

Sto guardando lo stage sulla combinatoria di Campobasso http://bioinf.dma.unipi.it/gobbino/Home ... Index.html
Per la domanda faccio riferimento a questo documento PDF http://olimpiadi.dm.unibo.it/downloads/Max/CB_C.pdf a pagina
A pagina 8 non ho capito il grafico del triangolo di Tartagli che ha fatto a sx della scritta: "FORMULA RICORSIVA": cos'è col.k? e col k+1? E quello sotto (affianco alla riga n+1) perchè è k+1? Poi non ho capito che senso ha la formula ricorsiva, potreste spiegarmela (compresa la dimostrazione usando i fattoriali)?
Prima di proseguire il video volevo chiarire questa cosa, in modo di proseguire con chiari i concetti che ha già trattato

[Claudio.]

Allora un coefficiente binomiale $ \binom{n}{k} $ è uguale al numero che compare alla riga n colonna k del triangolo di tartaglia.
Adesso una riga del triangolo di tartaglia si costruisce(lasciando stare le prime due) si costruisce iniziando con l'1 e continuando mettendo la somma dei due numeri sopra, quindi se indichiamo un numero tramite la sua riga e la sua colonna, $ (n,k) $, abbiamo che un numero $ (n+1,k+1) $ è uguale alla somma dei due sopra di lui, che sono $ (n,k) $ e $ (n,k+1) $(basta disegnare il triangolo e te ne accorgi), adesso abiamo detto che ogni numero corrisponde a un coefficiente binomiale quindi segue che $ \binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1} $dalla definizione di binomiale guardala quì:
http://it.wikipedia.org/wiki/Coefficiente_binomiale

[Olivo3]

Grazie mille, se ho altri dubbi li posto qua

[Olivo3]

Ciao, mi puoi dimostrare anche la formula con i fattoriali (quell'esercizio a fondo pagina)?
Sto continuando a guardare il video...Nella pagina dopo non ho capito cosa significa prendere k+1 dai primi n eprendere k dai primi n e aggiungere l'(n+1)-esimo... Mi puoi spiegare questa parte?
Poi nell'esercizio: "Qual'è la massima potenza di 2 che divide 2006!" perchè per saperlo bisogna fare questo procedimento (sommare gli esponenti di 2 di ciascun numero sino a 2006) per saperlo?
E poco dopo perchè per sapere con quanti zeri termina 2006! è importante sapere il numero dei fattori 5 e non anche quello dei fattori 2?

Grazie

[Claudio.]

1) Ti ho già dato il link.
2) è la dimostrazione combinatoria di quella formula, allora lui dice: $ \binom{n+1}{k+1} $ è il numero dei modi in cui si possono scegliere k+1 ragazzi su n+1. Adesso calcoliamo in altro modo queste possibilità, consideriamo gli n+1 ragazzi in due gruppo, in uno ci sono n ragazzi, nell'altro ce n'è solo 1. Adesso noi questi k+1 ragazzi li possiamo scegliere in due modi, cioè o scegliendoli solo tra gli n, cioè non prendendo quello da solo, oppure prendondo quello da solo e scegliendo irestanti k tra gli n, quindi tutte le possibilità sono la somma di queste due cioè $ \binom{n}{k+1}+ \binom{n}{k} $
3) Si, come vorresti farlo?
4) Perchè i fattori 2 sono sicuramente di più di quelli 5.

[Olivo3]

3) Si, come vorresti farlo?

No, volevo sapere perchè con questo procedimento si riesce a sapere qual'è la massima potenza di 2 che divide 2006!

Perchè i fattori 2 sono sicuramente di più di quelli 5.

Ma 10 si scompone con 2*5, quindi perchè non dobbiamo considerare solo i numeri che hanno come fattori sia 2 che 5, tipo 10, 20, 100, ecc?

[io.gina93]

-per ogni numero che ha come divisore un solo 5, moltiplicato per qualunque numero che ha come divisore 2 (e suoi multipli), il numero ottenuto è divisibile per 10.
-per ogni numero che ha come divisore 5^2, moltiplicato per qualunque numero che come divisore 4(e suoi multipli), il numero ottenuto è divisibile per 100.
-per ogni numero che ha come divisore 5^3, moltiplicato per qualunque numero che come divisore 8(e suoi multipli), il numero ottenuto è divisibile per 1000.
.....

esempi:
numeri che hanno come divisore un solo 5:
(5*3) ==>15 15*2=30, 15*4=60 15*6=90 ....
(5*7)==>35 35*2=70, 35*4=140, 35*6=210...

numeri che hanno come divisore 5^2:
5^2==>25 25*4=200, 25*8=200
[(5^2)+3]==>75 75*4=300, 75*8=600....

Nota Bene: è vero che puoi fare 25*2=50, ma in questo modo ti dimentichi uno zero.. poichè 25=5^2, devi moltiplicarlo per un numero che ha come divisore 2^2 e quindi 4, 8, 16 .... e quindi avrai 100, 200

spero di essermi spiegata bene...

[Olivo3]

Iogina,
Grazie pela risposta, ma mi sono rimasti due dubbi: perchè la guida considera solo i 5 e non 10 (2*5)? Facendo quindi 2006/10 + 2006/100, ecc?
Poi non ho capito cosa significa questa frase:

è vero che puoi fare 25*2=50, ma in questo modo ti dimentichi uno zero

, ma probabilmente non ho capito bene il senso di questa risoluzioine al problema: "qual'è la massima potenza di 2 che divide 2006!", quindi potresti/potreste rispondermi alla domanda precedente:

No, volevo sapere perchè con questo procedimento si riesce a sapere qual'è la massima potenza di 2 che divide 2006!

?
Grazie

[io.gina93]

quanti 2 ci sono in $ 2006! $?
come minimo 1003...(nel senso che ci sono 1003 numeri pari.. ma se proprio vuoi saperlo viene 1003+501+250+125+62+31+15+7+3+1=1998 quindi 2^1998 divide 2006!)

quanti 5 ci sono in $ 2006! $?
prima trovi tutti i multipli di 5==> 2006:5=401
poi i multipli di 25 (perchè hanno almeno due fattori 5)==> 2006:25=80
poi quelli di 125 (perchè hanno almeno 3 fattori 5)==> 2006:125=16
poi quelli di 625 (perchè hanno alemno 4 fattori 5)===>2006:625=3
non provo con 3125.. perchè non ci sta nel 2006..

401+80+16+3=500
quindi ci sono 500 cinque...==>5^500
per ottenere dei 10 ti servono 500 due, e li prendi dal 2^1998...
quindi, salvo errori, 2006! termina con 500 zeri..
________________________________________________________________________________________________________________________________

proviamo a seguire il tuo ragionamento (quello di trovare quanti 10 ci sono nel 2006!)
2006:10=200
2006:100=20
2006:1000=2

quindi ci sono 222 dieci... 10^222 divide 2006...
e allora 2006 termina con 222 zeri, che è SBAGLIATO!

quello che dice Gobbino è: dobbiamo trovare tutti i fattori 5 perchè il 10 è fatto da 5*2. di fattori 2 ne abbiamo a volontà, quindi trovati tot quantità di fattori 5, li moltiplichiamo per tot quantità di 2...

se non ne sei convinto prova a verificare con 5!
secondo te non dovrebbe terminare con zero, ma invece sì perchè 5!= 5 *4*3* 2 *1=120

[Olivo3]

ok, ho capito per il 5, mi puoi solo spiegare il perchè per sapere qual'è la massima potenza di un numero x che divide un numero y fattoriale bisogna fare questo procedimento. Adesso ho capito che funziona, ho capito il fatto che dobbiamo considerare il 5 e non il 2 nel caso sucessivo, ma mi resta questo dubbio, sul motivo di questa risoluzione al problema.
Spero di essere stato chiaro

[Claudio.]

No, non sei stato chiaro per niente, cosa significa il motivo della risoluzione? Vuoi dire forse come faccio a capire che devo fare così?
Allora lasciando perdere i fattoriali, se abbiamo due numeri a e b con a<b, trovare qual'è la massimo potenza di a che divide b, significa che se componiamo emtrambi in fattori primi ipotizziamo che $ a=x^n\cdot y^m $con $x^n<y^m$ in fattori primi, significa trovare quanti $ x^n\cdot y^m $ ci sono nella scomposizione in fattori primi di b, adesso se nella somposizione di b, ci sono più $ y^m $ che $ x^n $ è chiaro che il valore interessante è il numero degli $x^n$ perchè li devi accoppiare,quando finiscono gli $x^n$, per quanti $y^m$ ti possano rimanere non puo più fare un fattore $x^n\cdot y^m$.
Adesso se b forsse espresso direttamente( nel senso non come fattoriale, sommatoria, produttoria ecc), sarebbe facile, bastarebbe scomporlo in fattori primi e contare, quando abbiamo un fatoriale alto, è impossibile scrivere tutti i fattori primi quindi come facciamo?
Allora intanto in un fattoriale è chiaro il numero dei fattori di $x^n$ è maggiore se $x^n<y^m$, quindi ci basta trovare gli $y^m$, come facciamo? Te lo spiega il video...in modo più semplice mi sembra abbastana arduo da spiegare:
Allora il fatoriale è il prodotto dei numeri che vanno da 1 a un certo numero, essendo un prodotto per ogni multiplo ti un numero $y^m$ c'è almeno un fattore $y^m$, quanti sono i multipli di $y^m$ minori di un numero b? $\displaystyle\frac b{y^m}$. Adesso ho detto almeno uno, perchè per esempio il fattore $(y^m)^2$ e tutti i suoi multipli contengono 2 fattori e sono sempre multipli di $y^m$ che quindi noi abbiamo contato come 1, allora dobbiamo trovare tutti i multipli di $(y^m)^2)$ che sono $\displaystyle\frac b{(y^m)^2}$ e aggiungere 1 per questi, e così via per tutte le potenze di $y^m<b$.(nelle divisioni si prende sempre la parte intera)

[Olivo3]

Tutto chiaro, grazie a entrambi