permutazioni

[seascoli]

Per vedere come spunta il 2, Newton ti aiuta con la sua formula della potenza N.ma di un binomio (spero ti sia nota):

$(p+q)^N=\sum_k^{0,N} ((N),(k))p^k q^(N-k)$

Questa formula è valida per ogni p e q (oltre che per ogni N).
Poni ora p=q=1 .... cosa ottieni?

[Nicos87]

(1+1)^N = 2^ N .. ma del pezzo a destra... N è k cambia e p e q perchè sono 1?

[adaBTTLS]

hai tot elementi. diciamo 7.
quanti sottoinsiemi puoi formare?
usiamo il modello biglie nelle scatole. hai sette biglie e due scatole. le sette biglie rappresentano i 7 elementi. le due scatole rappresentano le due possibilità che hai di "prendere o meno" i vari elementi per formare il "tuo" sottoinsieme. tutti i possibili modi distinti ti dànno tutti i possibili sottoinsiemi.
per ogni elemento puoi decidere se prenderlo opèpure no, se la risposta è sì metti la biglia corrispondente nella prima scatola, se al contrario la risposta è no la metti nella seconda.
dopo aver ripetuto l'operazione per 7 volte (le biglie sono 7), vai a vedere quali hai messo nella prima scatola, ed hai il tuo sottoinsieme.
in quanti modi potevi decidere? cioè quanti sono i possibili sottoinsiemi? per ogni elemento hai due scelte, le scelte sono indipendenti, quindi?
2*2*2*2*2*2*2 (2* se stesso 7 volte, cioè 2^7).
ma hai anche l'insieme vuoto ottenuto rispondendo 7 volte "no", ed hai anche tutto l'insieme, rispondendo 7 volte "sì".
questa volta i 7 colori potevi prenderli anche tutti, ma non nessuno. quindi dei due sotttoinsiemi impropri togliamo solo l'insieme vuoto.
è chiaro?
ti è piaciuta questa descrizione?
ciao!

[Nicos87]

bellissimo! ma allora se io ho, non so, diciamo 10 pezzi di stoffa e mi chiedo in quanti modi di versi posso cucirli, senza l'obbligo di cucirli tutti, posso usare lo stesso ragionamento? perchè ogni pezzo se lo voglio lo prendo, se no non lo uso, e posso però cucirli tutti insieme se mi va, ed avrei 2^ 10 -1, dove -1 è "mi rifiuto di cucire" ? grazie

[adaBTTLS]

se non ti interessa in quale ordine li vuoi cucire, sì.
questo ti dice solo in quanti modi puoi scegliere quali prendere.

[adaBTTLS]

una variante della formula si usa nei "sistemi automatici" per contare i bit, ... come saprai quando si parla di memoria di computer lo si fa sempre in termini di potenze del due (come numero di bit), perché appunto i vari codici dipendo da in-out, due scelte per ogni passaggio. infatti $2^n$ è il numero di parole distinte di $n$ lettere prese da un alfabeto di $2$ lettere, ed è quindi anche il numero di "numeri binari" di n cifre (compresi anche quelli che iniziano per 0, ovviamente). in tal caso due parole con le stesse lettere in ordine diverso sono distinte.
se vuoi confrontare i due procedimenti, quello che qui indica 1-0, in-out, nell'altro caso era sì-no, sempre due scelte. l'ordine era importante anche nell'altro caso, ma ci diceva se ad esempio l'elemento n. 5 faceva parte oppure no del sottoinsieme.

nel messaggio precedente ti ho detto che non distingui dall'ordine in cui vuoi cucire (disporre) le stoffe, come qui se disponi i numeri in ordine crescente avrai $2^n$ stringhe, se vuoi costruire un numero più grande utilizzando le stringhe base, i modi con cui puoi sceglierlo aumentano a dismisura...

spero di aver reso l'idea senza creare troppa confusione. ciao.

[seascoli]

Nycos87 ha scritto:

(1+1)^N = 2^ N .. ma del pezzo a destra... N è k cambia e p e q perchè sono 1?

Ovviamente, se in un'identità compare qualche simbolo, come $p$ o $q$, e ti si dice di porre $p=q=1$, s'intende che ciò vada fatto dappertutto , dovunque cioè figurino i simboli $p$ e a $q$, nella fattispecie sia a sinistra dell'uguale sia a destra dell'uguale. Se fai così, a sinistra, come tu stesso riconosci, ottieni $2^N$. Allo stesso tempo, però, a destra ti viene la sommatoria, nuda e cruda, di tutti i coeffic. binomiali $((N),(k))$ con $N$ fissato, cioè:
$\sum_{k=0}^{N}((N),(k))$
che pertanto deve essere uguale a $2^N$ qualunque sia $N$. Infatti:
$1+2+1=4=2^2$
$1+3+3+1=8=2^3$
$1+4+6+4+1=2^4$
etc...
Non la sapevi questa?

[Nicos87]

Scusate se vi rispondo con un po' di ritardo,
Per seascoli : no, non sapevo come maneggiare quella formula...
Per Ada: il concetto dei bit l'ho capito, forse un po' "concettualmente" e non proprio precisamente, ma va bene così

Grazie mille a entrambi !

[adaBTTLS]

prego.

se ti va, puoi provare a fare qualche altro esercizio. i seguenti sono tratti dalle dispense del mio prof.
- quanti anagrammi [si intende anche senza significato] si possono scrivere con la parola MATEMATICA ?
- quante sono le parole lunghe n su m lettere senza doppie [si intendono lettere successive uguali] ?
- in quanti modi si possono distribuire 10 caramelle a 3 bambini così che ogni bambino riceva almeno due caramelle ?

non ci sono le risposte, ma se ti va di svolgerli, posta il procedimento, e sicuramente riceverai commenti.
ciao.

[seascoli]

Ada scripsit:
- quante sono le parole lunghe n su m lettere senza doppie [si intendono lettere successive uguali] ?

Che significa "parole lunghe n su m lettere" ?