Chiarimenti sulla tecnica del double counting

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.
Rispondi
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Chiarimenti sulla tecnica del double counting

Messaggio da nico lol »

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.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Chiarimenti sulla tecnica del double counting

Messaggio da afullo »

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.
matpro98
Messaggi: 75
Iscritto il: 24/04/2017, 11:36

Re: Chiarimenti sulla tecnica del double counting

Messaggio da matpro98 »

Sì, per induziome viene (ma forse è meglio su $m$). E, anche se non è una vera dimostrazione, viene pure per via "grafica"
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Re: Chiarimenti sulla tecnica del double counting

Messaggio da nico lol »

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.
matpro98
Messaggi: 75
Iscritto il: 24/04/2017, 11:36

Re: Chiarimenti sulla tecnica del double counting

Messaggio da matpro98 »

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$
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Chiarimenti sulla tecnica del double counting

Messaggio da ronny »

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.
Rispondi