|
| |
|
|
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; 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
| 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.
|
|
|
MATHEMATICA
| a[n_] := LCM @@ Range[n] + n - 1; a[0] = 1; Table[a[n], {n, 0, 27}] (* From Jean-François Alcover, Dec 16 2011 *)
|
|
|
PROG
| (Haskell)
a065500 n = a003418 n + n - signum n -- Reinhard Zumkeller, Sep 15 2011
|
|
|
CROSSREFS
| a(n) = A060401(n)-1 = A003418(n)+n-1, except at n=0 (where the cross-references are undefined).
Sequence in context: A032064 A151397 A192167 * A120341 A094357 A136532
Adjacent sequences: A065497 A065498 A065499 * A065501 A065502 A065503
|
|
|
KEYWORD
| easy,nonn,nice
|
|
|
AUTHOR
| Toby Bartels (toby(AT)math.ucr.edu), Nov 25 2001
|
| |
|
|
