How many ways can seven basketball players of different heights line up ?

In how many ways can seven basketball players of different heights line up in a single row so that no


player is standing between two people taller than he is?





Please show how you arrived at answer.|||It is 64, and this is easily shown by induction. (No combinitorics or long proofs are necessary!)





{The number of ways for k players is 2^(k-1) }


Each time a new player enters the line, the number of ways to line them up doubles.





Let n(k) be the number of ways for k players.


We can assume without loss of generality that the (k+1)st player is taller than all the others.





n(k+1) = 2n(k), since for each of the n(k) ways, we can place the (k+1)st player in one of only two places, namely immediately next to the kth (tallest) player on either side of him. If placed anywhere else, there will be at least one player between two taller players.





Since n(1) = 1, n(2) = 2, n(3) = 4, etc,


n(7) = 2^6 = 64|||did everybody miss the "no player is standing between two people taller than he is" part of the question?





**********





the answer's 64. i've got two methods to do it.





method 1 (the user-friendly idiot-proof method)





picture seven individual platforms in a row for the players to stand on (this's what i pictured anyway :p) these are the seven platforms:


A B C D E F G





now assume the players are of height 1ft, 2ft, 3ft, 4ft, 5ft, 6ft, 7ft. actually, honestly speaking, i don't really remember the last time i saw a 1-footer, 2-footer or 3-footer playing basketball, but we can ignore that i guess.





let's also assume that they go up the platforms in ascending height order, i.e. 1-ft goes up first, then 2-ft, then 3-ft... so they don't all rush to choose their favorite platforms at the same time and create chaos. note that this assumption does NOT change the outcome of the question in any way.





now take a look at Mr. 1-foot, where can he stand? he's only got two choices: A or G. if he stands anywhere from B to F he'd be sandwiched by taller guys, 'cause he's the shortest, this should be pretty obvious.





so from this observation we discover a general rule: the shortest shrimp (no offense to the vertically-challenged) ALWAYS stands on one of the far ends of the line.





case 1:


now say 1-ft chooses to go to platform A, so we're left with B~G unoccupied. who's the shortest among the 6 now? none other than Mr. 2-feet. so according to that rule thingy we discovered, he can only stand on B or G.





case 2:


similarly, if 1-ft chooses to go to platform G, we're left with A~F unoccupied, and so 2-ft can only go to A or F.





so 1-ft has 2 choices, and for each choice he makes, 2-ft has 2 choices too, and for each choice 2-ft makes, 3-ft will have 2 choices too, and so on and so forth.





here's a little catch: when we reach 6-ft, he has 2 choices too. after he makes his choice, 7-ft does NOT have a choice, he'd be forced to take that last unoccupied platform.





so it's 2*2*2*2*2*2 = 2^6 = 64





the first 2 represents the number of choices 1-ft can make


the 2nd 2 represents the number of choices 2-ft can make


...


the 6th 2 represents the number of choices 6-ft can make


7-ft has no choice to make so there's only one possibility, but multiplying by 1 is stupid so we'll ignore it.





i'll try my best to create a tree diagram to explain this if you still have trouble understanding.





......................................鈥?br>

.................................___A_鈥?choices


...........................__B__...._G鈥?choices


..........................C.......G...鈥?choices


...





the underscores are the branches to the letters below it.





method 2 (the "cheating" method):





think of it this way: rewrite the whole question, but change 7 players into 1 player, i.e. how many ways can 1 player line up so that he is not sandwiched by taller players, it's a stupid question that comes with the answer 1. duh, there's only ONE way to arrange 1 player - he stands alone.





now try 2 players: 2 players can't sandwich each other - you need 3 to form a "sandwich", so the only arrangements are (1,2) and (2,1), so the answer is 2 different arrangements.





now 3 players: there's only one requirement - 1-ft can't stand in the middle, so (1,2,3), (1,3,2), (2,3,1), and (3,2,1) are possible arrangements, thus there are 4 arrangements.





4 players: remember the "shortest guy must stand on ends" rule? (1,2,3,4) (1,2,4,3) (1,3,4,2) (1,4,3,2) (2,3,4,1) (2,4,3,1) (3,4,2,1) (3,4,1,2) - a grand total of 8 combinations.





you can try 5 if you want, but i find it inconvenient to type 16 combinations here, with 5 numbers each, so yeah.





notice a pattern?





1 player --%26gt; 1 arrangement


2 players --%26gt; 2 arrangements


3 players --%26gt; 4 arrangements


4 players --%26gt; 8 arrangements





can you guess the next?





5 players --%26gt; 16 arrangements


6 players --%26gt; 32 arrangements


7 players --%26gt; 64 arrangements!





and we've got it. to put it more mathematically:


(n) number of players gives 2^(n-1) arrangements.





**********





oh no, i don't know why my tree diagram looks like that, sorry about that.|||this is fairly simple stats:





7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040 ways





you have the first space were you can choose 7 or the 7 players to stand there





the second space you now only have 6 of the 7 players who can stand there





the third spot 5 of 7 and so forth








to add in standing between two people taller than him...i don't totally know if we have enough information about that, because then one of the players (the shortest would always have to be at one of the ends......so then we would have to keep those spots fixed...however the shortest guy has two spots he could be at.)|||5040 ways|||This is my second try:





The total # of arrangements that satisfy the requirement of nobody between two taller players is:





64





there are 7 positions for the tallest player. If he is on either end the other playres must line up by height so there is 1 way each. 2 positions * 1 way = 2.





If the tallest is 1 position in from the end there are 6 players who can be on the short end and the others must be in line so there are 6 ways each. 2 ways to be one 1 * 6 = 12





If the tallest is 2 positions in there are 6*5/2*1 = 15 ways to select 2 players on the short end, in height order. 2 ways to be 2 in * 15 = 30.





If the tallest player is in the middle position there are


6*5*4/3*2*1 = 20 ways to arrange the other 6 around him


in height order = 20.





Answer = 2 + 12 + 20 + 30 = 64 arrangements.





Whew!|||5040