A Tinker’s Trade - Lauren Ipsum: A Story About Computer Science and Other Improbable Things - page 33

“Way more.”
“Um, a million?” Laurie said.
“More like a million million times that!” said Tinker.
“But how can that be?”
“Let's say there are only three towns: A, B, and C,” Tinker said. “You are already standing in
A, so you have to worry only about B and C. How many ways can you go?”
“Well,” she said, “I could go from B to C, or go to C and then B. That's two.”
“That's right! But BC is the same as CB, just backward. Every path has a mirror image, so
with three towns there is really only one possible path that visits them all. What if there were
four towns, A, B, C, and D?”
Laurie counted on her fingers. “I could go BCD, or BDC, or CBD, or CDB, or DCB, or . . .
DBC. Six! No, three.”
“That's three times as many. Add another town, and you have twelve times as many,” Tinker
said. “Add a sixth town and there are sixty different paths through all of them. With seven
towns there are three hundred sixty paths . As you add more towns, the number of paths gets
very big!”
3 towns: 2 ÷ 2 = 1
4 towns: 2 × 3 ÷ 2 = 3
5 towns: 2 × 3 × 4 ÷ 2 = 12
6 towns: 2 × 3 × 4 × 5 ÷ 2 = 60
7 towns: 2 × 3 × 4 × 5 × 6 ÷ 2 = 360
8 towns: 2 × 3 × 4 × 5 × 6 × 7 ÷ 2 = 2,520
9 towns: 2 × 3 × 4 × 5 × 6 × 7 × 8 ÷ 2 = 20,160
“For twenty-one towns you have to multiply one times two times three times four, all the
way up to twenty. It makes a HUGENORMOUS number!”
2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 × 11 × 12 × 13 × 14 × 15 × 16 × 17 × 18 × 19 × 20 ÷ 2 =
1,216,451,004,088,320,000
“!” said Laurie.
“Indeed!” Tinker said. “All of that 'one times two times three' stuff takes too long to write.
So you can use the exclamation point as a shorthand.”