A322253 Number of circular permutations of the integers from 0 to n which generate a complete stepping-on sequence, when the stepping-on direction depends on the odd/even parity of the current value.

1, 2, 2, 4, 4, 48, 24, 32, 288, 3072, 3856, 38272, 89328, 1294080

Offset: 1

Author

Ian Duff, Dec 01 2018

Keywords

• nonn
• more

Comments

There are n! circular permutations of the integers from 0 to n. Only some have the property that a complete sequence of these integers can be found by choosing a start value then continuing to move left or right by the number of steps indicated, the direction of each move depending on whether the current value is odd or even. For example, of the six permutations for n = 3, only 0132 and 0213 generate a complete sequence if an odd value gives a leftward move that number of places and an even value gives a rightward move that number of places. If the direction rule is reversed, the two valid permutations are 0231 and 0312, the reverse of the previous two. Thus a(3) = 2.

Putting 0 in position 1 at the left and counting rightwards, the starting position for a complete sequence is 2 + floor(n/2) for the rule odd/left, even/right and floor((n+3)/2) for the opposite rule. As a further example, one of the a(9) = 288 valid permutations using the former rule for n = 9 is 0986423175. Starting at position 2 + floor(9/2), i.e., 6, the sequence 2, 1, 3, 6, 5, 4, 7, 9, 8, 0 is found. Clearly, all such sequences end with zero.

It is conjectured that the sequence continues indefinitely.

From David A. Corneth, Dec 05 2018: (Start)

For even n, if [d1, d2, ..., dn] is a valid permutation then so is [n + 1 - d1, n + 1 - d2, ..., n + 1 - dn] which is a different permutation.

More generally, for any valid permutation where n is even, di and n+1 - di can be interchanged for any value (where n + 1 - di != di) to give another valid permutation. Hence a(n) is divisibly by 2^k for n = 2*k.

a(n) > 0. For n = 1, [0, 1] is valid, for n = 2, [0, 1, 2] is valid; for n = 3, [0, 3, 1, 2] is valid etc. By taking this valid tuple from n by adding n + 1 to the right of the permutation or to the right of the 0, depending on the parity of n, one finds another valid tuple. Hence a(n) > 0. (End)

For the complementary case where stepping-on is always in the same direction, no permutation of 0 to n with n even can generate a complete sequence. For odd n, the number of complete sequences corresponds to A141599((n + 1)/2) for n up to 11, as limited by available computing power - it is conjectured that this correspondence continues indefinitely. - Ian Duff, Dec 25 2018

Links

• David A. Corneth, tuples for a(n) for n = 1..12
• David A. Corneth, PARI program

Crossrefs

a(2n - 1) = A141599(n) for n up to 7, again limited by available computing power. It is conjectured that the correspondence continues indefinitely.

Programs

PARI

\\ See PARI link \\ David A. Corneth, Dec 04 2018

Extensions

a(12)-a(14) from David A. Corneth, Dec 04 2018