A102687

[David Wilson]

Regarding this sort of sequence:

%I A000001
%S A000001 
3125,1075,985,580,1281,295,1305,580,925,631,1305,220,1305,655,901,580,1305,295,1305,\
556,925,655,1305,220,1281,655,925,580,1305,271,1305,580,925,655,1281,220,1305,655,\
925,556,1305,295,1305,580,901,655,1305,220,1305,631,925,580,1305,295,1281,580,925,\
655,1305,196,1305,655,925,580,1281,295,1305,580,925,631,1305,220,1305,655,901,580,\
1305,295,1305,556,925,655,1305,220,1281,655,925,580,1305,271,1305,580,925,655,1281,\
220,1305,655,925,556,1305
%N A000001 Let a(n,m) = card{f^(n) : f is a mapping from a set of m elements 
into itself}, where f^(l)(x) = f^(l-1)(f(x)),l>0, f^(0)(x) = x; sequence 
gives a(n,5).
%Y A000001 Cf. A102687.
%O A000001 1
%K A000001 ,nonn,

For any m, f^(0) = I, the identity mapping on m elements.  Thus a(0, m) = 1,
and we should prepend a(0) = 1 to the above sequence and any like sequences.

Regarding the values of a(n, m):

Let m = {0 ,..., m-1}, the standard set of m elements.  Let I : m -> m be 
the
identity on m, and f : m -> m be an injection on m.

If we look at the action of f on a single element x of m, we see that 
f^(k)(x)
(k = 0, 1, 2, ...) must be ultimately periodic.  The period must be reached
within m-1 iterations of f, and the period must be of length at most m.

 From this we can conclude that for any f, the sequence of mappings f^(k)
(k = 0, 1, 2, ...) is ultimately periodic in k, with at most m-1 initial 
elements
and fundamental period dividing q(m) = lcm(1, ..., m) = A003418(m).

 From this we can conclude that for fixed m >= 1, a(n, m) is ultimately
periodic with at most m-1 initial elements and period dividing q(m).

Let us look at the cases for m = 1 through 6:

a(n, 1) = (1)
a(n, 2) = 1 (4 3)
a(n, 3) = 1 27 (12 19 12 21 10 21)
a(n, 4) = 1 256 100 (116 73 148 44 148 73 116 76 148 41 148 76)
a(n, 5) = 1 3125 1075 985 (580 1281 295 1305 580 925 631 1305 220 1305 655 
901
        580 1305 295 1305 556 925 655 1305 220 1281 655 925 580 1305 271 
1305
        580 925 655 1281 220 1305 655 925 556 1305 295 1305 580 901 655 1305
        220 1305 631 925 580 1305 295 1281 580 925 655 1305 196 1305 655 
925)
a(n, 6) = 1 46656 13356 11026 5721 (12942 3136 13806 5601 9286 5952 13806 
1921
        13806 6816 8422 5601 13806 3136 13806 4737 9286 6816 13806 1921 
12942
        6816 9286 5601 13806 2272 13806 5601 9286 6816 12942 1921 13806 6816
        9286 4737 13806 3136 13806 5601 8422 6816 13806 1921 13806 5952 9286
        5601 13806 3136 12942 5601 9286 6816 13806 1057 13806 6816 9286 
5601)

 From this small amount of empirical data, it appears that a(n, m) has 
exactly
m-1 initial elements and period exactly q(m).

It also appears that for n >= m-1, a(n, m) is a function of gcd(n, q(m)). 
This
would indicate that the period of a(n, m) is the same as the period for 
gcd(n, q(m)),
that is, q(m).  It also indicates that there are at most d(q(n)) = 
A056793(n)
distinct elements in the period of a(n, m).

----- Original Message ----- 
From: "David Wasserman" <dwasserm at earthlink.com>
To: <ham>; <seqfan at ext.jussieu.fr>
Sent: Monday, February 07, 2005 2:36 AM
Subject: Re: A102687


> Dear Vladeta,
>    That is very interesting, and rather surprising.  At first I thought 
> a(n, 5) should be nonincreasing, but when I thought about it some more, I 
> saw why it isn't.
>    Did you also compute a(n, 3) and a(n, 4)?
>    I notice that for any given f: m -> m, the sequence f^(n) is eventually 
> periodic.  Therefore the sequence of sets {f^(n) | f: m -> m} is also 
> eventually periodic, its period being the lcm of the periods for each f. 
> So a(n, m) is also eventually periodic, probably with the same period but 
> possibly smaller.  It looks like a(n, 5) has period 60 after the first 3 
> terms.
>    {f: m -> m} is a symmetric group.  We can ask the same question about 
> any finite group.  For example, with the cyclic group of order k, we get 
> the sequence a(n) = n/gcd(n, k).  The quaternion group gives 
> 8,2,8,1,8,2,8,1...
>
> - David
>
>>Dear Seqfans,
>>
>>There is an interesting sequence of Eric Wegrzynowski:
>>
>><http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A102687>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A102687
>>
>>I just submitted to the OEIS:
>>
>>%I A000001
>>%S A000001 
>>3125,1075,985,580,1281,295,1305,580,925,631,1305,220,1305,655,901,580,1305,295,1305,556,925,655,1305,220,1281,655,925,580,1305,271,1305,580,925,655,1281,220,1305,655,925,556,1305,295,1305,580,901,655,1305,220,1305,631,925,580,1305,295,1281,580,925,655,1305,196,1305,655,925,580,1281,295,1305,580,925,631,1305,220,1305,655,901,580,1305,295,1305,556,925,655,1305,220,1281,655,925,580,1305,271,1305,580,925,655,1281,220,1305,655,925,556,1305
>>%N A000001 Let a(n,m) = card{f^(n) : f is a mapping from a set of m 
>>elements into itself}, where f^(l)(x) = f^(l-1)(f(x)),l>0, f^(0)(x) = 
>>x; sequence gives a(n,5).
>>%Y A000001 Cf. A102687.
>>%O A000001 1
>>%K A000001 ,nonn,
>>
>>
>>Best regards to all,
>>
>>Vladeta Jovovic
>
>