Snabb kombinatorisk fråga
Blir inte frågan "Hur många tal kan man bilda av siffrorna 1, 2, ..... 9 om varje siffra bara får användas en gång och siffrorna skall komma i storleksordning? Exempel på tillåtna tal är 235, 7, 5689." ekvivalent med: Hur många delmängder finns det med 9 tal där nollmängden inte räknas?
henrikus skrev:2^9-1
Exakt, men fungerar tänket?
Ja. Det finns endast ett sätt att välja m olika tal bland n olika tal där talen är sorterade. Så antalet blir B(9,1) + B(9,2) + ... + B(9,9) =2^9-1 (B är binomialkoefficient.)
Jag antar att tänket är:
Alla siffror ställs upp på en rad i storleksordning:
123456789
För att bilda ett av våra efterfrågade tal så skall vi ta ovanstående slinga och stryka några av siffrorna, t.ex.
123456789, ger 235
123456789, ger 7
123456789, ger 5689
Är vi nyfikna på hur många sätt vi kan göra detta på så har vi egentligen nio stycken binära val:
Skall ettan strykas?
Skall tvåan strykas?
Skall trean strykas?
t.o.m.
Skall nian strykas?
Eftersom varje fråga kan besvaras med antingen "ja" eller "nej" så ger detta upphov till 9 stycken val med två möjliga alternativ. Detta ger då totalt 2*2*2*2*2*2*2*2*2= 29 möjliga tal. Men eftersom att vi inte kan bilda ett tal genom att stryka alla siffror så försvinner en kombination och vi får lösningen 29-1.
Edit: Och det är först nu som jag inser att frågan var om denna fråga kan betraktas som ekvivalent med hur många delmängder man kan bilda. Jag skulle säga "Ja". För att bilda en delmängd går man igenom alla siffrorna en efter en och besvarar frågan "Skall denna siffra ingå i delmängden?". 9 binära val. Sedan frågar man sig hur många delmängder det ger upphov till. 29. Sedan stryker man delmängden som är tomma mängden och får 29-1.
