Sistemato il tex.
Francesco
Complimenti ai ragazzi che hanno rinnovato il forum e lo gestiscono al meglio!
ecco un quesito per i più giovani:
si mostri che
$ 2^n -n-1=\displaystyle\sum_{k=1}^{n-1}k2^{n-k-1} $
provate anche con un "ragionamento combinatorio"
Se la scritura non è comprensibile appena ho dieci minuti lo posto con LaTex(di cui come avrete capito non sono un mago!)
Dimostrare l' identità
-
HarryPotter
- Moderatore
- Messaggi: 354
- Iscritto il: 01 gen 1970, 01:00
- Località: Pavia
Spero di essere considerato tra "i più giovani", altrimenti siete liberi di fustigarmi:
Possiamo vedere la sommamatoria in questione in altro modo, cioè:
$ $$\displaystyle\sum_{k=1}^{n-1}k2^{n-k-1}= \sum_{k=0}^{n-2}2^{k}+\sum_{k=0}^{n-3}2^{k}+ \cdots + (2+1)+1$$ $
Queste possono essere viste come tante serie geometriche, da cui per formula abbiamo che il tutto è uguale a:
$ $$\displaystyle\left({\frac{2^{n-1}-1}{2-1}}\right) + {\left(\frac{2^{n-2}-1}{2-1}\right)} + {\cdots} + {\left(\frac{4-1}{2-1}\right)}+ 1$$ $
ovvero a:
$ $$\displaystyle(2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2+1)-n$$ $
che è appunto uguale a:
$ $$\displaystyle2^n-n-1$$ $
Rimane il ragionamento combinatorio...
@Bollazzo: Non ti ricorda qualcosa?
Possiamo vedere la sommamatoria in questione in altro modo, cioè:
$ $$\displaystyle\sum_{k=1}^{n-1}k2^{n-k-1}= \sum_{k=0}^{n-2}2^{k}+\sum_{k=0}^{n-3}2^{k}+ \cdots + (2+1)+1$$ $
Queste possono essere viste come tante serie geometriche, da cui per formula abbiamo che il tutto è uguale a:
$ $$\displaystyle\left({\frac{2^{n-1}-1}{2-1}}\right) + {\left(\frac{2^{n-2}-1}{2-1}\right)} + {\cdots} + {\left(\frac{4-1}{2-1}\right)}+ 1$$ $
ovvero a:
$ $$\displaystyle(2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2+1)-n$$ $
che è appunto uguale a:
$ $$\displaystyle2^n-n-1$$ $
Rimane il ragionamento combinatorio...
@Bollazzo: Non ti ricorda qualcosa?
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Questa soluzione non è combinatoria 
però un’induzione piccola piccola non fa mai male 
..
1) se n=2: 4-2-1=2^{2-1-1}=1
2)Hp: $ 2^n-n-1 $ = $ \sum^{n-1}_{k=1} k2^{n-k-1} $
Th: $ 2*2^n-n-1-1 $= $ \sum^{n}_{k=1} k2^{n-k} $
$ 2*2^n-n-1-1=2(2^n-n-1)+n $= $ 2(\sum^{n-1}_{k=1} k2^{n-k-1})+n $= $ (\sum^{n-1}_{k=1} k2^{n-k})+n $= $ (\sum^{n-1}_{k=1} k2^{n-k})+n*2^{n-n} $ = $ \sum^{n}_{k=1} k2^{n-k} $
che è la tesi.
Buona giornata. Simone
però un’induzione piccola piccola non fa mai male ..1) se n=2: 4-2-1=2^{2-1-1}=1
2)Hp: $ 2^n-n-1 $ = $ \sum^{n-1}_{k=1} k2^{n-k-1} $
Th: $ 2*2^n-n-1-1 $= $ \sum^{n}_{k=1} k2^{n-k} $
$ 2*2^n-n-1-1=2(2^n-n-1)+n $= $ 2(\sum^{n-1}_{k=1} k2^{n-k-1})+n $= $ (\sum^{n-1}_{k=1} k2^{n-k})+n $= $ (\sum^{n-1}_{k=1} k2^{n-k})+n*2^{n-n} $ = $ \sum^{n}_{k=1} k2^{n-k} $
che è la tesi.
Buona giornata. Simone
Riguardo alla dimostrazione costruttiva mi rendo conto che pur non essendo niente di metafisico non è così immediato trovarla.
Come avrete capito l' identità l' ho ottenuta risolvendo in due modi diversi un problema combinatorio ma la domanda che vi ripongo è: quale?
In effetti per identificarlo ci vuole un pò di flessibilità , provate con un tipo un poco speciale di permutazione...
Forza Enomis!!!
Come avrete capito l' identità l' ho ottenuta risolvendo in due modi diversi un problema combinatorio ma la domanda che vi ripongo è: quale?
In effetti per identificarlo ci vuole un pò di flessibilità , provate con un tipo un poco speciale di permutazione...
Forza Enomis!!!
Dunque
Inizio col verificare che $ n+1 $ sono combinazioni con ripetizione (che da ora abbrevierò con $ C_r $di 2 oggetti di classe n. La formula per le $ C_r $ di k oggetti di classe n è:
$ \displaystyle \frac{(k+n-1)!}{n!(k-1)!} $
Sostituisco k con 2 ed ho:
$ \displaystyle \frac{(n+1)!}{n!}=n+1 $
Perciò il primo membro è formato dalle stringhe date da una disposizione con ripetizione $ 2^n $ meno le $ C_r $.
Le $ C_r $ io le vedo così per esempio in 4 posti (n=4) (B=bianco, N=nero):
NNNN
NNNB
NNBB
NBBB
BBBB
In quale altro modo posso contare quelle stringhe che avanzano? Per prime sommo quelle che hanno la prima casella bianca; quindi fissata la prima casella posso disporre le rimanenti le caselle sono $ n-1 $ perciò le disposizioni sono $ 2^{n-1} $ però devo sottrarne 1 perché altrimenti conto anche la stringa tutta bianca: B BBB. Conclusione le prime che sommo sono $ 2^{n-1}-1 $. Ora conto quelle che hanno la prima casella nera e la seconda bianca (fissando perciò NB) e dispongo come voglio le caselle rimanenti in $ 2^{n-2}-1 $ modi, c’è sempre il –1 perché altrimenti conterei, come nell’esempio, anche NB BB. Continuo così fissando sta volta le prime due nere e poi una bianca (NNB) trovando così $ 2^{n-3}-1 $ e così via finché $ n-k=1 $ perciò $ k=n-1 $ che significa che ho sommato $ n-1 $ termini quindi avrò:
$ \displaystyle 2^{n-1}+2^{n-2}+2^{n-3}+\cdots;.-(n-1)= $
$ \displaystyle 2^{n-1}+2^{n-2}+2^{n-3}+\cdots;.+1-n $
Che è uguale al secondo membro come ha notato HarryPotter facendo il ragionamento inverso
P.P.S. Non credo sia la soluzione combinatorica che volevi tu, probabilmente ne esiste una migliore.
Inizio col verificare che $ n+1 $ sono combinazioni con ripetizione (che da ora abbrevierò con $ C_r $di 2 oggetti di classe n. La formula per le $ C_r $ di k oggetti di classe n è:
$ \displaystyle \frac{(k+n-1)!}{n!(k-1)!} $
Sostituisco k con 2 ed ho:
$ \displaystyle \frac{(n+1)!}{n!}=n+1 $
Perciò il primo membro è formato dalle stringhe date da una disposizione con ripetizione $ 2^n $ meno le $ C_r $.
Le $ C_r $ io le vedo così per esempio in 4 posti (n=4) (B=bianco, N=nero):
NNNN
NNNB
NNBB
NBBB
BBBB
In quale altro modo posso contare quelle stringhe che avanzano? Per prime sommo quelle che hanno la prima casella bianca; quindi fissata la prima casella posso disporre le rimanenti le caselle sono $ n-1 $ perciò le disposizioni sono $ 2^{n-1} $ però devo sottrarne 1 perché altrimenti conto anche la stringa tutta bianca: B BBB. Conclusione le prime che sommo sono $ 2^{n-1}-1 $. Ora conto quelle che hanno la prima casella nera e la seconda bianca (fissando perciò NB) e dispongo come voglio le caselle rimanenti in $ 2^{n-2}-1 $ modi, c’è sempre il –1 perché altrimenti conterei, come nell’esempio, anche NB BB. Continuo così fissando sta volta le prime due nere e poi una bianca (NNB) trovando così $ 2^{n-3}-1 $ e così via finché $ n-k=1 $ perciò $ k=n-1 $ che significa che ho sommato $ n-1 $ termini quindi avrò:
$ \displaystyle 2^{n-1}+2^{n-2}+2^{n-3}+\cdots;.-(n-1)= $
$ \displaystyle 2^{n-1}+2^{n-2}+2^{n-3}+\cdots;.+1-n $
Che è uguale al secondo membro come ha notato HarryPotter facendo il ragionamento inverso
P.S. Grazie Herry perchè questa soluzione l'avevo già trovata però non sapevo come trasformarla nel secondo membroHarryPotter ha scritto: $ \displaystyle(2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2+1)-n $
ovvero a
$ \displaystyle\left({\frac{2^{n-1}-1}{2-1}}\right) + {\left(\frac{2^{n-2}-1}{2-1}\right)} + {\cdots} + {\left(\frac{4-1}{2-1}\right)}+ 1 $
$ \displaystyle\sum_{k=0}^{n-2}2^{k}+\sum_{k=0}^{n-3}2^{k}+ \cdots + (2+1)+1=\sum_{k=1}^{n-1}k2^{n-k-1} $
P.P.S. Non credo sia la soluzione combinatorica che volevi tu, probabilmente ne esiste una migliore.
"Forse questo mondo è l'inferno di un'altro pianeta."
Aldous Huxley
Aldous Huxley
Molto bene Iron, utilizzando il risultato di Harry hai saputo ottenere una soluzione almeno plausibile. Un "difetto" (sperando di non esser pignoli) si può forse trovare nel fatto che essa sia forse un pò troppo innaturale e artificiosa (mi riferisco al fatto che vedi il primo termine come somma di disposizioni e combinazioni). Inoltre dovresti cercare di correggere il "ragionamento combinatorio" per far discendere il secondo membro direttamente ( e non, nel tuo caso, mediante il risultato di Harry). Prova a vedere quel 2^n come la cardinalità dell' insieme delle parti di un insieme con card. n e ricorda quanto ho scritto sopra (pensa cioè ad una permutazione "VINCOLATA" di n elementi).
A questo punto non è difficile: non vi resta che interpretare quel "VINCOLATA" e avrete ottenuto il "problema generatore".
Tanto per fare un esempio , nei dérangements il vincolo è che il generico elemento i non può stare nella posizione i (dovrei mettere indici e sottoindici per esser preciso ma per un esempio dovrebbe andare) oppure considerate le permutazioni di n interi dove non avviene mai che i sia immediatamente seguito
da i+1 (provate a farlo!).
A questo punto non è difficile: non vi resta che interpretare quel "VINCOLATA" e avrete ottenuto il "problema generatore".
Tanto per fare un esempio , nei dérangements il vincolo è che il generico elemento i non può stare nella posizione i (dovrei mettere indici e sottoindici per esser preciso ma per un esempio dovrebbe andare) oppure considerate le permutazioni di n interi dove non avviene mai che i sia immediatamente seguito
da i+1 (provate a farlo!).
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Sia data una stringa di lunghezza n di palline rosse e blu indistinguibili se non per il colore.
Suppongo che abbia almeno 2 palline rosse.
Le possibili disposizioni sono (come si verifica facilmente) $ 2^n-n-1 $.
Immagino di disporre le palline ordinatamente (da 0 a n-1) lungo la retta dei numeri naturali.
Ad ogni pallina posso assegnare una coordinata (z)
Sia j=n-k la distanza tra la prima pallina rossa $ z_1 $ della stringa (ovvero la pallina rossa con la coordinata z più piccola) e l'ultima pallina rossa $ z_2 $ (intesa come $ z_2-z_1 $).
Sia la stringa delle palline comprese tra la prima rossa e l'ultima pallina rossa (estremi inclusi) chiamata S_j.
S_j è lunga n-k+1(ovvero comprende n-k+1 palline).
Le palline di S_j si dispongono in $ 2^{n-k-1} $ modi possibili poichè la prima e l'ultima hanno un colore fisso.
Sia il punto (inteso come coordinata z) in cui c'è la prima pallina rossa (ovvero la pallina rossa con la coordinata z più piccola) chiamato inizio della stringa S_j.
Nel caso (non accettabile) in cui non siano presenti palline rosse considero il punto di coordinata (n) come punto di inizio.
Posso verificare facilmente che l'inizio può essere (una volta fissato j) in k punti differenti.
Questo perchè le coordinate dell'inizio possibili sono n+1 (anche se le due coordinate maggiori non sono mai accettate poichè non posso avere 1 o 0 palle rosse) e la lunghezza "occupata" da S_j è n-k+1 (quindi le ultime n-k+1 coordinate non sono disponibili come inizio) da cui deduco che gli inizi accettabili sono n+1-( n-k+1)=k.
Per ogni valore di j accettabile (e quindi per ogni valore di k accettabile) ho quindi $ k2^{n-k-1} $ disposizioni possibili.
Quindi le stesse configurazioni si contano anche in (facendo attenzione agli indici):
$ \sum^{n-1}_{k=1} k2^{n-k-1} $
Noto infatti che ho un solo inizio disponibile quando j=n-1 e S_j è lungo n; se S_j è lungo 2 (j=1) allora ho n-1 inizi possibili: non posso averne più di n-1 o meno di 1.
EDIT riscritto un pezzo di soluzione.
Buona Domenica.
Suppongo che abbia almeno 2 palline rosse.
Le possibili disposizioni sono (come si verifica facilmente) $ 2^n-n-1 $.
Immagino di disporre le palline ordinatamente (da 0 a n-1) lungo la retta dei numeri naturali.
Ad ogni pallina posso assegnare una coordinata (z)
Sia j=n-k la distanza tra la prima pallina rossa $ z_1 $ della stringa (ovvero la pallina rossa con la coordinata z più piccola) e l'ultima pallina rossa $ z_2 $ (intesa come $ z_2-z_1 $).
Sia la stringa delle palline comprese tra la prima rossa e l'ultima pallina rossa (estremi inclusi) chiamata S_j.
S_j è lunga n-k+1(ovvero comprende n-k+1 palline).
Le palline di S_j si dispongono in $ 2^{n-k-1} $ modi possibili poichè la prima e l'ultima hanno un colore fisso.
Sia il punto (inteso come coordinata z) in cui c'è la prima pallina rossa (ovvero la pallina rossa con la coordinata z più piccola) chiamato inizio della stringa S_j.
Nel caso (non accettabile) in cui non siano presenti palline rosse considero il punto di coordinata (n) come punto di inizio.
Posso verificare facilmente che l'inizio può essere (una volta fissato j) in k punti differenti.
Questo perchè le coordinate dell'inizio possibili sono n+1 (anche se le due coordinate maggiori non sono mai accettate poichè non posso avere 1 o 0 palle rosse) e la lunghezza "occupata" da S_j è n-k+1 (quindi le ultime n-k+1 coordinate non sono disponibili come inizio) da cui deduco che gli inizi accettabili sono n+1-( n-k+1)=k.
Per ogni valore di j accettabile (e quindi per ogni valore di k accettabile) ho quindi $ k2^{n-k-1} $ disposizioni possibili.
Quindi le stesse configurazioni si contano anche in (facendo attenzione agli indici):
$ \sum^{n-1}_{k=1} k2^{n-k-1} $
Noto infatti che ho un solo inizio disponibile quando j=n-1 e S_j è lungo n; se S_j è lungo 2 (j=1) allora ho n-1 inizi possibili: non posso averne più di n-1 o meno di 1.
EDIT riscritto un pezzo di soluzione.
Buona Domenica.
Bravo Enomis! Direi che la tua è un' ottima proposta.
Credo che l' essenziale sia quell' ALMENO , almeno conoscendo il problema originario. So per certo che esso è stato proposto a Cortona, 1998. Purtroppo non ho sottomano il testo esatto ed invito gentilmente chi l' abbia a "postarlo". Se non sbaglio dovrebbe anche trovarsi nella raccolta "Barsanti, Conti et alii".Suppongo che abbia almeno 2 palline rosse
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Come tu stesso mi hai fatto notare in "altra sede" (P.M.) il problema da me proposto non è agevolmente "riconducibile" all'originale di Cortona 1998.
Nel Cortona 98: 2^n è visto come la cardinalità dell' insieme delle parti di un insieme con card. n.
Nella mia proposta: 2^n è il numero di disposizioni con ripetizione con 2 "simboli" e "lunghezza" n (chiedo venia per il poco formalismo).
Si può però ricondurre la cardinalità dell' insieme delle parti di un insieme con card. n al numero di disposizioni con ripetizione con 2 "simboli" e "lunghezza" n:
Assegnamo un codice binario a ciascun elemento di un insieme di cardinalità n: 1 se l'elemento è nel sottoinsieme in considerazione e 0 se l'elemento non è nel sottoinsieme considerato.
Il numero totale dei sottoinsiemi risulta essere quindi il numero totale dei possibili codici binari (disposizioni con ripetizione con 2 "simboli" e "lunghezza" n)..ovvero 2^n.
Sia n>1 un intero. Trovare il numero di permutazioni $ (a_1,a_2...,a_n) $di (1,2,...,n) tali che esista e sia unico l'indice i $ \in $ {1,2,...,n-1} con $ a_i>a_{i+1} $.
Buon lavoro, e buona domenica. Simone.
Nel Cortona 98: 2^n è visto come la cardinalità dell' insieme delle parti di un insieme con card. n.
Nella mia proposta: 2^n è il numero di disposizioni con ripetizione con 2 "simboli" e "lunghezza" n (chiedo venia per il poco formalismo).
Si può però ricondurre la cardinalità dell' insieme delle parti di un insieme con card. n al numero di disposizioni con ripetizione con 2 "simboli" e "lunghezza" n:
Assegnamo un codice binario a ciascun elemento di un insieme di cardinalità n: 1 se l'elemento è nel sottoinsieme in considerazione e 0 se l'elemento non è nel sottoinsieme considerato.
Il numero totale dei sottoinsiemi risulta essere quindi il numero totale dei possibili codici binari (disposizioni con ripetizione con 2 "simboli" e "lunghezza" n)..ovvero 2^n.
Scusatemi la divagazione. Rilancio proponendo il poblema originale:quismulta ha scritto:Purtroppo non ho sottomano il testo esatto ed invito gentilmente chi l' abbia a "postarlo".
Sia n>1 un intero. Trovare il numero di permutazioni $ (a_1,a_2...,a_n) $di (1,2,...,n) tali che esista e sia unico l'indice i $ \in $ {1,2,...,n-1} con $ a_i>a_{i+1} $.
Buon lavoro, e buona domenica. Simone.