Surjektiva funktioner
Jag har fastnat på d). När det gäller injektion funktioner som i c) så får man antal injektion funktioner genom att ta 5*4*3 = 60. Men hur gör man i d)? Svaret ska bli 150.
Det finns inget lika enkelt sätt att räkna surjektioner.
Man kan skriva det som en generell formel men det blir rätt krångligt.
Men vi kan resonera steg för steg.
Antal funktioner överhuvudtaget mellan de två mängderna 3^5=243
Antal funktioner som endast antar max två värden 3*2^5=96
Antal funktioner som endast antar ett värde 3*1^5=3
Så (inklusion-exklusion) antalet surjektiva funktioner 243-96+3=150.
Man verkar även kunna få det som
Dr. G skrev:Man verkar även kunna få det som
Hur är tankegången där?
Det stämmer ju men jag fattar inte sambandet.
För surjektion så har man antingen
3 av en, 1 av en annan och 1 av en tredje
eller
2 av en, 2 av en annan och 1 av en tredje
3 av 5 kan väljas på C(5,3) sätt, 1 av 5 på C(5,1) sätt. Det femte värdet måste vara det "tredje" värdet, så det kan bara anta ett värde.
2 av 5 kan väljas på C(5,2) sätt, 2 av 5 på C(5,2) sätt. Det femte värdet måste vara det "tredje" värdet, så det kan bara anta ett värde.
Argumentet med det femte värdet känns för närvarande inte helt 100, med det verkar stämma.
Dr. G skrev:För surjektion så har man antingen
3 av en, 1 av en annan och 1 av en tredje
eller
2 av en, 2 av en annan och 1 av en tredje
3 av 5 kan väljas på C(5,3) sätt, 1 av 5 på C(5,1) sätt. Det femte värdet måste vara det "tredje" värdet, så det kan bara anta ett värde.
2 av 5 kan väljas på C(5,2) sätt, 2 av 5 på C(5,2) sätt. Det femte värdet måste vara det "tredje" värdet, så det kan bara anta ett värde.
Argumentet med det femte värdet känns för närvarande inte helt 100, med det verkar stämma.
Fast när vi valt 3 av 5, återstår ju endast 2. Och dessutom kan det värde som antas av 3 väljas på tre sätt. Så den biten blir väl snarare:
(5 över 3)*(2 över 1)*3=60
Alternativet 2,2,1 blir på samma sätt:
(5 över 2)*(3 över 2)*3=90.
Summa 60+90=150.
Ja, såklart Smutsmunnen, tack för det!
Man kan även lösa detta rekursivt.
Om man med f(a,b) betecknar antalet surjektiva funktioner från en mängd med a element till en mängd med b element så gäller rekursionssambandet:
f(a,b)=b*(f(a-1,b-1)+f(a-1,b))
Tillsammans med f(a,a)=a! och f(a,1)=1 kan man sedan rekursivt beräkna f(a,b) för alla a,b, även om det kan bli väldigt beräkningstungt för stora värden.
Hur bevisar man rekursionen?
Ta ett bestämt värde i definitionsmängden säg 1. 1 kan avbildas på b olika element i målmängden. Nu finns två möjligheter. Antingen är 1 det enda element som avbildas på detta element. Då ska övriga a-1 element avbildas surjektivt på övriga b-1 element. Eller så är det fler element i definitionsmängden som avbildas på samma element i målmängden. Då ska övriga a-1 element avbildas surjektivt på b element.
