|
FORMULA
|
If x appears after x-1 in the permutation then we say that x is a ceiling point.
if i = 1: aup(n,k,i,l) = sum( abar(n,k,i,l) for m in [0..k] )
otherwise: aup(n,k,i,l) = sum( abar(n-1,k,1,m) for m in [l..k] ) + sum( sum( adown(n-1,k,j,m) for m in [i..k]) for j in [1..i-1] )
abar(n,k,i,l) = sum( a(n-1,k-1,j,l-1) for j in [1..k-1] )
adown(n,k,i,l) = sum( aup(n-1,k,j,l) + adown(n-1,k,j,l) for j in [i..k] )
a(n,k,i,l) = aup(n,k,i,l) + adown(n,k,i,l) + abar(n,k,i,l)
where n is the length, k is the number of left to right minima, i is the position of the maximum, l is the position of the first ceiling point
aup implies that max is a ceiling point, abar implies that max is a left to right minimum and adown implies max is neither.
Initial conditions: if i > l or k > n or i > k or l > k then aup(n,k,i,l) = adown(n,k,i,l) = 0, if i < l or l <= 0 then aup(n,k,i,l) = 0, if n - k = 1 then a(n,k,i,l) = 1, if i does not equal 1 the abar(n,k,i,l) = 0, abar(n,n,1,0) = 1.
a(n) = sum( sum( sum( a(n,k,j,m) for m in [0..k] ) for j in [1..k] ) for k in [1..n] )
|