[seqfan] Re: pebbles sequence

[drew at math.mit.edu]

Hi Tanya,

This is an interesting problem. I think it actually suggests three 
sequences, one of which appears to already be in the OEIS (but with no 
connection to pebble sequences noted).

First, we have the sequence that you have computed, where a(n) is the 
length of the longest non-repeating sequence of pebble-moves among the 
partitions of n. I would suggest that this is the main "pebble-sequence".

The first 100 terms of this sequence are:

 1, 2, 3, 5, 6, 7, 8, 9, 11, 13, 13, 13, 14, 19, 21, 21, 18, 19, 22, 29, 
31, 31, 25, 25, 26, 33, 41, 43, 43, 36, 32, 33, 37, 46, 55, 57, 57, 49, 41, 
41, 42, 51, 61, 71, 73, 73, 64, 55, 50, 51, 56, 67, 78, 89, 91, 91, 81, 71, 
61, 61, 62, 73, 85, 97, 109, 111, 111, 100, 89, 78, 72, 73, 79, 92, 105, 
118, 131, 133, 133, 121, 109, 97, 85, 85, 86, 99, 113, 127, 141, 155, 157, 
157, 144, 131, 118, 105, 98, 99, 106, 121

Second, we have the sequence in which a(n) is the length of the longest 
cycle of pebble-moves among the partitions of n.

The first 100 terms of this sequence are:

1, 2, 1, 3, 3, 1, 4, 4, 4, 1, 5, 5, 5, 5, 1, 6, 6, 6, 6, 6, 1, 7, 7, 7, 7, 
7, 7, 1, 8, 8, 8, 8, 8, 8, 8, 1, 9, 9, 9, 9, 9, 9, 9, 9, 1, 10, 10, 10, 10, 
10, 10, 10, 10, 10, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 12, 12, 
12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 
13, 13, 13, 1, 14, 14, 14, 14, 14, 14, 14, 14, 14

which is not in the OEIS, but follows a simple pattern that begs for a 
proof.

Third, we can consider the sequence in which a(n) is the length of the 
shortest cycle of pebble-moves among the partitions of n.

The first 100 terms of this sequence are:

 1, 2, 1, 3, 3, 1, 4, 2, 4, 1, 5, 5, 5, 5, 1, 6, 3, 2, 3, 6, 1, 7, 7, 7, 7, 
7, 7, 1, 8, 4, 8, 2, 8, 4, 8, 1, 9, 9, 3, 9, 9, 3, 9, 9, 1, 10, 5, 10, 5, 
2, 5, 10, 5, 10, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 12, 6, 4, 3, 
12, 2, 12, 3, 4, 6, 12, 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 
1, 14, 7, 14, 7, 14, 7, 2, 7, 14

which agrees with the first 100 terms of A054531. Obviously this also begs 
for a proof. In any case A054531 probably deserves a comment.

In terms of your original question, based on this data the growth of the 
first sequence is roughly linear in n.

Regards,

Drew


On Nov 18 2009, Tanya Khovanova wrote:

>Hello Sequence Fans,
>
>I suggest to add pebble sequences based on the famous pebble problem:
>
> You have 45 pebbles arranged in several piles. Each turn you take one 
> pebble from each pile and put them into a new pile. What is an asymptotic 
> behavior for this process?
>
> For example, if you start with one pile of 6, next step will be two 
> piles: {1,5}, then {2,4} and so on. Eventually the sequence of partitions 
> will start repeating itself.
>
> The sequence I calculated is the following: given n - the number of 
> pebbles we take a partition and apply the operation above until we see a 
> partition that we saw before. The sequence is the number of steps we need 
> until the sequence repeats itself for the worst partition.
>
> For example, for n = 6, the worst case is {2,2,1,1}, and the steps are: 
> {2, 2, 1, 1}, {1, 1, 4}, {3, 3}, {2, 2, 2}, {1, 1, 1, 3}, {2, 4}, {1,
>  2, 3}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}. Hence a(6) = 7.
>
>Here is the coding in Mathematica and the sequence:
>
>In[33]:= << Combinatorica`
>step[list_] := Sort[Select[Prepend[list - 1, Length[list]], # > 0 &]]
>cycleStart[list_] := (res = 1; sofar = {list}; current = list; 
>  nextStep = Nest[step, current, 1]; 
>  While[! MemberQ[sofar, nextStep], res++; current = nextStep; 
>   nextStep = Nest[step, current, 1]; sofar = Append[sofar, current]];
>   res)
>Table[Max[Map[cycleStart, Partitions[n]]], {n, 30}]
>
> Out[36]= {1, 2, 3, 5, 6, 7, 8, 9, 11, 13, 13, 13, 14, 19, 21, 21, 18, 19, 
> 22, 29, 31, 31, 25, 25, 26, 33, 41, 43, 43, 36}
>
> My problem is that I am not sure which sequence to call the pebble 
> sequence, the one I calculated or a(n)+1, when we see the first 
> repetition, or the longest sequence of terms before the cycle starts.
>
> I need help with naming and describing these sequences, (not to mention 
> that more terms would be nice)
>
>Tanya
>
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>