Endless Games of War: Counting the Deals That Never End

In the card game War with one card of each rank, cards 1, ..., n, the higher card wins each turn, and the winning card and then the losing card go under the winner's pile. Some deals never end. Let a(n) be the number of the n! deals of cards 1, ..., n that never end. We compute a(n) exactly for n ≤ 16, each value with at least two independent programs. Before this, a(10) and the zeros for n ≤ 4 were known from Spivey, and the zeros at n = 6, 8, 12 from searches of all deals by Delahaye and Mathieu. The zeros fall exactly at n = 1, 2, 3, 4, 6, 8, 12, 16, the numbers of the form 2^k or 3·2^k. Spivey (2010) proved that every other n has endless games, and his Question 2 asks whether these n have any cycles at all. For each of these n up to 16, an exhaustive search of the positions in which one player holds the highest card on top finds no position of any kind on a cycle. For odd n we prove that every cycle has length lcm(n+1, 2a, 2b) for some a, b ≥ 1 with a + b = (n-1)/2. Cycles can also be counted without any search, as linear extensions of explicit partial orders. This gives all cycles for odd n, with a closed form when (n+1)/2 is prime, and for every n the cycles of the type Spivey constructs. The length of every cycle of that type is divisible by n + 2^v, where 2^v is the largest power of 2 dividing n. Spivey's Question 1 asks whether War has cycles of other types than those constructed in the proof of his Theorem 3. It does. The smallest deck with one has 14 cards, and explicit families give such cycles, reached from ordinary deals, for every n = m·2^v with m ≡ 3 (mod 4), m ≥ 7 and v ≥ 1. Some of them have arbitrarily many categories in the sense of Spivey's original definition. The values a(n)/n! answer Spivey's Question 3 for n ≤ 16. The sequence is A400411 in the OEIS, and the code and data are public.