A Solution
Last week’s Leftovers post contained three old problems. JBL solved one of them, but there are two still left over. Here is the answer to one of them
The Barcelona Barber
A Barcelona barber usually gives good hair cuts, but today he was spectacular. Ten in a row, absolutely perfect. He hires a photographer to take pictures of the pleased clients in different arrangements.The photographer is no dummy. He … wants to get home in a reasonable amount of time, so he asks for some constraints.
To continue click ——–>
It’s good with the barber. “Take them in two rows of five each. Let each man be taller than the man to his left, and let each man be taller than the man immediately in front of him. And take all the arrangements like that!”
The photographer agrees. How many photos will he take? (June 3)
Well, this is a bit unusual. If you haven’t seen this before you have little choice but list out the possibilities. Let’s let our men be A through J, short to tall.
JIHGF
EDCBA
IHGE
FDCBA
JIHFE
GDCBA
JIGFE
HDCBA
JHGFE
IDCBA
JIHGD
FECBA
JIHFD
GECBA
JIHED
GFCBA
JIGFD
HECBA
JIGED
HFCBA
JIFED
HGCBA
JHGFD
IECBA
JHGED
IFCBA
JHFED
IGCBA
JIHGC
FEDBA
JIHFC
GDEBA
JIHEC
GFDBA
JIHDC
GFEBA
JIGFC
HEDBA
JIGEC
HFDBA
JIGDC
HFEBA
JIFEC
HGDBA
JIFDC
HGEBA
JHGFC
IEDBA
JHGEC
IFDBA
JHGDC
IFEBA
JHFEC
IGDBA
JHFDC
IGEBA
JIHGB
FEDCA
JIHFB
GEDCA
JIHEB
GFDCA
JIHDB
GFECA
JIGFB
HEDCA
JIGEB
HFDCA
JIGDB
HFECA
JIFEB
HGDCA
JIFDB
HGECA
JHGFB
IEDCA
JHGEB
IFDCA
JHGDB
IFECA
JHFEB
IGDCA
JHFDB
IGECA
I got 42. Quite an exercise in organized list-making. Was there another way? I can only make one suggestion: Smaller numbers. If we have two, there is only one way. If there are 4, there would be 2 ways. If there were 6 people, we would have five ways (I am only supplying the back row):
FED
FEC
FEB
FDC
FDB
With 8 people, there would be 14 ways. So we have 1,2,5,14… And following JBL, we can plug those into
The On-Line Encyclopedia of Integer Sequences
which quickly lets us know that we seem to have the Catalan numbers (thus Barcelona Barber, ha ha)
(The numbers themselves have nothing to do with Catalonia, they are named for a mathematician George Catalan. Ever wonder where the name of the London Plane Tree, NYC’s offical tree, comes from? Same sort of story.)
The Catalan numbers are interesting enough that I may devote a post to them in the near future.
JD2718 
The first definition of the Catalan numbers I ever met was that C_n = “the number of paths from (0, 0) to (n, n) along gridlines that never pass above the line y = x.” It’s a fun process to try and prove that various different problems have the Catalan numbers as solutions — that is, to show that problem A and problem B have teh same answer, without ever calculating that answer (constructing a correspondence). This question maps fairly quickly onto the question I mention above, if we consider arranging the 10 people, one at a time, starting with the tallest.
They (and the various places they appear) are definitely worthy of a future post.
Then there will be that post. The mappings between problems can be quite interesting. We can move easily from yours to “how many ways can votes for two candidates be counted so that the final count is a tie, but at every point until the final count, candidate A is in the lead.”