Chiarimenti sulla tecnica del double counting

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Chiarimenti sulla tecnica del double counting

Messaggioda nico lol » 09/07/2019, 19:32

Ciao ragazzi, qualcuno potrebbe aiutarmi su questo esercizio che proprio non riesco a venirne a capo? magari qualche "hint"?
devo riuscire a capire come approcciare questo tipo di problemi perché non riesco... grazie in anticipo:
il libro mi riporta una dimostrazione "algebrica" che a me non piace per niente... se qualcuno magari può indicarmi qualche soluzione "geniale" è meglio.
Grazie :D
Non hai i permessi necessari per visualizzare i file allegati in questo messaggio.
nico lol
 
Messaggi: 22
Iscritto il: 15/03/2017, 21:59

Re: Chiarimenti sulla tecnica del double counting

Messaggioda afullo » 10/07/2019, 22:35

Hai provato per induzione? Per [tex]n=0[/tex] entrambi i membri vengono [tex]m+1[/tex], mentre nel passo induttivo si potrebbe provare ad utilizzare Stiefel. Magari domani provo.
afullo
 
Messaggi: 1643
Iscritto il: 13/03/2013, 22:06

Re: Chiarimenti sulla tecnica del double counting

Messaggioda matpro98 » 12/07/2019, 8:12

Sì, per induziome viene (ma forse è meglio su $m$). E, anche se non è una vera dimostrazione, viene pure per via "grafica"
matpro98
 
Messaggi: 60
Iscritto il: 24/04/2017, 11:36

Re: Chiarimenti sulla tecnica del double counting

Messaggioda nico lol » 12/07/2019, 13:46

Mi potresti dire per via “grafica” come funziona?
A me l’induzione esce, ma non mi pice, infatti cerco sempre metodi creativi (anche se sono scarso).
Comunque io ho provato a ragionare così ma non capisco il perché, non viene.
Allora, ho considerato il mio insieme composto da n+m+1 elementi.
Spezzo l'insieme in 2 sottoinsiemi:
Il primo, formato da n+1 elementi e il secondo formato da m elementi.
A questo punto devo trovare il numero di modi di scegliere n+1 elementi da n+m+1, quindi:
posso scegliere n+1 elementi da n+1 elementi (primo insieme).
Oppure posso scegliere n+1 elementi da n+1+1 elementi (cioè prendo un elemento dall'insieme m e lo aggiungo all'insieme n+1) e vado avanti cosi.
Tuttavia, mi esce una sommatoria, questo è vero, ma è sbagliata perche dovrebbe essere una sommatoria del tipo (n+k su n) e non (n+k su n+1). E' questo quello che non riesco a capire... :cry:
Grazie in anticipo.
nico lol
 
Messaggi: 22
Iscritto il: 15/03/2017, 21:59

Re: Chiarimenti sulla tecnica del double counting

Messaggioda matpro98 » 12/07/2019, 22:08

Per via grafica intendo con il triangolo di Tartaglia (o di Pascal), notoriamente legato ai coefficienti binomiali. Prova a vedere cosa succede lì al variare di $m$ e/o di $n$
matpro98
 
Messaggi: 60
Iscritto il: 24/04/2017, 11:36

Re: Chiarimenti sulla tecnica del double counting

Messaggioda ronny » 31/07/2019, 12:40

nico lol ha scritto:Mi potresti dire per via “grafica” come funziona?
A me l’induzione esce, ma non mi pice, infatti cerco sempre metodi creativi (anche se sono scarso).
Comunque io ho provato a ragionare così ma non capisco il perché, non viene.
Allora, ho considerato il mio insieme composto da n+m+1 elementi.
Spezzo l'insieme in 2 sottoinsiemi:
Il primo, formato da n+1 elementi e il secondo formato da m elementi.
A questo punto devo trovare il numero di modi di scegliere n+1 elementi da n+m+1, quindi:
posso scegliere n+1 elementi da n+1 elementi (primo insieme).
Oppure posso scegliere n+1 elementi da n+1+1 elementi (cioè prendo un elemento dall'insieme m e lo aggiungo all'insieme n+1)
e vado avanti cosi.

Così però mi sembra che tu riconti anche tutti i modi già contato quanto hai scelto n+1 elementi tra n+1 (che poi è un modo solo).
Semmai devi imporre che un elemento sia quello aggiunto e gli altri n (n+1-1) siano scelti tra n+1. Così ottieni nuovi modi di scegliere.
Prova con questa logica e vedi quanto viene.

nico lol ha scritto:Tuttavia, mi esce una sommatoria, questo è vero, ma è sbagliata perche dovrebbe essere una sommatoria del tipo (n+k su n) e non (n+k su n+1). E' questo quello che non riesco a capire... :cry:
Grazie in anticipo.
ronny
 
Messaggi: 25
Iscritto il: 20/04/2019, 23:28


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti