cp's OEIS Frontend

A378004 Number of winning positions of Gordon Hamilton's Jumping Frogs game with n single frogs, up to left-right symmetry.

%I A378004 #24 Nov 26 2024 08:19:15
%S A378004 1,1,2,5,12,39,123,412,1431,4831,17363,60697,219777,781260,2858031,
%T A378004 10329091,38103069,138996792
%N A378004 Number of winning positions of Gordon Hamilton's Jumping Frogs game with n single frogs, up to left-right symmetry.
%C A378004 For the rules of the Jumping Frogs game, see A377232.
%C A378004 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.
%C A378004 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.
%C A378004 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.
%D A378004 See references at A377232.
%H A378004 Jinyuan Wang, <a href="/A378004/a378004_2.py.txt">Python program</a>.
%e A378004 For four frogs, we can win:
%e A378004   1111 -> 0211 -> 0013 -> 0004
%e A378004   11101 -> 02101 -> 03001 -> 00004
%e A378004   11011 -> 02011 -> 02020 -> 04000
%e A378004   111001 -> 201001 -> 003001 -> 000004
%e A378004   1101001 -> 0201001 -> 0003001 -> 0000004
%e A378004 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.
%e A378004 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:
%e A378004                        _____________4____
%e A378004                       /             |    \
%e A378004                  ___3001___        202    13
%e A378004                 /   |  |   \      /   \    |
%e A378004           201001 12001 2101 1021 1102 112 121
%e A378004          /   |     |         |    |
%e A378004   1101001 111001 11101      1111 11011
%e A378004 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.)
%Y A378004 Cf. A000120, A000217, A030101, A377232, A377307.
%K A378004 nonn,more
%O A378004 1,3
%A A378004 _Glen Whitney_, Nov 13 2024
%E A378004 a(16)-a(18) from _Jinyuan Wang_, Nov 25 2024