1,3

For the rules of the Jumping Frogs game, see A377232.

Counts the number of distinct winning positions of the game with exactly n frogs, each in a different place. Positions are considered the same if one can be obtained from the other by reversing it left-to-right.

Equivalently, a(n) is the number of unordered pairs {k, A030101(k)} with k odd such that the binary weight A000120(k) = n, and k occurs in A377232.

Since a stack of k frogs moves exactly k spaces in the Jumping Frogs game, the sum of the lengths of all moves starting from a position with n single frogs is at most A000217(n-1), the (n-1)st triangular number. Hence if it is a winning position, the length of the position (excluding unoccupied places to the left of the first occupied one, and unoccupied places to the right of the last occupied one) is at most one more than this triangular number. Therefore a(n) is finite for all n.

See references at A377232.

Jinyuan Wang, Python program.

For four frogs, we can win:

1111 -> 0211 -> 0013 -> 0004

11101 -> 02101 -> 03001 -> 00004

11011 -> 02011 -> 02020 -> 04000

111001 -> 201001 -> 003001 -> 000004

1101001 -> 0201001 -> 0003001 -> 0000004

Any other position with four frogs in different places is either a left-right reversal of one of these, or no sequence of moves will result in all frogs in the same place. Hence a(4)=5.

Equivalently, one can start with four frogs in a single place and make a tree of all possible reverse moves, and then count leaves in which all frogs are in different places:

_____________4____

/ | \

___3001___ 202 13

/ | | \ / \ |

201001 12001 2101 1021 1102 112 121

/ | | | |

1101001 111001 11101 1111 11011

Again we see that a(4) = 5. (Note that nodes whose labels or reversed labels have already occurred earlier in a row are omitted from this tree.)

Cf. A000120, A000217, A030101, A377232, A377307.

Sequence in context: A050258 A383829 A051436 * A054581 A203151 A140440

Adjacent sequences: A378001 A378002 A378003 * A378005 A378006 A378007

nonn,more

Glen Whitney, Nov 13 2024

a(16)-a(18) from Jinyuan Wang, Nov 25 2024

approved