proposed

approved

editing

proposed

Reinhard Zumkeller, <a href="/A065500/a065500.txt">TITLE FOR LINK</a>

(Haskell)

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

approved

editing

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.

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.

easy,nonn,nice,new

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

easy,nonn,nice,new

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

0,3

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.

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

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.

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

easy,nonn,nice

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

approved