A163947 Number of functions on a finite set that are not obtainable by any composition power (excluding identity as power).

0, 0, 6, 84, 1400, 25590, 516432

Offset

1,3

Comments

a(n) is the number of functions on a finite set {1,...,n} that are not composition powers of any other function or powers(>1) of itself.

Hard to compute for n>7, as the number of functions to test is n^n.

Links

Table of n, a(n) for n=1..7.

Formula

a(n) = n^n - A163948(n).

Example

For n=2, the set is {1,2} and we have 4 functions: the constants 1 and 2, the identity, and the transposition. Any composition power of a constant function or of identity is the function itself. Odd composition powers of the transposition give the transposition. Thus all 4 functions are represented.
For n=3, the set is {1,2,3} and f:{1,2,3}->{1,1,2} cannot be represented by composition powers of any other function, or powers of itself (as fof gives the constant function=1). There are 6 functions in this situation (similar).

Crossrefs

Cf. A102687, A163859, A163860, A163861, A163948.

Sequence in context: A244284 A011945 A113888 * A306244 A277304 A128575

Adjacent sequences: A163944 A163945 A163946 * A163948 A163949 A163950

Keyword

more,hard,nonn

Author

Carlos Alves, Aug 06 2009

Status

approved