A188160 For an unordered partition of n with k parts, remove 1 from each part and append the number k to get a new partition until a partition is repeated. a(n) gives the maximum steps to reach a period considering all unordered partitions of n.

0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 12, 12, 13, 18, 20, 20, 17, 18, 21, 28, 30, 30, 24, 24, 25, 32, 40, 42, 42, 35, 31, 32, 36, 45, 54, 56, 56, 48, 40, 40, 41, 50, 60, 70, 72, 72, 63, 54, 49, 50, 55, 66, 77, 88, 90, 90, 80, 70, 60, 60, 61

Offset: 1

Author

Paul Weisenhorn, Mar 28 2011

Keywords

• nonn

Comments

Alternatively, if one iteratively removes the largest part z(1) and adds 1 to the next z(1) parts to get a new partition until a partition recurs, one gets the same maximum number of steps to reach a period.

The two shuffling operations are isomorphic for unordered partitions.

The two operations have the same length and number of periods for ordered and unordered partitions.

The steps count the operations including any pre-periodic part up to the end of first period, that is, the number of distinct partitions without including the first return.

Examples

			For k=6 and 0 <= j <= 1:
a(19)=21;  a(20)=28;  a(21)=30;  a(22)=30;  a(23)=24;  a(24)=24;  a(25)=25.
For n=4: (1+1+1+1)->(4)->(3+1)->(2+2)->(2+1+1)--> a(4)=4.
For n=5: (1+1+1+1+1)->(5)->(4+1)->(3+2)->(2+2+1)->(3+1+1)-->a(5)=5.
		

References

• R. Baumann LOG IN, 4 (1987)
• Halder, Heise Einführung in Kombinatorik, Hanser Verlag (1976) 75 ff.

Links

• Ethan Akin, Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250
• J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982) 483-486

Crossrefs

Cf. A185700, A177922, A184996, A037306.

Programs

Maple

A188160 := proc(n)
        local k,j,T ;
        if n <= 2 then
                return n-1 ;
        end if;
        for k from 0 do
                T := k*(k+1) /2 ;
                if n = T and k >= 1 then
                        return k*(k-1) ;
                end if;
                if k>=4 then
                        j := T-1-n ;
                        if j>= 0 and j <= (k-4)/2 then
                                return k^2-k-2-(k+1)*j ;
                        end if;
                        j := n-T-1 ;
                        if j>= 0 and j <= (k-4)/2 then
                                return k^2-k-k*j ;
                        end if;
                end if;
                if k >= 2 then
                        j := n-(k^2+2*k-(k mod 2))/2 ;
                        if j>=0 and j <= 1 then
                                return (k^2+2*k-(k mod 2))/2+j
                        end if;
                end if;
        end do:
        return -1 ;
end proc: # R. J. Mathar, Apr 22 2011

Formula

a((k^2+k-2)/2-j) = k^2-k-2-(k+1)*j with 0<=j<=(k-4)/2 and 4<=k.

a((k^2+k+2)/2+j) = k^2-k-k*j with 0<=j<=(k-4)/2 and 4<=k,

a((k^2+2*k-(k mod 2))/2+j) = (k^2+2*k-(k mod 2))/2+j with 0 <= j <= 1 and 2 <= k.

a(T(k)) = 2*T(k-1) = k^2-k with 1 <= k for the triangular numbers T(k)=A000217(k).