Kombinatorisk tenkning

[svinepels]

Hvordan tenker dere når dere løser kombinatoriske oppgaver som for eksempel følgende:

Finn antall binære strenger med lengde 10 som inneholder nøyaktig 4 1-tall.

Har inntrykk av at jeg tenker for tungvint på slike oppgaver, hadde vært nyttig med litt innsikt i andres tenkemåter.

[Gustav]

Standardmåten er vel å finne antall muligheter for å plukke ut 4 av 10 ved bruk av binomialkoeffisienten [tex]10\choose 4[/tex].

[Karl_Erik]

Jeg vet ikke helt hvor grunnleggende tenking du er interessert i - om jeg løser et slikt problem i praksis ville jeg tenkt at en slik streng står i 1-1-korrespondanse med antallet måter å velge ut fire av ti plasser det skal stå 1 på, og så ville jeg bare sagt at svaret var tallet 4C10 fordi jeg er så vant med dette siste problemet.

Om en lurer på hvordan en -egentlig- skal tenke for å løse det antar jeg du først tenker at om du hadde tatt hensyn til rekkefølgen ting ble valgt i hadde svaret vært 10*9*8*7, da den første velges blant 10, den andre blant 9 og så videre. Deretter ville jeg sagt at om du lister opp måtene du kan velge ut fire ting av ti når du tar hensyn til rekkefølge, og så for hver av disse mulighetene ser bortifra rekkefølgen, forekommer ethvert uordnet utvalg {A,B,C,D} 4!=24 ganger - {A,B,C,D} forekommer som ABCD, ABDC, ACBD, ACDB, ADBC, ADCB og så videre. Dette betyr, med standardnotasjonen, at svaret blir 10*9*8*7/24. Fører man et litt mer generelt argument får en formelen for binomialkoeffisisenter.

[Nebuchadnezzar]

Er det lov at en streng har null som første plassering?
Vil ikke 01000001 være akkuratt det samme som 1000001 ?

Selv tenker jeg at vi må bruke et totall på første plassering. Dermed får vi

[tex] {9} \choose{3} [/tex]

[Karl_Erik]

Er det lov at en streng har null som første plassering?
Vil ikke 01000001 være akkuratt det samme som 1000001 ?

Selv tenker jeg at vi må bruke et totall på første plassering. Dermed får vi

[tex] {9} \choose{3} [/tex]

Som binære tall er disse like. Som strenger er de forskjellige.