Combinatorics, Product Rule / Rule of Product

The Rule of Product is a fundamental counting principle: if there are `n` ways to do one task and `m` ways to do another task, then there are `n \times m` ways to perform both tasks. Questions involve applying this rule to count sequences of choices or outcomes.

  • THE ANTIQUARY'S CHAIN

    An antiquary possessed a number of curious old links, which he took to a blacksmith, and told him to join together to form one straight piece of chain, with the sole condition that the two circular links were not to be together. The following illustration shows the appearance of the chain and the form of each link. Now, supposing the owner should separate the links again, and then take them to another smith and repeat his former instructions exactly, what are the chances against the links being put together exactly as they were by the first man? Remember that every successive link can be joined on to another in one of two ways, just as you can put a ring on your finger in two ways, or link your forefingers and thumbs in two ways. Sources:

  • THE EIGHT ROOKS

    It will be seen in the first diagram that every square on the board is either occupied or attacked by a rook, and that every rook is "guarded" (if they were alternately black and white rooks we should say "attacked") by another rook. Placing the eight rooks on any row or file obviously will have the same effect. In diagram `2` every square is again either occupied or attacked, but in this case every rook is unguarded. Now, in how many different ways can you so place the eight rooks on the board that every square shall be occupied or attacked and no rook ever guarded by another? I do not wish to go into the question of reversals and reflections on this occasion, so that placing the rooks on the other diagonal will count as different, and similarly with other repetitions obtained by turning the board round. Sources:

  • LION-HUNTING

     

    My friend Captain Potham Hall, the renowned hunter of big game, says there is nothing more exhilarating than a brush with a herd—a pack—a team—a flock—a swarm (it has taken me a full quarter of an hour to recall the right word, but I have it at last)—a pride of lions. Why a number of lions are called a "pride," a number of whales a "school," and a number of foxes a "skulk" are mysteries of philology into which I will not enter.

    Well, the captain says that if a spirited lion crosses your path in the desert it becomes lively, for the lion has generally been looking for the man just as much as the man has sought the king of the forest. And yet when they meet they always quarrel and fight it out. A little contemplation of this unfortunate and long-standing feud between two estimable families has led me to figure out a few calculations as to the probability of the man and the lion crossing one another's path in the jungle. In all these cases one has to start on certain more or less arbitrary assumptions. That is why in the above illustration I have thought it necessary to represent the paths in the desert with such rigid regularity. Though the captain assures me that the tracks of the lions usually run much in this way, I have doubts.

    The puzzle is simply to find out in how many different ways the man and the lion may be placed on two different spots that are not on the same path. By "paths" it must be understood that I only refer to the ruled lines. Thus, with the exception of the four corner spots, each combatant is always on two paths and no more. It will be seen that there is a lot of scope for evading one another in the desert, which is just what one has always understood.

    Sources:

  • SETTING THE BOARD

    I have a single chessboard and a single set of chessmen. In how many different ways may the men be correctly set up for the beginning of a game? I find that most people slip at a particular point in making the calculation. Sources:

  • THE SIX PAWNS

    In how many different ways may I place six pawns on the chessboard so that there shall be an even number of unoccupied squares in every row and every column? We are not here considering the diagonals at all, and every different six squares occupied makes a different solution, so we have not to exclude reversals or reflections. Sources: