Conteggio funzioni

dm.unipi.it/~berardu/Didattica/2013-14MD/2compito1luglio2014/2014lug1_MDwea.pdf
sapete come si risolve l'esercizio a pag 3 di calcolo combinatorio ?

Comments

  • MindFlyerMindFlyer Posts: 436
    edited March 2015
    Cito l'esercizio:

    Esercizio 3. Sia [tex]\mathbb N_{10}[/tex] l’insieme dei numeri naturali da 1 a 10 inclusi.
    a) Quante sono le funzioni [tex]f \colon \mathbb N_{10} \to \mathbb N_{10}[/tex] la cui immagine [tex]{\rm Im}(f)[/tex] ha almeno due elementi?
    b) Quante sono le le funzioni [tex]f \colon \mathbb N_{10} \to \mathbb N_{10}[/tex] la cui immagine [tex]{\rm Im}(f)[/tex] ha esattamente due elementi?
    c) Quante sono le le funzioni [tex]f \colon \mathbb N_{10} \to \mathbb N_{10}[/tex] la cui immagine [tex]{\rm Im}(f)[/tex] ha esattamente tre elementi?

    Sono un po' riluttante a darti la soluzione brutale perché è un esercizio molto standard. Facciamo che ti do prima qualche hint.

    a) Conta le funzioni che non appartengono all'insieme. E' molto più facile!

    b) Fissa prima i due elementi [tex]a[/tex] e [tex]b[/tex] dell'immagine. In quanti modi puoi fissarli? Una volta che li hai fissati, devi decidere quali dei 10 numeri vengono mandati in [tex]a[/tex] e quali in [tex]b[/tex], tenendo conto che almeno uno deve andare in [tex]a[/tex] e almeno uno deve andare in [tex]b[/tex]. Per evitare di contare la stessa funzione due volte, conviene anche qui ragionare sul complementare...

    c) Idem come sopra, ma con tre elementi anziché due. Scegli prima gli elementi dell'immagine (in quanti modi?), e poi conti le funzioni che vanno in tutti e tre. Di nuovo, per contarle senza incasinarti conviene contare il complementare, ovvero le funzioni la cui immagine sono al più due dei tre elementi. E per contare queste, devi prima scegliere i due elementi dell'immagine tra i tre che hai già scelto (in quanti modi?), e poi contare tutte le funzioni la cui immagine sono quei due elementi. Dopodiché riaggiungerai le funzioni la cui immagine è esattamente uno dei tre elementi (cf. principio di inclusione-esclusione).
  • BeagleGBeagleG Posts: 16
    edited March 2015
    a) questo primo punto lo risolverei appunto con il complemetare:

    tutto - le funzioni che vanno in un solo elemento:

    [tex]10^{10} - 10[/tex]

    b) sceglierei le funzioni che vanno in due elementi moltiplicate per il resto senza f(a) e f(b)

    [tex]\binom{10}{2} * 8^{10}[/tex]

    c) ...

    [tex]\binom{10}{3} * 7^{10}[/tex]


    ovviamente sono tutt'altro che sicuro
  • MindFlyerMindFlyer Posts: 436
    edited March 2015
    Eccomi, scusa.

    Ok per il punto a! :)

    Il punto b ha qualche problema. Giustamente dici che i modi per scegliere l'immagine sono [tex]{10 \choose 2}=45[/tex]. Ma poi non capisco quel [tex]8^{10}[/tex]. Dopo aver scelto l'immagine devi contare le funzioni con quell'immagine, ovvero le funzioni che mandano qualcosa in [tex]a[/tex] e qualcosa in [tex]b[/tex]. Dicevo di ragionare sul complementare, cioè contare le funzioni da [tex]\mathbb N^{10}[/tex] in [tex]\{a,b\}[/tex] la cui immagine non è tutto [tex]\{a,b\}[/tex], ovvero è solo [tex]\{a\}[/tex] o solo [tex]\{b\}[/tex]. Quindi questa parte è sostanzialmente uguale al punto a.

    Il punto c lo vediamo dopo.
  • BeagleGBeagleG Posts: 16
    MindFlyer wrote: »
    Eccomi, scusa.

    Ok per il punto a! :)

    Il punto b ha qualche problema. Giustamente dici che i modi per scegliere l'immagine sono [tex]{10 \choose 2}=45[/tex]. Ma poi non capisco quel [tex]8^{10}[/tex]. Dopo aver scelto l'immagine devi contare le funzioni con quell'immagine, ovvero le funzioni che mandano qualcosa in [tex]a[/tex] e qualcosa in [tex]b[/tex]. Dicevo di ragionare sul complementare, cioè contare le funzioni da [tex]\mathbb N^{10}[/tex] in [tex]\{a,b\}[/tex] la cui immagine non è tutto [tex]\{a,b\}[/tex], ovvero è solo [tex]\{a\}[/tex] o solo [tex]\{b\}[/tex]. Quindi questa parte è sostanzialmente uguale al punto a.

    Il punto c lo vediamo dopo.

    [tex]8^{10}[/tex] l'ho scritto per dire le rimaneti funzioni ovvero se due le ho fissate (parlo del codominio) a,b mi rimangono le rimanti funzioni da contare nel codomionio che sono 8 mentre quelle del dominio sono 10 quidi [tex]8^{10}[/tex], vorrei capire meglio il mio errore...
  • MindFlyerMindFlyer Posts: 436
    BeagleG wrote: »
    [tex]8^{10}[/tex] l'ho scritto per dire le rimaneti funzioni ovvero se due le ho fissate (parlo del codominio) a,b mi rimangono le rimanti funzioni da contare nel codomionio che sono 8 mentre quelle del dominio sono 10 quidi [tex]8^{10}[/tex], vorrei capire meglio il mio errore...

    Ok, è presto detto!
    Dopo che hai scelto i due elementi dell'immagine devi contare le funzioni con quell'immagine.
    Il suggerimento è di calcolare il complementare, ma la domanda è: il complementare rispetto a cosa?
    Non rispetto a tutte le funzioni del mondo, ma solo rispetto alle funzioni il cui codominio è [tex]\{a,b\}[/tex]. Queste sono facili da contare, e diciamo che sono [tex]X[/tex]. Il complementare delle tue funzioni rispetto a queste è anche facile da contare (l'hai fatto nel punto a), e diciamo che qui le funzioni sono [tex]Y[/tex].
    Allora il tuo risultato è [tex]{10 \choose 2} (X-Y)[/tex].
  • BeagleGBeagleG Posts: 16
    edited March 2015
    [tex]{10 \choose 2} (2^{10}-10)[/tex] ??.

  • MindFlyerMindFlyer Posts: 436
    Quasi... Come hai calcolato quell'[tex]Y[/tex]?
  • BeagleGBeagleG Posts: 16
    come tutte le funzioni che vanno in un solo elemento... forse ci sono
    [tex][/tex]
    BeagleG wrote: »
    [tex]{10 \choose 2} (2^{10}-10)[/tex] ??.
    il 10 sono tutte le funzioni che vanno in un solo elemento ... quindi è [tex]{10 \choose 2} (2^{10}-1)[/tex]

  • MindFlyerMindFlyer Posts: 436
    No, non è nemmeno 1. Su, pensaci un attimo. :D
  • BeagleGBeagleG Posts: 16
    BeagleG wrote: »
    come tutte le funzioni che vanno in un solo elemento... forse ci sono
    [tex][/tex]
    BeagleG wrote: »
    [tex]{10 \choose 2} (2^{10}-10)[/tex] ??.
    il 10 sono tutte le funzioni che vanno in un solo elemento ... quindi è [tex]{10 \choose 2} (2^{10}-1)[/tex]
    [tex]{10 \choose 2} (2^{10}-2)[/tex]
  • MindFlyerMindFlyer Posts: 436
    Giusto, bravo! :)
    Le funzioni a valori in [tex]\{a,b\}[/tex] la cui immagine non è tutto [tex]\{a,b\}[/tex] devono mandare o tutti gli elementi in [tex]a[/tex], o tutti gli elementi in [tex]b[/tex]. E quindi sono esattamente due.

    Adesso si può passare al punto c. Prova a rifare la stessa cosa, cum grano salis...
    E questa volta non accetto risposte secche ma voglio una spiegazione completa. Ricorda che buona parte dell'esame non è indovinare la risposta, ma dare una motivazione comprensibile. Quindi parte dell'esercizio consiste proprio in questo.
  • BeagleGBeagleG Posts: 16
    c) inizialemente posso fissare gli elementi dell'immagine in [tex]{10 \choose 3} [/tex], poi decido quali sono i numeri che posso mandare in [tex]\{a,\}[/tex], [tex]\{b,\}[/tex] o [tex]\{c,\}[/tex], tenendo conto che almeno uno deve andare [tex]\{a,\}[/tex], [tex]\{b,\}[/tex] o [tex]\{c,\}[/tex]. Quindi questo secondo punto è [tex](3^{10}-3)[/tex].

    risultato [tex]{10 \choose 3} (3^{10}-3)[/tex]
  • MindFlyerMindFlyer Posts: 436
    edited March 2015
    Ok bravo, ci siamo quasi, ma manca qualcosa.

    BeagleG wrote: »
    poi decido quali sono i numeri che posso mandare in [tex]\{a,\}[/tex], [tex]\{b,\}[/tex] o [tex]\{c,\}[/tex], tenendo conto che almeno uno deve andare [tex]\{a,\}[/tex], [tex]\{b,\}[/tex] o [tex]\{c,\}[/tex]. Quindi questo secondo punto è [tex](3^{10}-3)[/tex].

    Qui fai un errore. Nota che in questa parte hai dato una risposta secca, probabilmente senza pensarci bene, e per questo motivo hai dimenticato di notare una cosa... Come mai [tex]3^{10}-3[/tex]? Quali sono le funzioni che devi togliere? Sono davvero solo 3? Abituati a motivare bene tutto nei dettagli, anche per prevenire questi errori.
  • BeagleGBeagleG Posts: 16
    edited March 2015
  • MindFlyerMindFlyer Posts: 436
    edited March 2015
    EDIT: ho visto che hai cancellato il commento... Comunque ti lascio il suggerimento che avevo scritto.

    Non so cosa intendi con "quello che ho già contato", non stai dando abbastanza dettagli. Anche se fosse giusto il risultato, in un esame questa spiegazione varrebbe poco. Devi fare lo sforzo di scrivere di più, e soprattutto con più chiarezza e precisione.

    Comunque le funzioni da togliere sono ben più che 27. Ti aiuto a mettere in ordine le idee.

    Le funzioni da [tex]\mathbb N^{10}[/tex] in [tex]\{a,b,c\}[/tex] sono [tex]3^{10}[/tex], giustamente.
    Queste possono essere di tre tipi:
    1) quelle la cui immagine ha esattamente 1 elemento,
    2) quelle la cui immagine ha esattamente 2 elementi,
    3) quelle la cui immagine ha esattamente 3 elementi.

    Tu vuoi contare le funzioni del tipo 3, sottraendo dal totale (ovvero da [tex]3^{10}[/tex]) le funzioni del tipo 1 e del tipo 2.

    Quelle del tipo 1 sono facili da calcolare, e sai bene come farlo.

    Rimangono da calcolare quelle del tipo 2. Ma una cosa simile l'hai fatta nel punto b: devi scegliere i due elementi dell'immagine, contare le funzioni che vanno in almeno uno di quei due elementi, e togliere quelle che vanno in esattamente un elemento.

    (In alternativa puoi "automatizzare" questo passaggio col principio di inclusione-esclusione, ma è bene vederlo anche in quest'altro modo.)
  • BeagleGBeagleG Posts: 16
    edited March 2015
    MindFlyer wrote: »
    EDIT: ho visto che hai cancellato il commento... Comunque ti lascio il suggerimento che avevo scritto.

    Non so cosa intendi con "quello che ho già contato", non stai dando abbastanza dettagli. Anche se fosse giusto il risultato, in un esame questa spiegazione varrebbe poco. Devi fare lo sforzo di scrivere di più, e soprattutto con più chiarezza e precisione.

    Comunque le funzioni da togliere sono ben più che 27. Ti aiuto a mettere in ordine le idee.

    Le funzioni da [tex]\mathbb N^{10}[/tex] in [tex]\{a,b,c\}[/tex] sono [tex]3^{10}[/tex], giustamente.
    Queste possono essere di tre tipi:
    1) quelle la cui immagine ha esattamente 1 elemento,
    2) quelle la cui immagine ha esattamente 2 elementi,
    3) quelle la cui immagine ha esattamente 3 elementi.

    Tu vuoi contare le funzioni del tipo 3, sottraendo dal totale (ovvero da [tex]3^{10}[/tex]) le funzioni del tipo 1 e del tipo 2.

    Quelle del tipo 1 sono facili da calcolare, e sai bene come farlo.

    Rimangono da calcolare quelle del tipo 2. Ma una cosa simile l'hai fatta nel punto b: devi scegliere i due elementi dell'immagine, contare le funzioni che vanno in almeno uno di quei due elementi, e togliere quelle che vanno in esattamente un elemento.

    (In alternativa puoi "automatizzare" questo passaggio col principio di inclusione-esclusione, ma è bene vederlo anche in quest'altro modo.)

    fisso gli elementi dell'immagine in [tex]{10 \choose 3} [/tex], poi decido quali sono i numeri che posso mandare in [tex]\{a,\}[/tex], [tex]\{b,\}[/tex] o [tex]\{c,\}[/tex], tenendo conto che almeno uno deve andare [tex]\{a,\}[/tex], [tex]\{b,\}[/tex] o [tex]\{c,\}[/tex]. In questa seconda fase :

    1) quelle la cui immagine ha esattamente 1 elemento --> so che queste sono 10
    2) quelle la cui immagine ha esattamente 2 elementi, --> so che queste sono [tex]2^{10}-2[/tex]

    per contare le funzioni del tipo 3 devo sottrarre dal totale [tex]3^{10}[/tex] le funzioni del tipo 1 che sono 10 (lo sò dal punto a) e quelle di di tipo 2 che sono [tex]2^{10} - 2[/tex] (lo sò dal punto b)

    scelgo 3 elementi su 10 con il binomiale, poi moltiplico quest'ultimo per tutte le funzioni di tipo 3 meno quelle che hanno esattamente un elemento e due elementi.

    [tex] {10 \choose 3} (3^{10} - (10 + 2^{10} - 2)[/tex]

  • MindFlyerMindFlyer Posts: 436
    edited March 2015
    Meglio, ma c'è ancora qualcosina che non va. :)

    BeagleG wrote: »
    1) quelle la cui immagine ha esattamente 1 elemento --> so che queste sono 10
    2) quelle la cui immagine ha esattamente 2 elementi, --> so che queste sono [tex]2^{10}-2[/tex]

    Ecco, queste le devi motivare... Anche qui, sono convinto che fai errori perché non ti sforzi di motivare le cose ma dai risposte secche. :(

    Ricordati che stiamo considerando le funzioni da [tex]\mathbb N^{10}[/tex] in [tex]\{a,b,c\}[/tex]. Dunque, le funzioni di questo tipo che hanno come immagine un solo elemento sono davvero 10? E per quelle la cui immagine sono due elementi fai un conto giusto (è lo stesso del punto b), ma ne dimentichi un pezzettino...
  • BeagleGBeagleG Posts: 16
    edited March 2015
    direi che sono 10 perché ho un dominio di 10 elementi che vanno in un solo elemento del codominio, questo lo so per il punto a, poi cosa mi sono dimenticato nel secondo punto ? [tex]{10 \choose 2}[/tex]...

    ...



  • MindFlyerMindFlyer Posts: 436
    Nel punto a avevi sia un dominio che un codominio di 10 elementi. Quindi 10 era giusto per forza. Adesso devi ragionare un po' meglio... Ma hai già fatto una cosa simile nel punto b, se ci pensi bene.

    Qui hai un dominio di 10 elementi e un codominio di 3. Ricorda che le funzioni che stai considerando sono sempre a valori in [tex]\{a,b,c\}[/tex]. Non perdere di vista il sottoproblema! Ci siamo già ristretti a questo caso scegliendo i 3 elementi in [tex]{10 \choose 3}[/tex] modi. Quindi le funzioni qui non sono 10, ma...?

    Nel secondo punto hai dimenticato un binomiale, esatto. Ma il binomiale non è precisamente [tex]{10 \choose 2}[/tex], per lo stesso motivo di cui sopra.

    Coraggio, un ultimo ritocco e ci siamo. ;)
  • MindFlyerMindFlyer Posts: 436
    Per evitare che il thread rimanga in sospeso, metto qui le risposte secche ai tre quesiti. Se qualcuno vuole lumi, soprattutto sul terzo punto e come risolverlo col principio di inclusione-esclusione, chieda.

    a) [tex]10^{10}-10[/tex]

    b) [tex]{10 \choose 2}(2^{10}-2)[/tex]

    c) [tex]{10 \choose 3}(3^{10} - 3\cdot 2^{10} + 3)[/tex]
Sign In or Register to comment.