using Memoize


#Avoid12453(n) gives the number of permutations of length n avoiding the pattern 12453
function Avoid12453(n)
	tic()
	output = Avoid12453_helper(n+1,n+2,[0])
	toc()
	return(output)
end

@memoize Dict function Avoid12453_helper(i,j,L)
	if (L == [0] && i == 1 && j == 2)
		return(1)
	end
	output = 0
	
	for k = 1:(i-1)
		output += Avoid12453_helper(k,j-1,L)
	end
	
	for k = (i+1):(j-1)
		Lp = copy(L)
		Lp[1] = Lp[1] + (j-k-1)
		Lp = r(Lp)
		output += Avoid12453_helper(i,k,Lp)
	end

	if L[1] > 0
		Lp = copy(L)
		Lp[1] = L[1] - 1
		Lp = r(Lp)
		output += min(2,L[1])*Avoid12453_helper(i,j,Lp)
	end
	for k = 2:(L[1]-1)
		Lp = r(vcat([k-1,L[1]-k],L[2:end]))
		output += Avoid12453_helper(i,j,Lp)
	end
	
	return(output)
end

r = function(L)
	Lp = L
	Lp = filter!(e->e!=0,Lp)
	if Lp == []
		return([0])
	else
		return(Lp)
	end
end