Technique
Few items, many rules: list by the first place and drop a branch as soon as it breaks a rule
Quantitative Aptitude • Permutations and Combinations
Statement
To count arrangements of a few items under several rules, choose the first place from the items allowed there, then each next place from the items left that break no rule with what is already placed. A branch that breaks a rule is stopped at once. The count is the number of complete branches.
How to use it
- 1Write every rule as a forbidden pair or a forbidden place, both ways round if the rule says 'each other'.
- 2Start with the first place and use only the items allowed there.
- 3At each place, try the items left in order and skip any that break a rule with the item just before it.
- 4Check the place rules again at the last place, then count the complete rows.
Worked example
Arrange A, B, C in a row so that A and B are not next to each other. How many ways?
Step-by-step
- 1Forbidden neighbours: AB and BA.
Why: 'Next to each other' works both ways.
- 2Start A: AB stopped; AC then B gives ACB, fine.
Why: A must not be followed by B; C then B is allowed.
- 3Start B: BC then A gives BCA. Start C: CAB and CBA both have A beside B, stopped.
- 4Complete rows: ACB, BCA.
Answer
2 ways.
Watch out
A rule worded 'X and Y do not follow each other' forbids both XY and YX; reading it one way only gives too many. Stopping a branch early is safe only when the rule is already broken.
Also known as
tree diagram, listing arrangements, systematic listing, arrangements with restrictions