Indelningsregel (kombinatorik)
Inom kombinatorik är divisionsregeln en räkneprincip . Den anger att det finns n / d sätt att utföra en uppgift om det kan göras med hjälp av en procedur som kan utföras på n sätt, och för varje sätt w , exakt d av n sätten motsvarar sättet w . I ett nötskal är divisionsregeln ett vanligt sätt att ignorera "oviktiga" skillnader när man räknar saker.
Tillämpas på set
I termer av en mängd: "Om den ändliga mängden A är föreningen av n parvis disjunkta delmängder var och en med d element, då är n = | A |/ d ."
Som en funktion
Divisionsregeln formulerad i termer av funktioner: "Om f är en funktion från A till B där A och B är ändliga mängder, och att det för varje värde y ∈ B finns exakt d värden x ∈ A så att f ( x ) = y (i vilket fall säger vi att f är d -till-ett), då | B | = | A |/ d ."
Exempel
Exempel 1
– Hur många olika sätt finns det att sitta fyra personer runt ett cirkulärt bord, där två sittplatser anses vara lika när varje person har samma vänstra granne och samma högra granne?
- För att lösa den här övningen måste vi först välja en slumpmässig plats och tilldela den till person 1, resten av platserna kommer att märkas i numerisk ordning, medurs rotation runt bordet. Det finns 4 platser att välja mellan när vi väljer den första plats, 3 för den andra, 2 för den tredje och bara 1 alternativ kvar för den sista. Det är alltså 4! = 24 möjliga sätt att placera dem på. Men eftersom vi bara överväger ett annat arrangemang när de inte har samma grannar till vänster och höger, spelar bara 1 av 4 sittplatser roll.
- Eftersom det finns 4 sätt att välja för plats 1, enligt divisionsregeln ( n / d ) finns det 24/4 = 6 olika sittplatser för 4 personer runt bordet.
Exempel 2
– Vi har 6 färgade tegelstenar totalt, 4 av dem är röda och 2 är vita, på hur många sätt kan vi ordna dem?
- Om alla tegelstenar hade olika färger skulle det totala antalet sätt att arrangera dem vara 6! = 720 , men eftersom de inte har olika färger skulle vi beräkna det så här:
- 4 röda tegelstenar har 4! = 24 arrangemang
- 2 vita tegelstenar har 2! = 2 arrangemang
- Totalt arrangemang av 4 röda och 2 vita tegelstenar = 6! / 4!2! = 15 .
Se även
Anteckningar
- Rosen, Kenneth H (2012). Diskret matematik och dess tillämpningar . McGraw-Hill Education. ISBN 978-0077418939 .
Vidare läsning
- Leman, Eric; Leighton, F Thompson; Meyer, Albert R; Matematik för datavetenskap, 2018. https://courses.csail.mit.edu/6.042/spring18/mcs.pdf