Enumerating the number of insert delete BSTs on n elements

ins_del.rb

#Chad Brewbaker 1/13/2014
#Counting the number of insert delete binary search trees
#http://cstheory.stackexchange.com/questions/20533/height-of-randomly-built-binary-search-tree-by-insert-and-delete?noredirect=1#comment54289_20533
# Seems to be  http://oeis.org/A000680

def legal_tree(arr)
  1.upto(arr.length/2) do  |i|
     ins=   arr.rindex([i, 0].to_s)
     del= arr.rindex([i, 1].to_s)
    if ins > del
      return false
    end
  end
  return true
end


def ins_del(size)
  arr = []
  1.upto(size) do  |i|
    arr.push( [i, 0].to_s)
    arr.push( [i, 1].to_s)
  end
   count =0
  arr.permutation(arr.length).each {|p|
      if(legal_tree(p.dup))
        count = count +1
      end
  }
 return count
end

1.upto(10) do |i|
  puts   "There are " + ins_del(i).to_s + " legal insert/delete BSTs on " + i.to_s + " elements."
end