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.

1, 1, 3, 8, 15, 64, 65, 426, 847, 2528, 2529, 27730, 27731, 360372, 360373, 360374, 720735, 12252256, 12252257, 232792578, 232792579, 232792580, 232792581, 5354228902, 5354228903, 26771144424, 26771144425, 80313433226

Offset: 0

Author

Toby Bartels (toby(AT)math.ucr.edu), Nov 25 2001

Keywords

• easy
• nonn
• nice

Comments

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.

This rig is the natural numbers modulo the congruence generated by setting a(n) equivalent to a(n)-n.

Examples

			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).
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.
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.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..100

Crossrefs

a(n) = A060401(n)-1 = A003418(n)+n-1, except at n=0 (where the cross-references are undefined).

Programs

Haskell

a065500 n = a003418 n + n - signum n -- Reinhard Zumkeller, Sep 15 2011

Mathematica

a[n_] := LCM @@ Range[n] + n - 1; a[0] = 1; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Dec 16 2011 *)

Formula

a(n) = lcm(seq(i, i=1..n))+n-1, except at n=0 (where the lcm is infinite).