Experimenting with Permutation Wordle

Aurora Hiveley Department of Mathematics Rutgers University Piscataway, NJ 08854 USA

                  aurora.hiveley@rutgers.edu

Abstract

Consider a game of permutation wordle in which a player attempts to guess a secret permutation in S_{n} in as few guesses as possible. In each round, the guessing player is told which indices of their guessed permutation are correct. How can we optimize the player’s strategy? Kutin and Smithline proposed a strategy called cyclic shift in which all incorrect entries are shifted one index to the right in successive guesses, and they conjectured its optimality. We investigate this conjecture by formalizing what a “strategy” looks like, performing experimental analysis on inductively constructed strategies, and examining the coefficients of an inductive strategy’s generating function.

1 Introduction

Consider a game in which a game master orders n objects labeled 1 through n, but keeps this ordering a secret. On your turn, you attempt to guess the secret ordering of these objects by guessing some permutation of {1, …, n}. The game master then indicates the subset of these n objects which are in the correct positions. The game ends when all objects are in the correct positions, meaning that you have guessed the secret ordering (referred to as the secret permutation.) This game, called “permutation wordle,” was developed by Kutin and Smithline [1] as a modification of Wardle’s popular New York Times game, Wordle. It is so called due to the similarities between the feedback loop in our game and that of Wordle.

Consider the following example game. The game master thinks of a secret permutation of {1, 2, …, 5}. Suppose they pick 42531, and say that the guesser’s first guess is 12345. The game master informs the guesser that the number 2 is in the correct position, and suppose the latter’s next guess is 52134. Now, the game master says that the number 3 is also in the correct position. The guesser’s next guess is 42531, so the game master tells them that this guess is fully correct. This game is completed in three guesses.

The study of permutation-guessing games is of great interest to the mathematical community and has been studied in several iterations. Kutin and Smithline were originally inspired by permutation-guessing games on Sporcle.com, and Stanley [5] considered a similar game based on the mobile game Royal Match. Li and Zhu [2] have studied a game similar to the classic board game Mastermind, but with a Wordle-like feedback loop. In their game, the secret code is pulled from the alphabet [m]^{n}, thereby acting as a more general version of our game since the secret code is not necessarily a permutation.

The guessing player in a game of permutation wordle will be interested in an optimal strategy. Kutin and Smithline proposed a strategy in which all incorrect objects from a guess are shifted one position to the right in a successive guess, skipping over (and leaving in place) each correct object. They dubbed this strategy circular shift, and they conjectured that this strategy is optimal among all strategies in such a game. Kutin and Smithline called a strategy optimal if the probability of success in r guesses, denoted by P_{r}, is maximal for all r. We say that a strategy is optimal if the average number of guesses needed to complete the game is minimized.

Conjecture 1. The average number of guesses needed to complete a game of permutation wordle is minimal when using the circular shifting strategy.

In this paper, we investigate the Kutin-Smithline conjecture by first formalizing what a strategy looks like for a game of permutation wordle and solidifying notation in Section 2. We then pursue an inductive approach, building strategies iteratively and examining how performance changes across iterations in Section 3. The central result of this paper, discussed in Section 4, uses generating functions to study the optimality of cyclic shift for a game terminating in one, two, or three guesses.

2 Notation

Following Kutin and Smithline’s notation, we use γ_{1}, γ_{2}, … to refer to the guessed permutations in each round. Without loss of generality and for ease of analysis, in this paper we always assume that γ_{1} = (1 2 … n). For a guess γ_{r}, let the set of correct positions (the ones which agree with the secret permutation) be denoted by J_{r}, and let the set of incorrect positions be denoted by I_{r}. In this sense, J_{r} ⊔ I_{r} = [n] for each r.

We formally define a strategy S as follows:

Definition 2. A strategy S is a list S := [s_{1}, s_{2}, …, s_{n}] where s_{i} is a permutation of length i. The i-th strategy component, s_{i}, may also be referred to with indexing notation, i.e., S[i].

To form the next guess γ_{r+1} from γ_{r} using S, we lock in all correct positions from J_{r} and permute the incorrect positions in I_{r}. We permute the elements of I_{r} according to the strategy component S[|I_{r}|]. In this way, we formalize Kutin-Smithline’s proposed “cyclic shift” strategy (abbreviated CS in this paper) by writing the following:

CS := [(1), (2 1), (2 3 1), …, (2 3 … n 1)] .

Then a general component of cyclic shift takes the form CS[i] = (2 3 … i 1). We default to a cyclic shift to the right, meaning that each incorrect index is shifted to the first available index to the right. But note that the leftward cyclic shifting strategy has an analogous interpretation in which a general component takes the form (n 1 2 … n − 1).

We preliminarily observe that a strategy component S[i] ought to be a derangement of [i], meaning a permutation without any fixed points (positions j such that S[i][j] = j). Otherwise, at least one incorrect entry is guessed in the same incorrect position for γ_{r+1} as it was in γ_{r}. Such a guess could never end the game since we know that at least one position is incorrect (in actuality, at least two positions are incorrect) and we waste an opportunity to learn more information by swapping a different element into that same incorrect position. Thus we assume that such a strategy must be inefficient, and so we use only derangements for strategy components. The study of derangements equates to the problem of hat-swapping, where n people each have a hat, and we want to know how many ways there are to return the hats such that no person ends up with their own. The number of derangements of {1, 2, …, n} can be calculated with a subfactorial, and this quantity has well known recurrences, summation formulas, and asymptotic behavior [2].

In the next section, we investigate an inductive approach to strategy construction which uses derangements as strategy components. However, derangements as a whole may produce challenges for us later on. Take, for example, the derangement 2143. Say that γ_{r} is generated using S[4] = 2143, then γ_{r} swaps the first two entries in γ_{r−1} as well as the last two entries. But if J_{r} = ∅, then S[4] generates γ_{r+1} as well by performing the same pairwise swaps once more. But this means that I_{r+1} = I_{r−1}, and the game enters an infinite loop where for all s ≥ r, the set I_{s} can never be nonempty. Hence, for simplicity of computation, later on in Section 4 we narrow our scope to include only cyclic permutations as strategy components. A cyclic permutation has a cyclic decomposition consisting of only a single cycle, so each element is cycled through every possible position as the cyclic permutation is repeatedly applied in our game, returning to its initial position only after n turns. This ensures that no such infinite loop is possible, as each entry must cycle through its correct position before returning to its initial incorrect index. There are (n − 1)! cyclic permutations of length n, and they can alternatively be counted by the Stirling numbers of the first kind by setting k = 1 [2].

3 Strategy analysis

Our analysis begins by compiling experimental data using the Maple package linked in the Appendix. We first construct the set of all strategies of length n whose components are derangements (called “deranged strategies”) and separately construct those whose components are cyclic permutations (called “cyclic strategies”.) For each such strategy, we compute the average number of guesses needed to win a game of permutation wordle if the guesser uses that strategy. To do this, for each permutation of length n, we execute a game of permutation wordle, count how many guesses are needed for the game to terminate, and average this count over all n! secret permutations of length n.

Using Maple, we are able to verify Kutin-Smithline’s conjecture for cyclic strategies up to length n = 7 and for deranged strategies up to length n = 5. For larger n, we encounter limitations due to run time and computational memory. We also test cyclic shift’s performance by comparing it to other strategies of the same length constructed by induction (see the next section for details.) For inductively constructed strategies, we are able to verify Kutin-Smithline’s conjecture up to n = 8.

With supporting experimental findings in hand, we turn our attention to a mathematical study of cyclic shift compared to other strategies. In the following section, we define an inductively constructed strategy and examine whether induction can help us verify cyclic shift’s optimality.

3.1 Inductive construction

We pursue an inductive approach. Consider a strategy constructed as follows:

Definition 3. An inductively constructed strategy (or inductive strategy) is a strategy S of length n such that S[i] = CS[i] for each 1 ≤ i ≤ n − 1, but S[n] is an arbitrary cyclic permutation of length n.

Then, to study Kutin-Smithline’s conjecture, we must focus on how S[n] performs before induction takes over. In other words, we are most interested in how a game plays out up until J_{r} ≠ ∅. From Kutin-Smithline’s conjecture, we would expect that (2 3 … n 1) (or (n 1 2 … n − 1), for a left-shifting strategy) perform the “best” in this context. But how can we test this theory?

We quantify the performance of a strategy component S[n] on permutations of length n as follows. For a derangement d ∈ D_{n} acting as the secret permutation, we execute one iteration of our guessing procedure. As usual, our first guess is the trivial permutation (1 2 … n). From there, generate another guess using S[n] and count the number of correct positions, i.e., |J_{2}|. Averaging this quantity across all derangements d, we produce a measurement of the performance of a strategy component S[n]. Note that we use derangements for this measurement so that we guarantee that J_{1} = ∅ after guessing the trivial permutation, thus assuring that S[n] is triggered to produce a new permutation on [n]. If J_{1} ≠ ∅, then induction kicks in immediately for a permutation of length less than n.

Surprisingly, all possible (deranged) choices for S[n] have the same average performance across secret permutations in D_{n} under this framework. Even more interestingly, the average number of correct indices after one guess for a strategy component of length n is \frac{n}{n−1}. We present the following proposition:

Proposition 4. For a deranged strategy component S[n], the average size of J_{2} across all games of permutation wordle whose secret permutation is a derangement of length n is \frac{n}{n−1}.

Proof. To study a game using strategy S with a given derangement S[n], first note that if γ_{1} = (1 2 … n), then γ_{2} = (S[n])^{−1}, assuming that the secret permutation is a derangement. Then J_{2} = {i ∈ [n] | d[i] = (S[n])^{−1}[i]}, so the set of correct positions is precisely the set of positions where the derangement and the inverse of our strategy component agree. Since the inverse of a derangement is also a derangement, and inverses are in one-to-one correspondence, we proceed using a derangement δ = (S[n])^{−1}. Note that |J_{2}| = |{i ∈ [n] | δ(i) = d(i)}| for a secret permutation d, so the average size of |J_{2}| across all d ∈ D_{n} is \frac{1}{|D_{n}|} ∑_{d∈D_{n}} |\{i ∈ [n] | δ(i) = d(i)\}|. To prove the claim that this average is equal to \frac{n}{n−1}, we show the following equivalent statement:

∑_{d∈D_{n}} |\{i | d(i) = δ(i)\}| = \frac{n}{n − 1} · |D_{n}|.  (1)

On the left-hand side of Eq. 1, we may equivalently fix a position in our fixed derangement δ and count the number of other derangements which share that position, then sum across all possible positions. Then we have ∑_{d∈D_{n}} |{i | d(i) = δ(i)}| = ∑_{i=1}^{n} |{d ∈ D_{n} | d(i) = δ(i)}|. From there, we may calculate |{d ∈ D_{n} | d(i) = δ(i)}| by utilizing the recurrence for |D_{n}|. Recall that |D_{n}| = (n−1)(|D_{n−1}|+|D_{n−2}|), wherein we construct a derangement of length n by choosing a position for the element n and then deranging the remaining elements. There are n − 1 possible locations for n. Say that d[n] = j. Then if d[j] = n as well, the number of ways to derange the remaining elements is |D_{n−2}|. If d[j] ≠ n, then the number of ways to derange the elements of [n] \ {n} is |D_{n−1}| since while j’s fixed position is occupied, we prohibit d[j] = n.

In our case for each fixed entry i, we know its location in δ so we do not need to choose one of n − 1 possible locations for the element i. Then it suffices to calculate the number of ways to derange the remaining elements, which is |D_{n−1}| + |D_{n−2}|. Thus, we have the following:

∑_{d∈D_{n}} |{i | d(i) = δ(i)}| = ∑_{i=1}^{n} |{d ∈ D_{n} | d(i) = δ(i)}|

= ∑_{i=1}^{n}(|D_{n−1}| + |D_{n−2}|)

= n · (|D_{n−1}| + |D_{n−2}|)

= n · (\frac{|D_{n}|}{n − 1}) .

We also note that the left-hand side sum in Eq. 1 produces the sequence 0, 2, 3, 12, 55, 318, 2163, 16952 for 1 ≤ n ≤ 8 (otherwise known as \underline{A284843} on the OEIS [4], or the Secret Permutation S[n] := 2341 S[n] := 2143

γ_{2} = 4123  γ_{2} = 2143
2143  {2, 4}  {1, 2, 3, 4}
2341  ∅  {1, 3}
2413  {4}  {1, 4}
3142  {2}  {2, 3}
3412  ∅  ∅
3421  {3}  ∅
4123  {1, 2, 3, 4}  {2, 4}
4312  {1}  ∅
4321  {1, 3}  ∅

Table 1: J_{2} for two cyclic S[n].

number of permutations with no circular 2-successions). But interestingly, the distribution of correct indices across all derangements is not equivalent for all strategy components S[n]. Consider the examples in Table 1. For two possible strategy components S[n] where n = 4, the corresponding set J_{2} is given for each secret permutation d ∈ D_{4}. For convenience, γ_{2} = (S[n])^{−1} is also listed beneath each example S[n]. Observe that for CS, there is one derangement with 4 common positions, two with 2, and four with 1. Meanwhile for the cycle 2143, there is one derangement with 4 common positions and four with 2, but none with only 1.

In this section, we proved that all S[n] ∈ D_{n} have the same average performance. Then in an inductive approach, simply trading S[n] for another derangement and examining its highest level performance will not do. We must instead examine how the performance later on in the game is effected by this exchange of strategy components. In the next section, we proceed by studying the number of permutations which can be guessed in r guesses for a given number r.

4 Generating functions

Kutin-Smithline [1] discusses generating functions in the context of multi-colored permutation wordle. We do not study this extension in our paper; however, we borrow their generating function framework to analyze strategies of standard permutation wordle. For a specific strategy S of length n, we construct a generating function f_{S}(x) according to its performance. A term a_{r}x^{r} of f_{S}(x) communicates that there are a_{r} many permutations of length n that the strategy S guesses in exactly r guesses. In the rest of this section, we are particularly concerned with a_{r} = [x^{r}]f_{S}(x) for r = 1, 2, and 3.

A statistical generating function, whose coefficients capture the enumeration or statistics of a desired quantity, is an alteration of the better known probability generating function (pgf). In a pgf, the coefficient a_{r} represents the probability that a random variable takes on the value r. In this sense, the coefficients of the statistical generating function, when divided by the size of the sample space, are equal to the coefficients of the probability generating function for the same problem. Probability generating functions are useful because they simplify statistical calculations. For example, the mean may be calculated by taking the derivative and setting x = 1, and the variance is calculated by summing the first and second derivatives evaluated at x = 1. Then in the statistical generating function, we can obtain the average number of guesses in a game of permutation wordle by taking the derivative, setting x = 1, and dividing by the sample size of n!. This would allow us to study Conjecture 1, so calculating a strategy’s statistical generating function is of great interest to us. For more information about generating functions, pgfs, and their uses, see Concrete Mathematics [2].

4.1 Linear and quadratic coefficients

Importantly, in Section 3 of Kutin-Smithline [1], the authors prove that the coefficients of the generating function for cyclic shift are the Eulerian numbers. In other words, [x^{k}]f_{CS}(x) = A(n, k −1) if CS is the cyclic shifting strategy of length n. Since cyclic shift’s performance is determined by the number of excedances in the secret permutation, the coefficients of f_{CS}(x) are nice and have this clean recurrence. Determining the coefficients of f_{S}(x) for a more general strategy S of length n is more daunting, but we do have the following:

Theorem 5. For all strategies of length n, we have [x^{1}]f_{S}(x) = 1 and [x^{2}]f_{S}(x) = A(n, 1).

Proof. Recall that without loss of generality, γ_{1} is always the trivial permutation of length n. Then the only permutation which can be guessed in only one guess is the trivial permutation, and this property is independent of the strategy used. Thus [x^{1}]f_{S}(x) always equals 1.

To count the number of strategies guessable in two guesses by a set strategy S, we count the number of permutations that can be generated in two guesses by the strategy S. We start with the trivial permutation for γ_{1}. Some subset of indices I_{1} are incorrect after the first guess, then the strategy component S[|I_{1}|] is used to generate the second guess. Since S[|I_{1}|] is deterministic, counting the number of permutations which can be generated in two guesses is equivalent to counting the number of possible subsets which may form I_{1}.

Note that if γ_{1} is not the secret permutation, then 2 ≤ |I_{1}| ≤ n. We cannot have zero incorrect entries, otherwise we fall into the previous case, and it is impossible to have only one incorrect entry in a permutation. Let |I_{1}| = k, then there are \binom{n}{k} possible subsets which can form I_{1}. Allowing k to range from 2 to n, we have that the number of permutations which may be generated in two guesses is ∑_{k=2}^{n} \binom{n}{k} = A(n, 1). As a sequence in n, we obtain the Eulerian numbers, which are described in entry \underline{A000295} of the OEIS [4].

Let us consider a special case of this argument: analysis of the inductively constructed strategies from Section 3.1. For an inductive strategy, a permutation with at least one correct entry in γ_{1} uses a “lower level” strategy component to generate γ_{2}, meaning that γ_{2} is generated by the component S[m] for m < n. However, these components are all cyclic shifting for an inductive strategy, and hence they are all identical for every inductive strategy.

Then every permutation which can be guessed in two guesses by some inductive strategy, and which is not a derangement, can be guessed by all inductive strategies in two guesses. For a fixed inductive strategy, there is one other permutation which can be guessed in two guesses, and this is the permutation γ_{2} = (S[n])^{−1} produced when J_{1} = ∅. Then for every strategy, (S[n])^{−1} is guessable in two turns, but each other permutation guessable in two must have had at least one common entry with γ_{1}, and so it is guessable by all inductively constructed strategies. This, however, is where the similarities between cyclic shift and an arbitrary inductive strategy stop.

4.2 Cubic coefficients

As we discussed before in the start of Section 3, experimental data does suggest that certain strategies are more efficient or optimal than others, and this difference is reflected in the later coefficients of the generating function. To analyze these coefficients, we must first do some bookkeeping. In order for a game to end in at least three guesses, we must work with permutations of length 3 or greater, so our strategy must also have length at least 3. There are only two cyclic strategies of length 3: rightward cyclic shift and leftward cyclic shift. In both cases [x^{3}]f_{S}(x) = A(3, 2) = 1, so this case is well understood. Henceforth, we concern ourselves only with strategies of length 4 or more. Consider the following conjecture:

Conjecture 6. Let f_{CS}(x) be the generating function for the cyclic shift strategy of length n. For all strategy lengths n, we have that [x^{3}]f_{CS}(x) > [x^{3}]f_{S}(x) for all deranged strategies S.

Experimental evidence suggests that this conjecture is true for all deranged strategies of length up to 6. We prove a slightly weaker version of the conjecture above which considers only cyclic strategies, but it is noteworthy that this result may be extended to deranged strategies, as well. We prove the claim for cyclic strategies using induction, or by considering only the inductively constructed strategies described in Section 3.1. Consider the following modification of the previous statement:

Theorem 7. Let f_{CS}(x) be the generating function for the cyclic shift strategy of length n. For all strategy lengths n, we have that [x^{3}](f_{CS}(x)) > [x^{3}](f_{S}(x)) for all inductive strategies S.

But before digging into the details of proving this theorem, we present some examples for the reader. In Table 2, we compile the generating functions of several inductive strategies of lengths 4 and 5, each identified by their final component S[n].

Observe, as proven in Section 4.1, that [x^{1}]f_{S}(x) = 1 and [x^{2}]f_{S}(x) = A(n, 1) for each strategy. The first strategy listed in each table segment is CS, and (of course) among these examples the cubic coefficient is maximum for CS of length 4 and 5.

To count the permutations which are guessed by a strategy S of length n in exactly three guesses as we did before for one and two guesses, we break our game into cases according to

S[n]  f_{S}(x)
n = 4 [2, 3, 4, 1] x^{4} + 11x^{3} + 11x^{2} + x
[2, 4, 1, 3] 3x^{4} + 9x^{3} + 11x^{2} + x
[2, 4, 1, 3] 3x^{4} + 9x^{3} + 11x^{2} + x
[4, 1, 2, 3] 5x^{4} + 7x^{3} + 11x^{2} + x
n = 5 [2, 3, 4, 5, 1] x^{5} + 26x^{4} + 66x^{3} + 26x^{2} + x
[4, 3, 1, 5, 2] 8x^{5} + 25x^{4} + 60x^{3} + 26x^{2} + x
[3, 5, 2, 1, 4] x^{6} + 10x^{5} + 27x^{4} + 55x^{3} + 26x^{2} + x
[5, 1, 2, 3, 4] 5x^{6} + 11x^{5} + 26x^{4} + 51x^{3} + 26x^{2} + x

Table 2: Inductive strategy generating function examples.

which of the three guesses first resulted in a correct entry. After this point, induction takes over and we use the standard right shifting strategy to finish the game.

Definition 8. For a game using strategy S with the secret permutation π, let ρ_{S}(π) := inf{i | J_{i} ≠ ∅}. Colloquially, ρ_{S}(π) is the natural number corresponding to the first turn where the player guesses at least one permutation entry correctly.

Of course then [x^{3}]f_{S}(x) = ∑_{i=1}^{3} |{π | ρ_{S}(π) = i}|. We consider each case individually. But before we proceed, we must include a derangement-counting lemma. Derangements which are guessed by CS in three guesses have two excedances, according to Kutin-Smithline [1]. Such derangements are counted by \underline{A046739} in the OEIS [4], but we include the following argument since the approach used in the proof is also utilized later on in this paper.

Lemma 9. There are 2^{n} − (2n + 1) derangements of length n which can be guessed by CS in three guesses.

Proof. Consider a derangement of [n] which can be guessed by CS in exactly three guesses. For a secret permutation which is a derangement, we know that J_{1} is empty and that γ_{2} = (n 1 2 … n − 1) after right shifting. Of course γ_{3} is deterministic since our game ends after three guesses, so it suffices to count the number of legal possibilities for J_{2}. For a permutation of length n, there are 2^{n} possible sets J_{2}. We know that we cannot have |J_{2}| = n or the game ends with only two guesses, and |J_{2}| = n − 1 is impossible, so we subtract these possibilities to obtain 2^{n} − \binom{n}{n} − \binom{n}{n−1} = 2^{n} − (n + 1).

Additionally, we cannot have that I_{2} = {i, (i mod n) + 1}. For simplicity of notation, we refer to (i mod n) + 1 as i + 1, with the understanding that i = n results in i + 1 = 1. If I_{2} = {i, i + 1}, we note that i, i + 1 ∉ J_{1}, so i and i + 1 are both shifted right in γ_{2}. This means that γ_{2}[i + 1] = i. And since I_{2} = {i, i + 1}, then γ_{3} is generated by swapping γ_{2}[i] and γ_{2}[i + 1]. This places i = γ_{3}[i], but this cannot possibly be the correct permutation since i ∉ J_{1}. Hence this scenario produces a contradiction. Observe that this contradiction is only produced when I_{2} consists of two adjacent entries, otherwise entry i in position i + 1 would be swapped into some other position which is not i, which is legal.

There are \binom{n}{1} ways to choose i in this scenario, so there are an additional n possible sets which cannot form J_{2}. This leaves us with 2^{n} − (2n + 1) possible derangements with two excedances.

With this lemma in hand, we begin our study of ρ_{S}(π) with the following theorem:

Theorem 10. For an inductive strategy S of length n ≥ 4, we have

|\{π | ρ_{S}(π) = 1\}| = 1 − 2^{n+1} + 3^{n} + \frac{n^{2}}{2} + \frac{5n}{2} − n · 2^{n}.

Proof. For ρ_{S}(π) = 1, we have that J_{1} ≠ ∅, meaning that the first guess (the trivial permutation) has at least one common entry with the secret permutation π. Note that 1 ≤ |J_{1}| ≤ n − 3. If |J_{1}| = n, then the game ends in one guess, and it is not possible for |J_{1}| = n − 1 since there cannot be only one entry in an incorrect location. If |J_{1}| = n − 2, then γ_{2} swaps the two incorrect entries from γ_{1}, which must produce the correct permutation, hence the game ends in two guesses. Then for the game to end in exactly three guesses, we must have that |J_{1}| ≤ n − 3.

Say that |J_{1}| = k. Then S[n − k], which is of course cyclic shifting, must guess the remaining n − k positions in two more guesses. The sub-permutation of π consisting of n − k remaining elements is a derangement of those elements since none of those entries were correct in γ_{1}. Then it suffices to count the number of derangements of length n − k which can be guessed by CS in 3 guesses total. We know from Kutin-Smithline [1] that this is equivalent to the number of derangements of length n − k with two excedances. Using Lemma 9, we conclude that there are 2^{n−k} − (2(n − k) + 1) such derangements.

So, we have that there are \binom{n}{k} ways to choose J_{1}, and 2^{n−k} − (2(n − k) + 1) permutations of the remaining elements which can be guessed in the remaining two guesses. Summing over all possible values of k, we have that there are ∑_{k=1}^{n−3} \binom{n}{k} (2^{n−k} − (2n − 2k + 1)) permutations with ρ_{S}(π) = 1. With the aid of Maple, we also obtain the following closed form for this sum of binomials, which has been added to the OEIS [4] as entry \underline{A385588}.

1 − 2^{n+1} + 3^{n} + \frac{n^{2}}{2} + \frac{5n}{2} − n · 2^{n}.

Observe that Theorem 10 and the subsequent proof are entirely independent of the strategy component S[n] since the n-th strategy component is never utilized. This case relies purely on induction, meaning that new guesses are generated only by using the lower index, cyclic shifting components of the strategy. We temporarily skip the case ρ_{S}(π) = 2 and first consider the case of ρ_{S}(π) = 3 as it behaves similarly to this previous case. Note that the following claim is actually stronger than we need it to be since it covers all cyclic strategies, not just the subset of inductive ones.

Theorem 11. For a cyclic strategy S of length n ≥ 4, we have |{π | ρ_{S}(π) = 3}| = 1.

Proof. For ρ_{S}(π) = 3, we have that J_{1}, J_{2} = ∅, but J_{3} ≠ ∅. For the game to end at guess three, we need J_{3} = [n]. If J_{1}, J_{2} = ∅, then γ_{3} consists of the trivial permutation of length n with S[n] applied twice, and since J_{3} = [n], we have that π = γ_{3}. This is the only possible outcome. There also cannot be an i ∈ [n] such that γ_{1}[i] or γ_{2}[i] = γ_{3}[i] since the component S[n] must be a cyclic permutation of length at least 3, and thus it cannot have 1- or 2-cycles in it which would allow an element i to return to the same location after S[n] is applied twice. Thus this is a legal game with only one possible permutation.

In the previous two cases, the number of permutations was independent of the strategy component S[n]. But we know experimentally (in Table 2, for instance) that [x^{3}]f_{S}(x) is not a constant for all of our inductive strategies, and since [x^{3}]f_{S}(x) = ∑_{i=1}^{3} |{π | ρ_{S}(π) = i}|, we conclude that the adjudicator is the so far unexamined set {π | ρ_{S}(π) = 2}. First, consider the following:

Theorem 12. For the cyclic shifting strategy CS of length n ≥ 4, we have |{π | ρ_{CS}(π) = 2}| = 2^{n} − 2n − 2.

Proof. In this case where ρ_{S}(π) = 2, we have J_{1} = ∅, so we obtain γ_{2} = (n 1 2 … n − 1) after a single right shift. As before, note that |J_{2}| ≠ n, n − 1, and that γ_{3} is deterministic since the game ends in three guesses, so it suffices to count the number of legal possible sets J_{2}. Once again, notice that there cannot be two adjacent entries i, i + 1 ∈ I_{2} (simplifying our notation as in Lemma 9). If such an i existed, then γ_{2}[i + 1] = i, and by the same argument as before the entry i is right shifted back around so that γ_{3}[i] = i. But again, this produces a contradiction since we assumed that the game ended in three guesses.

Every other subset of [n] represents a legal possibility for J_{2}, so we count them as follows. There are 2^{n} total possible subsets, but we cannot have subsets of size 0 or of size n or n − 1. Then we have 2^{n} − \binom{n}{0} − \binom{n}{n} − \binom{n}{n−1} = 2^{n} − 1 − 1 − n = 2^{n} − n − 2. We must also subtract off subsets of size two which consist of adjacent pairs \{i, i + 1\}. There are \binom{n}{1} = n choices for i, so we subtract these off as well and obtain the desired result: 2^{n}−n−2−n = 2^{n}−2n−2.

To demonstrate the optimality of CS compared to each other inductive strategy S in games lasting for only three guesses, we aimed to show that [x^{3}]f_{S}(x) < [x^{3}]f_{CS}(x). But with the previous two calculations in hand, we actually have that |{π | ρ_{S}(π) = i}| are fixed when i ∈ {1, 3} for every inductive strategy of length n. It then suffices to show that |{π | ρ_{S}(π) = 2}| < 2^{n} − 2n − 2 for an arbitrary S.

Theorem 13. For an inductively constructed strategy S of length n ≥ 4, we have that |{π | ρ_{S}(π) = 2}| < 2^{n} − 2n − 2.

Proof. As before, we want to count the number of possible J_{2} subsets. Note, of course, that the number of these subsets cannot exceed 2^{n} − n − 2 since regardless of the strategy used, J_{2} must have a size at least 1 and no bigger than n − 2 for ρ_{S}(π) = 2 in a game ending after three guesses. Then we must count the number of outlying subsets which are also subtracted.

Recall that since J_{1} = ∅, we have γ_{2} = (S[n])^{−1}, and since S[n] is a cyclic permutation (and hence a derangement), the inverse is also a derangement. In the case of standard cyclic shift studied before, the game would not end after three guesses if J_{2} = {i, (i mod n) + 1} since entry i would cycle back around to position i in γ_{3}. Now, let i be in position j of γ_{2}, noting that i ≠ j since γ_{2} is a derangement. Similarly, let k be the position of entry j in γ_{2}. Then if J_{2} = {j, k}, then entry j is shifted back to position j in γ_{3} when cyclic shift takes over, which produces a contradiction as before since the game cannot end in three guesses.

This is also true for all supersets of {j, k} which contains only indices between j and k, as the entry j still circles back around to index j. For example, if j = 2 and k = 5, then the sets {2, 3, 5} and {2, 4, 5} are also illegal since entry 2 in position 5 will right shift back to position 2. (This was not the case for standard cyclic shift since j = i + 1 and thus for entry i to cycle back to position i, the subset J_{2} had to have size exactly 2.) Clearly for every choice of j (of which there are n total), there is at least one set subtracted, so we have at most 2^{n} − 2n − 2 legal sets J_{2}. However, there must be at least one choice of j such that k ≠ j + 1, and hence there are sets containing {j, k} and elements between j and k which must also be subtracted. If there were no such j, then γ_{2}[j + 1] = j for all j ∈ [n], and this would make S[n] = (2 3 … n 1), which is a contradiction to S ≠ CS. Hence, we must eliminate at least one more illegal subset J_{2}, and thus we have a total number of legal sets J_{2} which is strictly less than 2^{n} − 2n − 2. So for an inductive strategy S where S[n] ≠ (2 3 … n 1), we have that |{π | ρ_{S}(π) = 2}| < 2^{n} − 2n − 2, as desired.

Thus, each inductive strategy has fewer permutations which can be guessed in three guesses (such that the first correct entry is obtained on guess number two) than standard cyclic shift does. Since we proved that |{π | ρ_{S}(π) = 2}| < |{π | ρ_{CS}(π) = 2}|, we also get that [x^{3}]f_{S}(x) < [x^{3}]f_{CS}(x), meaning that cyclic shift performs optimally for games lasting only three guesses when compared to other inductively constructed strategies.

4.3 Worst cubic coefficients

In the same context as the previous section, the inductive strategy whose performance is least optimal is the strategy with S[n] = (n 1 2 … n − 1), i.e., which left shifts for a permutation of length n, but then inductively right shifts for all smaller sub-permutations. We refer to this strategy as CSL. Notice that Table 2 includes the generating functions for CSL of lengths 4 and 5 in the last rows of each subsection, respectively. In fact, we can use Maple to experimentally generate the cubic coefficients for CSL of lengths 3 through 8 as follows: 1, 7, 51, 263, 1100, 4093. While the cubic coefficients for CS were equal to A(n, 2), this sequence does not have as neat of a closed form definition. But we can still calculate [x^{3}]f_{CSL}(x) by considering the same three cases from the previous section, and we do so in this section.

At first glance, we do notice that for n ≥ 4, each of these cubic coefficients is strictly smaller than A(n, 2). This indicates that there are strictly more permutations which CS can guess in exactly three guesses than CSL can. After comparing with the cubic coefficients of all other inductive strategies, we descry the following:

Theorem 14. For all strategy lengths n ≥ 4, we have that [x^{3}]f_{CSL}(x) < [x^{3}]f_{S}(x) for all inductive strategies S.

Note, as before, that this claim is equivalent to the statement that |{π | ρ_{CSL}(π) = 2}| < |{π | ρ_{S}(π) = 2}| for every inductive strategy S. Then we first count the permutations on the left hand side of our inequality as follows:

Theorem 15. For the inductive strategy CSL of length n ≥ 4, we have |{π | ρ_{CSL}(π) = 2}| = L_{n} − n − 1, where L_{n} is the n-th Lucas number.

Proof. As before, it suffices to count the number of legal possible sets J_{2}. Notice that there still cannot be two adjacent entries i, i + 1 ∈ I_{2} (letting i + 1 stand in for (i mod n) + 1, as usual.) If such an i existed, then γ_{2}[i] = i + 1 after left shifting, and since i, i + 1 ∈ I_{2}, the entry i+1 in position i is right shifted back to position i+1 in γ_{3}. But γ_{3}[i+1] = i+1 produces a contradiction since we assumed that the game ended in three guesses and i + 1 ∉ J_{1} since J_{1} = ∅.

Then we may count legal subsets J_{2} with size at least 1 and at most n − 2 by instead counting sets I_{2} with size at least 2 and at most n − 1 which contain no pairs of adjacent elements. These are counted by \underline{A023548} in the OEIS [4], which describes convolutions of the natural numbers with Fibonacci numbers. From this listing, we see that the number of such sets from a permutation of length n is L_{n} − n − 1, where L_{n} is the n-th Lucas number.

With this count in hand, we now aim to show that |{π | ρ_{S}(π) = 2}| > |{π | ρ_{CSL}(π) = 2}| by considering the number of legal sets J_{2}. We use a similar strategy to that employed in Theorem 13.

Theorem 16. For an inductive strategy S of length n ≥ 4, we have |{π | ρ_{S}(π) = 2}| > |{π | ρ_{CSL}(π) = 2}|.

Proof. Consider an arbitrary inductive strategy S and a game of permutation wordle with the secret permutation π ending in three guesses but such that ρ_{S}(π) = 2. Then γ_{2} = (S[n])^{−1}, as we have seen before. From γ_{2}, construct a new permutation p as follows. Let p[1] = 1. Then let p[2] = k_{1} where γ_{2}[k_{1}] = 1. Next, let p[3] = k_{2} where γ_{2}[k_{2}] = k_{1}. Repeat up to j = k_{n−2}, at which point all elements of [n] appear in p. Since S[n] is a cyclic permutation, so is (S[n])^{−1} = γ_{2}, and thus p is a valid, cyclic permutation of length n. More simply, throughout this paper we have defined the permutations used in strategy components using the bottom line of two-line notation. Now, p is the same permutation as γ_{2}, but written in cycle notation.

Now recall that in Theorem 13, we observed that for an inductive strategy S, we cannot have I_{2} = {j, k} such that γ_{2}[j] = i and γ_{2}[k] = j. So, to count legal subsets I_{2}, we must count subsets that do not contain {j, k}. This is equivalent to counting subsets of p which do not contain adjacent elements since each adjacent pair is precisely a duo {j, k} where γ_{2}[k] = j. Using the same argument from Theorem 15 to count such subsets, we have at least L_{n} − n − 1 possible sets I_{2}. Thus |{π | ρ_{S}(π) = 2}| ≥ L_{n} − n − 1.

But we have actually undercounted, here. Before, in Theorem 15 when counting legal J_{2}’s for CSL, all supersets of {i, i + 1} produced a contradiction and thus could not be a legal I_{2} set. In Theorem 13, we noted that for a generic strategy S, we need only eliminate supersets of {j, k} which also contain elements l such that j < l < k. In other words, a set {j, k, m} where k < m < j (modulo n) is a totally acceptable candidate set for I_{2} since the entry j is still right shifted back to position j, which was previously occupied by the element k, when γ_{3} is generated.

In CSL, note that k = j − 1 for all j ∈ [n]. Hence, there are no possible m such that k < m < j. Then for every inductive strategy S which is not CSL, there must be at least one j such that its corresponding k ≠ j − 1. Such a j has at least one possible m, and for each possible m there is at least one set {j, k, m} which is a legal I_{2}, and hence represents a permutation π such that ρ_{S}(π) = 2. Then for an arbitrary inductive strategy S, we have |{π | ρ_{S}(π) = 2}| ≥ (L_{n} − n − 1) + 1, or |{π | ρ_{S}(π) = 2}| > L_{n} − n − 1. Thus |{π | ρ_{S}(π) = 2}| > |{π | ρ_{CSL}(π) = 2}|, as desired.

Since |{π | ρ_{S}(π) = 2}| > |{π | ρ_{CSL}(π) = 2}| and we know that |{π | ρ_{S}(π) = 1}| and |{π | ρ_{S}(π) = 3}| are equal for all inductive strategies S, we conclude that [x^{3}]f_{CSL}(x) < [x^{3}]f_{S}(x). This proves Theorem 14. And, as promised, we may now use the fact that [x^{3}]f_{CSL}(x) = ∑_{i=1}^{3} |{π | ρ_{CSL}(π) = i}| to calculate [x^{3}]f_{CSL}(x). Adding together the results of Theorems 10, 11, and 16, we have

[x^{3}]f_{CSL}(x) = 1 + (1 − 2^{n+1} + 3^{n} + \frac{n^{2}}{2} + \frac{5n}{2} − n · 2^{n}) + (L_{n} − n − 1) .

For 3 ≤ n ≤ 8, we can use this equation to replicate the results produced by Maple at the beginning of Section 4.3.

5 Conclusion and future work

Thus far, we have proven Kutin-Smithline’s conjecture for games terminating in exactly three guesses. In Section 4, we used the coefficients of a strategy’s generating function to show inductively that CS is optimal for a game terminating in exactly three guesses, showing that CS is able to guess the maximum number of permutations in exactly three guesses. It is possible that the techniques in this paper could be extended to games terminating in four or more guesses, however the work in this paper surrounding cubic coefficients was motivated by experimental observations which do not extend to coefficients of higher order terms in our generating functions. So, it may be that a more nuanced approach is required to analyze and compare those coefficients.

Even so, the results in this paper concern a specific case of the work originally conducted by Kutin and Smithline. We narrowed our focus to consider games terminating in one, two or three guesses, and we also made several assumptions and simplifications when defining what constitutes a “strategy.” Our strategies consisted primarily of cyclic permutations, so expanding this to derangements, or even to general permutations, will likely change our findings. We also required that a strategy component S[n] was fixed within a strategy S, meaning that there was no allowance for a guesser to modify their strategy midway through, perhaps after several failed guesses resulting in I_{r} = ∅. So there is still a large amount of work to be done investigating cyclic shift’s performance and determining whether it truly is optimal in a game of permutation wordle, and not just in a game with the limitations and assumptions employed in our paper.

6 Appendix

The majority of the findings in this paper are supported by a Maple package, which can be

found at https://aurorahiveley.github.io/wordle.txt. This package includes exam-

ples as well as a handful of procedures which verify (experimentally) each of the theorems in this paper. Bugs should be reported to the author at aurora.hiveley@rutgers.edu.

7 Acknowledgments

The author thanks her advisor Dr. Doron Zeilberger for the introduction to the problem and feedback on earlier drafts.

References

[1] S. Kutin and L. Smithline, Permutation wordle, arxiv preprint arXiv:2408.00903

   [math.CO], 2024. Available at https://arxiv.org/abs/2408.00903.

[2] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edition, Addison-Wesley, 1994.

[3] R. Li and S. Zhu, Playing Mastermind with Wordle-like feedback. Amer. Math. Monthly, 131 (2024), 390–399.

[4] N. J. A. Sloane and The OEIS Foundation Inc., The On-Line Encyclopedia of Integer

   Sequences, https://oeis.org, 2025.

[5] R. Stanley. Guessing a permutation in a way analogous to Wordle. MathOverflow, 2025,

   https://mathoverflow.net/q/497111 (version: 2025-07-02).

2020 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: permutation wordle, statistical generating function, derangement, cyclic permutation.

(Concerned with sequences \underline{A000295}, \underline{A023548}, \underline{A046739}, \underline{A284843}, and \underline{A385588}.)

Received September 17 2025; revised version received February 17 2026; March 1 2026; March 9 2026. Published in Journal of Integer Sequences, March 9 2026.

Return to Journal of Integer Sequences home page.