# Simple permutation/combination question

In how many ways I can arrange six books on different subjects in a row such that the Math book is always to the left of history book (not necessarily adjacent) ?

-
Consider symmetry... – anon Jun 27 '12 at 3:27
Do you have any thoughts on the problem yourself? Have you tried anything? Got stuck somewhere? – Gerry Myerson Jun 27 '12 at 3:27
Yes I tried. But I think I probably lack the basics to get around this problem. – user2434 Jun 27 '12 at 3:32

The total number of arrangements, with no restrictions, is just $6!$, since you are ordering six books.

Let us say an arrangement is "good" if the math book is to the left of the history book, and "bad" if the math book is to the right of the history book.

I claim that every good arrangement can be paired off with a bad arrangement in a way that covers all arrangements. How? If you have a bad arrangement, and you reverse it, what happens?

So, if you can divide the $6!$ arrangements into exactly two halves, with one half consisting of the good arrangements and one half consisting of the bad arrangements, then how many good arrangements are there?

-

Arturo's method is very elegant and you should study it to understand precisely why it's true.

If you find yourself initially lost in problems like this it's worth considering what would be necessary to construct each valid case. You must be sure to count each valid case once, and only once. Separating the set of all possibilities into mutually exclusive subsets whose union is the set is called a partition, and is a very useful concept.

There are 6 possible book places. Each valid case must have a math book in one of these places. The set of all arrangements can be partitioned into subsets where the math book is in one particular place (1-6). Let the math book be in place n. Then the history book must precede it and be located in one of $(n-1)$ locations. The remaining 4 books can be placed in any order; there are $4!$ ways to do so. The total arrangements for one subset of cases would then be $4!\cdot(n-1)$. To count all cases, sum each possible value of $n$. Can you demonstrate this to be an identity with the value given by Arturo's method?

Notice that the problem was decomposed into several subproblems that were generally the same. Then by understanding how to solve one of these subproblems one understands how to solve all of them and hence the original problem. Notice the relationship between problem decomposition and synthesis and the partitioning of the set.

You might also realize that there was nothing special about the math book in this strategy. That's not quite true as all math books are special, but what I mean is that you could have enumerated each valid case by first placing the history book and then the math book. The difference would be that if the history book was in place $n$ then there would be $(6-n)$ places for the math book. Can you demonstrate this value to be identical to the previous?

Finally, this symmetry may lead you to realize something interesting. What would happen if you accidentally confused the history and math book upon placing them? Every single case you thought would be right, would actually be wrong! Since every single case must be valid or invalid (there are no maybes), and every single case's validity can be switched by switching book placements, there must be a direct correspondence between valid and invalid cases. Consider the meaning of this. If you looked at your books through a mirror, you may also realize that each arrangement reverses into an arrangement of opposite validity. Pairing reversals to facilitate counting is what Arturo mentioned.

Identifying symmetry or similarity, and decomposing a problem into multiple more tractable subproblems, are two useful problem solving strategies. They are often particularly useful for combinatorial problems.

-

There's more than one way to do it. You could choose the position of the history book (leaving room for the math book), then the position of the math book, and the positions of the rest of the books. For each choice note how many possibilities there were.

Determine the number of ways to make alternative choices by adding. I can select one of my fingers by choosing one of the five on my left hand OR one of the five on my right hand, for a total of ten options.

Determine the number of options derived from two independent choices by multiplying the number of options available at each of the two choices. If I choose one of the five fingers on my right hand AND one of the five fingers on my left hand, I have fully 5*5 = 25 options.

-

The use of symmetry in the solutions above are more interesting. A crude solution (similar to minopret's outline) would use the pigeon hole principle. Labelling the positions $1$-$6$, and counting the possible positions gives the same solution. So, if the history book is the first position, there are $5!$ possible book combinations for the remaining $5$ slots. If the history book is in the second position, then there are only four positions available for the math book, and once it's position has been established only $4!$ possible combinations for the remaining books. If the history book is in the third position, then there are only $3$ positions available for the math book, and once it's position has been established only $4!$ possible combinations for the remaining books. Carrying on, the total number of ways the books can be arranged is $$5! + 4\cdot 4! + 3\cdot4! + 2\cdot4! + 1\cdot4! = 5!\cdot3.$$

-