OFFSET
0,3
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.
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..100
FORMULA
a(n) = lcm(seq(i, i=1..n))+n-1, except at n=0 (where the lcm is infinite).
EXAMPLE
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.
PROG
(Haskell)
a065500 n = a003418 n + n - signum n -- Reinhard Zumkeller, Sep 15 2011
CROSSREFS
KEYWORD
easy,nonn,nice
AUTHOR
Toby Bartels (toby(AT)math.ucr.edu), Nov 25 2001
STATUS
approved