Mathematics desk
< October 6	<< Sep \| October \| Nov >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 7

Complete stepping-on sequences

The circular permutation 07531642 has the property that all "stepping-on" sequences (pick a value, move to the right by the indicated number of steps, continue until 0, and thus termination, is reached or cycling occurs) terminate, and starting at 1 gives the complete sequence 16345270. It's easy to see that only permutations from 0 up to an odd integer 2n-1 can have this property - direct enumeration has given the number of them for n = 1, 2, 3, 4, 5 and 6 as 1, 2, 4, 24, 288 and 3856. Looking at OEIS shows these values occurring in (sequence A141599 in the OEIS), which gives the number of permutations having a different property, essentially that the differences between successive terms, mod the length of the permutation, are all different. So my question is in two parts:

(a) Can the properties be reconciled to show that the two kinds of permutations have the same count for all n? (b) Can the count be calculated, rather than checking all (2n-2)! permutations? I suspect that the answer is not readily, as A141599 has values up to only n = 9, and that one was added recently.

→2A00:23C6:590:300:5CD8:E918:AA35:EF1E (talk) 15:19, 7 October 2018 (UTC)[reply]

Part (b) - apparently not, as far as is known. Bubba73 ^{You talkin' to me?} 23:26, 7 October 2018 (UTC)[reply]

I'm a bit confused; for n = 1 I get 01 only, for n=2 I get 0312 only, and for n=3 I get 053142 only, so the sequence you're looking for seems to be 1, 1, 1, ... . If p is the original permutation, 07531642 in your example, and s is the step sequence, or 16345270 in your example, then the condition on s is that for any (contiguous) subsequence the sum of the entries is not a multiple of 2n. (Applying this to the entire sequence gives you the even-ness condition; to me it wasn't all that easy to see, but the proof is short once you know the trick.) That means, for example, for 2n=8 you can eliminate s's that start 17... or 125... . Using a depth-first search you could use this condition to considerably trim the branches and greatly reduce the number of permutations considered. The calculation time would probably still grow exponentially with n however. I'm not entirely sure this applies though since I'm getting different numbers. If you look at the cumulative sums of the entries of p, or 1, 7, 10, 14, 19, 21, 28 in the example, and reduce mod 2n, or 1726354, the result has the property described in A141599, so maybe that has something to do with why the numbers you're getting match that sequence. --RDBury (talk) 02:50, 8 October 2018 (UTC)[reply]

Ok I think my problem was I was assuming you had to start the "stepping on" at 1 as in the example. So for n=3 the four permutations are 014235, 053142, 042531, 013425, where you start at the bold entry. I'm pretty sure that everything I said before still holds and the correspondence you're looking for is given by taking partial sums pf the s's. --RDBury (talk) 03:30, 8 October 2018 (UTC)[reply]

If the permutation is of 0, 1, ... p, then the total length stepped is p(p+1)/2, which for even p is a multiple of the permutation length p+1, so it is impossible to land on 0. For odd p, likewise, a complete terminating sequence must begin "halfway" at position (p+3)/2 in the permutation; for the case above where p=5, all of the emboldened starts are indeed in position 4.Semiable (talk) 16:35, 8 October 2018 (UTC)[reply]