cp's OEIS Frontend

A065500 Number of distinct functions from a set with n^n elements to itself that can be defined naturally (in n) by typed lambda-calculus expressions.

%I A065500 #16 Nov 21 2013 13:11:37
%S A065500 1,1,3,8,15,64,65,426,847,2528,2529,27730,27731,360372,360373,360374,
%T A065500 720735,12252256,12252257,232792578,232792579,232792580,232792581,
%U A065500 5354228902,5354228903,26771144424,26771144425,80313433226
%N A065500 Number of distinct functions from a set with n^n elements to itself that can be defined naturally (in n) by typed lambda-calculus expressions.
%C A065500 Each of these sets of functions is naturally a quotient set of the set of natural numbers (including 0) on which addition and multiplication are well-defined, thus forming a commutative rig (not ring) with a(n) elements.
%C A065500 This rig is the natural numbers modulo the congruence generated by setting a(n) equivalent to a(n)-n.
%H A065500 Reinhard Zumkeller, <a href="/A065500/b065500.txt">Table of n, a(n) for n = 0..100</a>
%F A065500 a(n) = lcm(seq(i, i=1..n))+n-1, except at n=0 (where the lcm is infinite).
%e A065500 a(2) = 3 as follows: Let {a,b} be a set with 2 elements. Then the 2^2 = 4 functions from {a,b} to itself are i (the identity function), t (the transposition), a (the constant function with value a) and b (the constant function with value b).
%e A065500 We're looking at functions from {i,t,a,b} to itself that are defined by typed lambda-calculus expressions. These expressions are lambda-f.(lambda-x.x), lambda-f.(lambda-x.fx), lambda-f.(lambda-x.ffx), lambda-f.(lambda-x.fffx) and so on.
%e A065500 Respectively, these map (i,t,a,b) to (i,i,i,i), (i,t,a,b), (i,i,a,b), (i,t,a,b), (i,i,a,b), (i,t,a,b) and so on. Only the first 3 of these are distinct; thereafter they are all repetitions. Therefore a(2) = 3.
%t A065500 a[n_] := LCM @@ Range[n] + n - 1; a[0] = 1; Table[a[n], {n, 0, 27}] (* _Jean-François Alcover_, Dec 16 2011 *)
%o A065500 (Haskell)
%o A065500 a065500 n = a003418 n + n - signum n -- _Reinhard Zumkeller_, Sep 15 2011
%Y A065500 a(n) = A060401(n)-1 = A003418(n)+n-1, except at n=0 (where the cross-references are undefined).
%K A065500 easy,nonn,nice
%O A065500 0,3
%A A065500 Toby Bartels (toby(AT)math.ucr.edu), Nov 25 2001