You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

 

Solutions:

 

Define g(n, l, r) as the result of this question, and f(n, l) as "N blocks, from left, see L blocks".
Then for each position the highest block can be, we have:

g(n,l,r) = (1<=k<=n) sum(C(n-1, k-1) * f(k-1, l-1) * f(n-k, r-1))
f(n, l) = (1<=k<=n) sum(C(n-1, k-1) * f(k-1, l-1) * (n-k)! )
f(n,1) = (n-1)!
f(n, n) = 1
f(n, m) = 0 if n < m

 

 

 

 

 

More Solutions