Treningsforum

Jeg har midtsemesterprøve i diskret matematikk i morgen, og tror muligens vi får bruk for en formel som ikke står i boka, og som jeg ikke finner. Formelen jeg er ute etter er for antall injektive (en-entydige) funksjoner fra en mengde M til en mengde N. Etter litt prøving, tipper jeg at den skal være n! (les n fakultet).

På forhånd takk hvis noen vet! :)

Går utifra at dette ikke er det samme n! som står i sannsynlighet for 2MX og 3MX?

Nå er ikke jeg mye på nett i dag, men dette er jo avhengig av av antallpunkter i N da. Og jeg antar, ut i fra hva du skriver, at det er n punkter der - og at mengden er endelig ? I så tilfelle, så vil antallet være m*n  vel ??

Logikken min er som følgende : dersom du har m punkter i M, og n punkter i N, så vil du fra hvert punkt i M ha n forskjellige injektive funksjoner. Siden mengden har m punkter vil det være m*n funksjoner alt i alt.

Men det dersom du snakker om en felles mengde funksjoner, så vil det heller være min{m, n} som gjelder, siden hvert punkt kun kan være forbunnet med 1 punkt, og det skal gå begge veier - det er i grunn denne løsningen jeg tror du er ute etter.

Nå har jeg antatt et par ting her du ikke har nevnt, men du får rette på meg hvis det er feil. Mistenker at du tenker på surjektive funksjoner.....

Nå har jeg ikke dette helt i fingrene lenger heller, lenge siden jeg holdt på med slik matematikk.... :-\

nå tuller du. N er en bokstav, ikke et tall og skal holde seg laaaangt unna matematikk;P

Hvilken linje går du på Caepp? Skal selv ha diskret matematikk i morgen :)

n er antall elementer i N ja, og m er antall elementer i M. Jeg tenker på injektive, ikke surjektive funksjoner, og har tegna opp alle n^m funksjoner (totalt antall) for verdien 3 for n og henholdsvis 2 og 3 for m. Totalt antall funksjoner fra mengden på to til mengden på tre, er 3^2=9. Tilsvarende er totalt antall funksjoner fra tre til tre 3^3=27. Antall injektive funksjoner for begge disse to tilfellene er 6, noe som såvidt jeg kan skjønne impliserer noe i retning av at antallet injektive er gitt ved n! (?), som i disse tilfellene er 3x2x1=6. Likevel blir det vel ikke helt riktig, i og med at vi ikke tar hensyn til m. Er m=1 f.eks, så vil jo ikke denne formelen holde...

 ::huh2::


Jeg går årsstudium i matte og statistikk på NTNU. Hva med deg?

Edit: Har testa for noen flere verdier, og er mer og mer sikker på at formelen må være n!/(n-m)! Tror jeg satser på det om jeg får bruk for det imorgen, selv om jeg ikke er 100% sikker :)

Formelen din holder heller ikke ved m > n = 1.

Lett.

Jeg var suveren i 'Abstrakt algebra' i vår, men glemt det meste.

'Entydig' angir at det er kun èn n for hver m som puttes inn i funksjonen, ikke sant? Men kan ulike verdier fra m gi samme n? Eller blander jeg surjektive og injektive funksjoner her?


Ok, nå fant jeg definisjonen på injektiv: Funksjonen er injektiv hvis det for ethvert element y E B, finnes høyst ett element x E A slik at f(x) = y.

Isåfall er formelen din riktig. Grunnen er at du kun kan "fakultere" like mange ledd som du har verdier i m.
La oss si at du har 4 verdier i m (A,B,C,D) og 7 i n (1,2,3,4,5,6,7). A har da syv ulike verdier å "velge" mellom. B har kun seks, siden A har "tatt" en av dem. Videre har C fem å velge mellom og D har fire.

Antall funksjoner blir da 7*6*5*4, med andre ord n!/[(n-m)!]

Hvordan gikk det?

Dette betinger i så fall at n > m.

Ja, men det er vel et kriterium for at man i det hele tatt skal kunne ha en injektiv funksjon.

At mengden M er "større" enn N ?

Dersom N er en delmengde av M, men ikke hele M, så vil funksjonen f(x) = x være injektiv den, alikvel er m>n.

Mistenker du blander med bijektive funksjoner nå....

Nei, M er en delmengde av N.

F(m) = n, men n må være ulik for hver m (siden den er injektiv), derfor må |N| > |M|

Var det ikke det jeg sa da... ?? ::huh2::

Muligens :)

Oppsummert. For at f(m) skal kunne være en injektiv funksjon, må ordenen til N være større enn ordenen til M; |N| > |M|

Derfor vil formelen alltid holde, unntat når |M| = |N|, da får vi 0! i nevner, og det regner jeg med blir 0 (eller er det kanskje ikke definert?).

0! er definert som 1.

Uansett så må det være slik at dette gjelder for N større enn ELLER LIK M.

M = N = {1} har jo minst en injektiv funksjon....


Kanskje viktig å pressisere her at vi snakker om lineær algebra også, for de som måtte være intressert....

Ok, hvis 0! er definert som 1, er formelen alltid gyldig. Hvis M=N={1}, finnes det kun èn injektiv formel (og denne vil også være surjektiv), nemlig f: M --> N, f(1)=1

Nettopp. Da er vi jo enige da. :)

Bortsatt fra at jeg liker å notere det som f(x) = x, men så er jeg ingen algebraiker eller da....

Med algebraisk betegnelse ville {1} blitt skrevet som {e}, identiteten i gruppeteori. :)

Jepp. Men dette er det snart 10 år siden jeg hadde noen om. Jeg har studert (på hovedfagsnivå) funksjonalanalyse - spesielt C*-algebraer og stokastisk analyse samt finansiell matematikk. Og da sier det seg selv at denne teorien her sitter ikke akkurat i fingrene lenger. :)

Allmenkunnskap.

Som f.eks. å kunne skrive det ordet riktig ? ::)

Bruker du mye av teorien i jobben din?

Funksjonalanalysen er det jo ingen ting, det er mer den analytiske legningen man er ute etter i en jobb som denne. Stokastisk analyse derimot brukes veldig ofte, og på et veldig høyt nivå også. Vi ligger ofte og følger med helt i forskningsfronten på noen av delområdene der. Finansiell matematikk blir jo i praksis bare en del av dette, men sitter sånn delvis i fingrene.

Men dette er avhengig av individuelle jobbspesifikasjoner naturligvis.

Studerer kommunikasjonsteknologi (siv.ing.).

Hva i heiteste er dere snakker om ?  ::huh2:: dette skjønte ihvertfall ikke jeg et kvekk av .......men jeg trenger jo ikke å skjønne meg på alt heller da  ::biggrin::

Snakker bare om dagligdagse ting egentlig, som 3 dimensjonale diskrete magnetiske Laplace-operatorer. Spesielt de er morsomme, men jeg er i grunn litt lei av de nå må jeg innrømme. Noen år på samme tema gjør noe med en, dessuten blir en litt skrullete av det... ::huh2::

Takk til UAC og LurePer for innspill! ::smile::

Fikk faktisk noe liknende på prøven, en påstand om at antall injektive funksjoner fra M til N (når n er større enn eller lik m) alltid er større enn eller lik m!. Denne satt jeg ei stund å funderte på, men kom etterhvert frem til at siden vi ikke har noen funksjoner fra en tom mengde til en ikketom mengde, så kan ikke antallet være lik M! som her er 0!=1. Etter prøven ser jeg typisk nok over prøven en ekstra gang, og oppdager at det i oppgaveteksten er presisert at M er ikketom... ::furious::

Ellers så klarte jeg å klebbe fryktelig med et induksjonsbevis der jeg skulle bevise at summen av 1/i fra 1 til (2^n)-1 er mindre enn eller lik n, for alle positive heltall. Litt lite tid igjen og veldig stressa når jeg begynte, så det gikk selvsagt ikke helt bra...Typisk nok så tenker jeg meg frem til riktig svar på vei ut av auditoriet...

Resten tror jeg gikk relativt bra, så da gjenstår det bare å se hvor store negative utslag disse to tabbene gir, har ikke fått karakter/fasit ennå.