How Many Possible Questions in DILR: Enumerate with a Tree

DILR

How many arrangements are possible? How many groups satisfy the rules? These questions feel risky, because you are not finding one answer but counting all of them, and missing a case gives the wrong number. Many students guess a formula and hope.

There is a safer way: enumerate with a tree. You pick a variable, branch on its values, prune any branch that breaks a rule, and count the leaves. This guide shows the method with three small examples whose counts you can confirm, and lists the habits that keep a count honest.

Why Counting Is Harder Than Finding

Finding one valid arrangement needs a single path through the rules. Counting all of them needs every path, and a missed branch changes the answer by a whole number. There is no partial credit for almost right.

That is why how many questions feel risky. Students often reach for permutations and combinations, which are the right tools when the cases are regular. In DILR, the rules are usually irregular. Two people cannot sit together, one item forces another, a position is reserved. Formulas rarely fit these cleanly.

A tree gives you a systematic way to cover every case once. It is a slower approach in principle, but with pruning it is often fast, and it comes with a built in check: you can see each case.

The Tree Method

The idea is to make decisions in order. First decide one thing, then the next, and at each step only keep options that can still lead to a valid case. By the end, each path from the root to a leaf is one valid case.

Choosing the order matters. Starting with the most constrained variable, the one with the fewest options or the most rules attached, cuts the tree early. Starting with a free variable gives you a wide tree that you prune later, which is the same work with more writing.

Example One: Choosing a Group

A committee of 3 is chosen from five people, P, Q, R, S and T. P and Q cannot both be on it. If R is on it, S must be on it. How many committees are possible?

Branch on P, the person involved in one rule. If P is in, Q is out, and two more are chosen from R, S and T. The pairs are RS, RT and ST. RT fails, because R is in without S. So P gives two committees: PRS and PST.

If P is out, branch on Q. If Q is in, choose two from R, S and T, with the same check. RS and ST work, so Q gives QRS and QST. If Q is out, all three must come from R, S and T, so the committee is RST, which satisfies the R and S rule.

The total is 2 plus 2 plus 1, which is 5 committees. You can check by trying a few non-members of the list: PQR fails the P and Q rule, and PRT fails the R and S rule. The tree covered every case and the count is secure.

Branch	Remaining choice	Valid committees
P in, Q out	Two from R, S, T	PRS, PST
P out, Q in	Two from R, S, T	QRS, QST
P out, Q out	All three from R, S, T	RST

Example Two: A Row With a Forbidden Pair

Four people, A, B, C and D, stand in a row. A and B must not stand next to each other. How many orders are possible? Here a formula works, and it is useful to compare it with the tree.

By the formula route, there are 24 orders in all. Count the orders where A and B are adjacent by treating AB as one block, giving 3 items, which can be arranged in 6 ways, and the block can be in two internal orders. That is 12 orders with A and B adjacent. So 24 minus 12 is 12 valid orders.

Now by tree. Place A first in position 1, 2, 3 or 4, and for each, count positions for B that are not adjacent. If A is in position 1, B can be in 3 or 4, which is 2 choices. If A is in position 2, B can only be in 4, which is 1 choice. If A is in position 3, B can only be in 1, which is 1 choice. If A is in position 4, B can be in 1 or 2, which is 2 choices. That is 2 plus 1 plus 1 plus 2, or 6 placements of A and B. The other two people fill the remaining spots in 2 ways, so 6 times 2 is 12. Both methods agree.

The tree is slower here, but it is also safe in cases where the formula does not apply. When the rules are irregular, the tree works and the formula does not. Our guide on permutation and combination shortcuts covers the cases where formulas are the quicker route.

Example Three: An Ordering Rule

Three talks, X, Y and Z, are scheduled in three slots. X must come before Y. How many schedules are possible? There are 6 orders of three items. The rule keeps exactly half, because in every order X is either before or after Y, and the two are equally common. So the count is 3.

Check with the tree. Place X first. Then Y and Z can follow in 2 ways: XYZ and XZY, both valid. Place Z first, and X must precede Y: ZXY is valid. Place Y first, which breaks the rule at once, so the branch is pruned. The valid schedules are XYZ, XZY and ZXY, which is 3.

The shortcut that half of all orders satisfy a before rule is useful whenever one pair is ordered and the rest are free. With more rules, the shortcut stops working, and you return to the tree. It helps to know both, and to check one against the other when time allows.

Keeping the Tree Small

The method can fail on time if the tree grows too wide. Three habits keep it small. First, branch on the most constrained variable. Second, prune early, at the first failed rule. Third, merge branches that behave the same, so you count them once with a multiplier.

For example, if two people are interchangeable under the rules, count the case for one of them and multiply by two. If the rest of the arrangement is free once a few key items are placed, count the free part with a simple factorial, and multiply. This hybrid of tree for structure and formula for the free part is often the fastest.

Write the tree in a compact form: a line per branch with a short label and a count. Avoid drawing large diagrams. The aim is a record you can check, not a picture.

One more habit: label each branch with the rule that cut it, in two or three letters. When a later question changes a rule, such as removing the restriction on P and Q, you can see at a glance which pruned branches come back, and you can adjust the count without starting over.

Checking Your Count

A count is easy to get wrong silently, so build in a check. One check is to count a different way, as we did in example two. Another is to list the cases explicitly if the number is small, then confirm each against the rules.

A third check is the complement. Count the invalid cases and subtract from the total, if the total is easy. In example two, the 24 total minus 12 adjacent gave the answer. If the tree and the complement disagree, one has a missing or extra case.

In an exam, you may only have time for a quick check. Choose a spot check: take one leaf and test every rule, then take one case you excluded and confirm it fails. Two minutes of checking is cheap compared with a lost mark.

A Practice Routine

Start with small counts, with four or five items and two or three rules, and do each by tree. Then redo each with a formula when one applies, and compare. This builds trust in both methods.

Next, add sets with several questions, where one question asks how many and others ask for specific cases. The tree from the first question often answers the rest, since it lists the cases. Our guide on what if questions without rebuilding the set shows the same idea of reusing structure.

A CAT study planner can schedule short counting sessions, and you can talk to a CAT mentor if you want feedback on your trees. For arrangement type sets, see the diagram lock method for seating arrangements.