Explain why the number of routes for Sharifa in Example, increased as it did. For example,...

Explain why the number of routes for Sharifa in Example, increased as it did. For example, if you found that the number of routes for five cities is 120, how would the total number of routes increase for six cities? What about for seven?

Example Determining the Number of Routes for a Salesperson

Suppose that Sharifa is going to visit branch offices of her medical supply company based in Atlanta with branch offices in Boston, New York, Cincinnati, Miami, Detroit, Portland, Los Angeles, Houston, and Kansas City. How many different ways can she begin in Atlanta, visit all branches, and return home?

SOLUTION:

In solving this problem, we will use several of our problem-solving techniques that we discussed in Section 1.1—we will consider simpler examples, draw diagrams, list our examples systematically, and look for a pattern. We will represent the cities by the first letter of their names. Suppose there was only the one office in Atlanta. Then Sharifa would make no visits. If there were one other city—say, Boston—then she would visit Boston and return home. We will represent her one possible trip by a tree diagram as in Figure. The diagram shows that there is only one possible trip: she would travel from A to B. Now suppose that there are two branch offices, Boston and New York. The diagram would now look like Figure. Here we see that there are two possible trips: ABN and ANB, and then return home.

With three branch offices—Boston, New York, and Cincinnati—the diagram would look like Figure.

We begin to see a pattern that we explain in Table. We will indicate a route by listing the first letter of the cities in the order that they are visited.

Figure (a) One branch office, Boston.(b) Two branch offices, Boston and New York.(c) Three branch offices?Boston, New York, and Cincinnati.

Systematically listing routes as more cities are added.