cp's OEIS Frontend

A224345 Number of closed normal forms of size n in lambda calculus with size 0 for the variables.

%I A224345 #39 Jan 20 2018 11:51:36
%S A224345 1,3,11,53,323,2359,19877,188591,1981963,22795849,284285351,
%T A224345 3815293199,54762206985,836280215979,13527449608779,230894574439485,
%U A224345 4144741143359355,78017419806432567,1535903379571939981,31550210953904250759
%N A224345 Number of closed normal forms of size n in lambda calculus with size 0 for the variables.
%H A224345 Pierre Lescanne, <a href="/A224345/b224345.txt">Table of n, a(n) for n = 1..500</a>
%H A224345 Maciej Bendkowski, K Grygiel, P Tarau, <a href="http://arxiv.org/abs/1612.07682">Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers</a>, arXiv preprint arXiv:1612.07682, 2016
%H A224345 K. Grygiel and P. Lescanne, <a href="http://arxiv.org/abs/1210.2610"> Counting and generating lambda-terms</a>, arXiv preprint arXiv:1210.2610 [cs.LO], 2012-2013.
%H A224345 Paul Tarau, <a href="http://www.cse.unt.edu/~tarau/research/2015/dbx.pdf">On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization</a>, 2015.
%H A224345 P. Tarau, <a href="http://arxiv.org/abs/1507.06944">A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations</a>, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.
%H A224345 Paul Tarau, <a href="https://arxiv.org/abs/1608.03912">A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms</a>, arXiv preprint arXiv:1608.03912 [cs.PL], 2016.
%F A224345 a(n) = F(n,0) where F(0,m) = m, F(n+1,m) = F(n,m+1) + G(n+1,m), and G(0,m) = m, G(n+1,m) = sum(k=0..n, G(n-k,m)*F(k,m)*d(n,0) ) where d(0,i) = [i = 1], d(n+1,i) = sum(j=i..n+1, binomial(j,i)*d(n,j) + g(n+1,j) ) and g(0,i) = [i = 1], g(n+1,i) = sum(j=0..i, sum(k=0..n, g(k,j)*d(n-k,i-j) ) ).
%t A224345 F[0, m_] := m; F[n_, m_] := F[n, m] = F[n-1, m+1] + G[n, m]; G[0, m_] := m; G[n_, m_] := G[n, m] = Sum[G[n-k-1, m]*F[k, m], {k, 0, n-1}]; a[n_] := F[n, 0]; Array[a, 20] (* _Jean-François Alcover_, May 23 2017 *)
%o A224345 (Haskell)
%o A224345 gtab :: [[Integer]]
%o A224345 gtab = [0..] : [[s n m |  m <- [0..]] | n <- [1..]]
%o A224345   where s n m  = let fi =  [ftab !! i !! m | i <- [0..(n-1)]]
%o A224345                      gi =  [gtab !! i !! m | i <- [0..(n-1)]]
%o A224345                  in foldl (+) 0 (map (uncurry (*)) (zip fi (reverse gi)))
%o A224345 ftab :: [[Integer]]
%o A224345 ftab = [0..] : [[ftab !! (n-1) !! (m+1) + gtab !! n !! m | m<-[0..]] | n<-[1..]]
%o A224345 f(n,m) = ftab !! n !! m
%Y A224345 Cf. A220894, A135501, A220895, A220896, A220897.
%Y A224345 Cf. A195691 for another size of the terms.
%K A224345 nonn
%O A224345 1,2
%A A224345 _Pierre Lescanne_, Apr 04 2013