Kombinatorik

Tanke: Vad skulle komplementet vara till "Ingen siffra i talet får ha en likadan siffra intill".

Vad menar du när du säger ”komplementet”?

Om vi i den hela mängden har en delmängd är delmängdens komplement den del av hela mängden som ligger helt utanför delmängden. Om hela mängden är alla människor, delmängden är alla kvinnor så är komplementmängden alla män och alla människor vars könsidentitet på annat vis ej är att betrakta som kvinnor.

Om hela mängden är de sifferkombinationer man kan bilda med 1, 1, 2, 2, 3 och 3 och delmängden är de sifferkombinationer man kan bilda så att inga identiska siffror är intill varandra så är dess komplement de övriga sifferkombinationerna. Man kan beskriva dessa med ord i en mening.

Hur skriver man komplementet?

Är komplementet:

”Komplementet består av de sifferkombinationer där två likadana siffror står jämte varandra.”

Läste på lite, handlar det om restriktioner?  Fattar dock inte exakt hur det fungerar :(

Om delmängden är de kombinationer där inga identiska siffror är intill varandra är dess komplement de kombinationer där det finns identiska siffror intill varandra.

Så mitt komplement stämde?

Hur fortsätter vi härifrån, om vi har ett komplement?

I ärlighetens namn så tror jag inte det är det lämpligaste sättet att jobba på. Det man kan göra är att tänka sig att man skriver varje siffra på en lapp och kastar om de för att få 6 objekt att sätta i permutation och sedan då vi är nyfikna på hur många kombinationer som har dubbelsiffror i sig ta fram en häftapparat och häfta samman lapparna med samma siffror och undersöka hur många sätta man kan placera dessa 5 objekt på, men då får man dessutom fallen att två dubbelsiffror eller tre dubbelsiffror förekommer. Detta kan man hantera på ett elegant vis som jag kan skriva ut men detta är inte något man lär sig i högstadiet.

Ett annat sätt att jobba på (och då det gäller kombinatorik finns det oftast många sätt att komma fram till resultatet på) är att gå igenom varje position i den tilltänkta talet i tur och ordning och i varje position besvara frågan hur många alternativ man har i valet av siffra. Nackdelen här är att antalet alternativ är beroende på vilka siffror man redan har förbrukat vilket gör att man får "om man gjort det valet har man nu si och så många alternativ, annars så och si många alternativ", men det visar sig att vi egentligen bara får två fall att hantera beroende på om vi väljer upprepning av siffran från första positionen i tredje positionen eller inte.

Bedinsis skrev:

Detta kan man hantera på ett elegant vis som jag kan skriva ut men detta är inte något man lär sig i högstadiet.

 

Kan du skriva ut det så jag lär mig det?

Medans du väntar på att Bedinsis ska ge dig den eleganta lösningen rekommenderar jag dig att gå på det andra stycket i #8. 

Skaffa dig en överblick av problemet genom ett testa följande.

De två första siffrorna i ditt 6-siffriga tal kan vara

12
13
21
23
31
32

om vi då väljer att undersöka hur det kan se ut för ett av dessa fall, 

i Fallet 12 som beynnelsesiffror. Vi fyller på 2 siffror till och får då dessa begynnelsefyrtal (det måste ingå en 3a annars kommer vi inte att kunna fylla i positionerna 5 och 6

1213
1231
1232

Kolla sen vilka de 2 sista siffrorna kan vara för var och en av dessa 3 kombinationer.

Hur många kombinationer får du totalt i detta fall? 

kan du sen dra någon slutsats hur många kombinationer det finns totalt? 

Cristian0311 skrev:

Bedinsis skrev:

Detta kan man hantera på ett elegant vis som jag kan skriva ut men detta är inte något man lär sig i högstadiet.

 

Kan du skriva ut det så jag lär mig det?

För all del.

Vi börjar med den hela mängden av alla kombinationer, där vi struntat i huruvida några av siffrorna förekommer direkt efter varandra (hädanefter kallat dubbelsiffror). Denna blir som du redan sagt 6!/(2!*2!*2!)=720/8=90.

Från detta vill vi subtrahera alla de lösningar där det förekommer en upplaga av två likadana siffror efter varandra. För att hitta hur många detta är så häftar vi samman två identiska lappar med varandra och får fem objekt att ställa i ordning, och tar reda på hur många permutationer vi kan få med det. Detta blir 5!/(2!*2!)= 30. Eftersom att vi kan göra detta med tre olika siffror så får vi multiplicera detta med 3, så vi skall subtrahera med 90.

Redan här kanske du blir en smula förvirrad, eftersom så här lång har vi kommit fram till att det finns 0 permutationer. Grejen är dock den att mängderna vi subtraherat med har ett visst överlapp, i mängden där vi tvingat ettorna att vara intill varandra förekommer kombinationen

[11][2][3][3][2]

i mängden vi tvingat treorna att vara intill varandra förekommer kombinationen

[1][1][2][33][2]

som ju är identiska. Så vi har subtraherat alla de kombinationer där två dubbelsiffror förekommer två gånger. För att råda bot på det får vi lägga till en upplaga av var och en av dessa kombinationerna. Så frågan är då på hur många sätt man kan bilda kombinationer där det förekommer två dubbelsiffror. För att undersöka det skriver vi varje siffra på varsin lapp och häftar samman fyra av lapparna till två stycken dubbelsifferslappar, och får därmed 4 objekt att sätta i permutation. Dessa kan man sätta på 4!/2!= 12 permutationer, och man kan välja ut vilka två siffror som skall bilda dubbelsiffror på tre vis ([11] & [22], [22] & [33] respektive [11] & [33]) så det blir 3*12 = 36.

Precis som tidigare har vi dock räknat lite för mycket. I mängden med [11] & [22] finns kombinationen

[11][22][3][3]

i mängden med [33] & [22] finns kombinationen

[1][1][22][33]

så då vi adderade dessa blev vissa kombinationer räknade flera gånger. För att råda bot på detta får vi subtrahera alla de mängder där alla dubbelsiffror förekommer, vilket det finns 3! permutationer av, och då vi skall välja ut tre siffror av tre att betrakta som dubbelsiffror får vi multiplicera med 1, så vi får 1*3!= 6 så vi skall subtrahera med 6 så i slutändan får vi 36-6= 30.

Så den totala lösningen ges av

[alla kombinationer] - [alla kombinationer där en dubbelsiffra förekommer] + [alla kombinationer där två dubbelsiffror förekommer] - [alla kombinationer där tre dubbelsiffror förekommer].

Detta lärde jag mig på universitetet, och vad vi egentligen gör är att klippa och klistra med innehållet i ett Venn-diagram. Om det kändes begripligt så har du lärt dig ett sätt att lösa sådana här uppgifter, om inte så kanske det finns en anledning att de lär ut det på universitetsnivå.

Jösses, tusen tack! Uppskattar verkligen ditt svar, ska läsa på lite mer. Förvänta dig fler frågor… 😅