why there are a trillion different ways to take the elevator to the 41st floor скачать в хорошем качестве

why there are a trillion different ways to take the elevator to the 41st floor

we present the 'compositions' of n: how many different ways can you write n as a sum of positive integers? we view this initially under the guise of the 'elevator' problem: how many different ways can you take an elevator up to a certain floor? we provide two different proofs that the number of compositions of n is given by the (n-1)th power of 2 (so that the number of ways to get to the 41st floor is 2^40 ~ 1 trillion) the first proof proceeds by observing a recursion between compositions namely, to reach the nth floor, one can: go up one floor from all the (n-1)th floor possibilities, go up two floors from all the (n-2)th floor possibilities, ... go up (n-2) floors from the 2nd floor possibilities go up (n-1) floors from the first floor, or lastly go straight there without stopping the function L(n)=2^(n-1) solves this recursion subject to the initial condition L(1)=1 the second proof proceeds by observing that the problem simply requires deciding at each floor whether to stop or not; or equivalently whether to 'slice' the given number (insert a plus between two summands) or not: as there are n-1 interstices, and 2 choices at each, there are necessarily 2^(n-1) different possibilities lastly, we show how one can enumerate the compositions with bits of length (n-1): we leave it to the viewer to discern why these, in descending order, are precisely the order in which the compositions are recursively generated