matematikk.net

Hei, jeg skulle bevise at:

[tex] \sum_{k=1}^{n}k^3 \cdot {n \choose k} = 2^{n-3}n^2(n+3)[/tex]

Jeg tenkte at dette ville være grei skuring. Jeg ser på venstresiden at de tar ut en gruppe k, og finner 3 ledere som kan overlappe hverandre.

Høyresiden er uforståelig for meg. Du tar først å velger en leder til alle stillingene. Dette gir naturligvis [tex]n \cdot 2^{n-1}[/tex], der [tex]2^{n-1}[/tex] spør resten av gruppen om de vil være i denne gruppen. Når to skal besitte de tre stillingene går det litt i surr for meg. Jeg er nå klar over [tex]{3 \choose 2}[/tex], men det går ikke helt logisk opp for meg. Person (n) kan besitte 1 eller 2 stillinger, og da finnes det bare de to ulike metodene.

Man kan også se på de tre ulike stillingene som 3 forskjellige, men da blir det jo flere enn 3?

Har du prøvd med induksjon?

Vel, jeg prøvde induksjon i 20 minutt uten få det helt til, men det er ikke vitsen siden dette skal omhandle det å telle på to ulike måter. Jeg vet at antall måter å velge 1 skribent, en nestleder og en leder der alle er samme person er [tex]n2^{n-1}[/tex], og antall måter å velge det samme med tre personer er [tex]n(n-1)(n-2)2^{n-3}[/tex] Jeg får altså:

[tex]Antall måter = n2^{n-1} + xxxxx + n(n-1)(n-2)2^{n-3}[/tex]
Jeg forstår ikke logikken bak det å finne en skribent, nestleder og leder der det bare er 2 som har begge stillingene blant n personer.

Ok. jeg tror jeg begynner å forstå hvor du vil. Dersom jeg har forstått det rett skal vi altså finne ut på hvor mange måter man kan plukke ut en gruppe og samtidig utnevne tre ulike stillinger til personene i denne gruppa. I tillegg må altså gruppa bestå av minst 1 person, og det er slik at 1 person kan inneha flere stillinger.

deler opp i tre tilfeller, som du nevner:

1) De tre stillingene tildeles tre ulike personer: Det gir [tex]n(n-1)(n-2)2^{n-3}[/tex] muligheter for valg av styrer.

2) To stillinger gis samme person. Den siste gis en annen. Det gir [tex]3n(n-1)2^{n-2}[/tex] muligheter

3) Tre stillinger gis samme person. Det gir [tex]n2^{n-1}[/tex] muligheter.

EDIT: På punkt 2) må man gange med faktoren 3 som er antallet måter å plukke ut 2 av de 3 stillingene til den første personen som trekkes ut.

Men fasiten sier at det er på 2) [tex]3n(n-1)2^{n-2}[/tex] og ikke [tex]n(n-1)2^{n-2}[/tex].

Jeg ville i beste fall sagt at de to som blir valgt kan bytte på å ha 2 jobber. Jeg forstår ikke helt hvordan 3'er-faktoren kommer fra.

Hoksalon wrote:Men fasiten sier at det er på 2) [tex]3n(n-1)2^{n-2}[/tex] og ikke [tex]n(n-1)2^{n-2}[/tex].

Jeg ville i beste fall sagt at de to som blir valgt kan bytte på å ha 2 jobber. Jeg forstår ikke helt hvordan 3'er-faktoren kommer fra.

Tankengangen blir vel at du først velger ut en person som skal ha to stilinger. Det er da n muligheter. Deretter velger du ut en annen, som totalt gir n(n-1) muligheter. For hver av disse er det 3 måter å plukke ut 2 av de 3 stillingene som du gir til den første personen.

Takk, endelig satt det