|
| |
|
|
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.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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.
|
|
|
MATHEMATICA
|
a[n_] := LCM @@ Range[n] + n - 1; a[0] = 1; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Dec 16 2011 *)
|
|
|
PROG
|
(Haskell)
|
|
|
CROSSREFS
|
a(n) = A060401(n)-1 = A003418(n)+n-1, except at n=0 (where the cross-references are undefined).
|
|
|
KEYWORD
|
easy,nonn,nice
|
|
|
AUTHOR
|
Toby Bartels (toby(AT)math.ucr.edu), Nov 25 2001
|
|
|
STATUS
|
approved
|
| |
|
|
