import qualified Data.MemoCombinators as Memo
-- memoizing a function remembers all earlier computed results
-- and thus is a form of Dynamic Programming

a195691 = normal True 0 where
  normal = Memo.memo3 Memo.bool Memo.integral Memo.integral $ \qLam k n ->
  -- counts number of normal form closed lambda terms of size n within k nested lambdas
  -- avoid redexes by not allowing the first term in an application to be a lambda term
   if n<2 then 0 else                                      -- no code shorter than 2 bits
     (if n-2<k then 1 else 0) +                    -- encode variable index n-1 in n bits
     (if qLam then normal True (k+1) (n-2) else 0) +   -- only count lambda terms if qLam
     sum [normal False k i * normal True k (n-2-i) | i <- [0..n-2]] -- count applications

main = print . map a195691 $ [0..]