Special Products of Transpositions

[Edit. Significantly expanded to add examples and (I hope) clarification. Feel free to skim by reading the gray boxes.]

A colleague asked me for insights on a collection of special permutations, but I'm afraid the topic falls a little outside of my realm of expertise. The permutations in question can be described thusly:

Permutations (on $n$ symbols) that are a product of $n$ transpositions with the cycle notation form $$(1,s_1)(2,s_2)(3,s_3)\cdots(n,s_n) \qquad\qquad (\star)$$ That is, the $i$th "factor" of the permutation exchanges the item at position $i$ with the item at position $s_i$, where we assume $i\neq s_i$.

Note that $(\star)$ is a "recipe" for a permutation, not the permutation's decomposition into orbits. Note also that there are $(n-1)^n$ recipes, but only $n!$ permutations of $n$ symbols. Multiple recipes give rise to the same permutation.

For instance, for $n=3$, we have $2^3=8$ recipes $(1a)(2b)(3c)$, resulting in just $3$ permutations: \begin{align} (12)(23)(31)&: 123 \to 213 \to 231 \to 132 \\ (12)(21)(32)&: 123 \to 213 \to 123 \to 132 \\ (13)(21)(31)&: 123 \to 321 \to 231 \to 132 \\ \\ (13)(23)(31)&: 123 \to 321 \to 312 \to 213 \\ (12)(23)(32)&: 123 \to 213 \to 231 \to 213 \\ (13)(21)(32)&: 123 \to 321 \to 231 \to 213 \\ \\ (12)(21)(31)&: 123 \to 213 \to 123 \to 321 \\ (13)(23)(32)&: 123 \to 321 \to 312 \to 321 \end{align}

More briefly: $$132\;(\times 3) \qquad 213\;(\times 3) \qquad 321\;(\times 2)$$ where the "$(\times m)$" gives the "multiplicity" of the permutation (ie, the number of recipes $(\star)$ that result in it).

For $n=4$, we have $3^4=81$ recipes, yielding $12$ permutations:

\begin{align} &1234\;(\times 3)\qquad 1342\;(\times 9)\qquad 1423\;(\times 7)\\ &2143\;(\times 11)\quad\;\; 2314\;(\times 9)\qquad 2431\;(\times 6)\\ &3124\;(\times 7)\qquad 3241\;(\times 6)\qquad 3412\;(\times 7)\\ &4132\;(\times 5)\qquad 4213\;(\times 5) \qquad 4321\;(\times 6) \end{align}

For $n=5$, we have $4^5 = 1024$ recipes, yielding $60$ permutations:

\begin{align} &12354\;(\times 9) \quad \phantom{0}12435\;(\times 9) \quad \phantom{0}12543\;(\times 8) \quad \phantom{0}13245\;(\times 9) \quad \phantom{0}13452\;(\times 28) \quad 13524\;(\times 21) \\ &14253\;(\times 21) \quad 14325\;(\times 8) \quad \phantom{0}14532\;(\times 20) \quad 15234\;(\times 15) \quad 15342\;(\times 7) \quad \phantom{0}15423\;(\times 20) \\ &21345\;(\times 9) \quad \phantom{0}21453\;(\times 37) \quad 21534\;(\times 29) \quad 23154\;(\times 37) \quad 23415\;(\times 28) \quad 23541\;(\times 19) \\ &24135\;(\times 21) \quad 24351\;(\times 18) \quad 24513\;(\times 25) \quad 25143\;(\times 16) \quad 25314\;(\times 14) \quad 25431\;(\times 20) \\ &31254\;(\times 29) \quad 31425\;(\times 21) \quad 31542\;(\times 15) \quad 32145\;(\times 8) \quad \phantom{0}32451\;(\times 19) \quad 32514\;(\times 15) \\ &34152\;(\times 25) \quad 34215\;(\times 20) \quad 34521\;(\times 18) \quad 35124\;(\times 21) \quad 35241\;(\times 14) \quad 35412\;(\times 20) \\ &41235\;(\times 15) \quad 41352\;(\times 14) \quad 41523\;(\times 21) \quad 42153\;(\times 16) \quad 42315\;(\times 7) \quad \phantom{0}42531\;(\times 14) \\ &43125\;(\times 20) \quad 43251\;(\times 20) \quad 43512\;(\times 20) \quad 45132\;(\times 15) \quad 45213\;(\times 15) \quad 45321\;(\times 12) \\ &51243\;(\times 12) \quad 51324\;(\times 10) \quad 51432\;(\times 17) \quad 52134\;(\times 12) \quad 52341\;(\times 6) \quad \phantom{0}52413\;(\times 15) \\ &53142\;(\times 15) \quad 53214\;(\times 17) \quad 53421\;(\times 18) \quad 54123\;(\times 14) \quad 54231\;(\times 14) \quad 54312\;(\times 12) \end{align}

And so forth.

In the above, we get $n!/2$ permutations (which would necessarily mean: all the members of $S_n$ that match $n$'s parity), but it's not immediately obvious to me that this is always the case. (Certainly, we always get $n$'s-parity permutations, but do we always get all of them?) I'll point out that my colleague and I are primarily interested in even $n$ ---so that we're working within (if not with the entirety of) the alternating group, $A_n$--- but considering all $n$ may help reveal patterns.

Now, my colleague and I are interested in counting the number of these special permutations "with multiplicity" that move items $i$, $j$, $k$ into positions $1$, $2$, $3$ (where $n \gg 3$). For instance,

Among the permutations of the form $(\star)$ on the (English) alphabet, how many result in $26$-letter strings beginning with a $3$-letter word of my choosing, say, "cat$\cdots$" or "dog$\cdots$"?

(More generally, how many permutations yield strings starting with a $4$-, $5$-, or $m$-letter word of my choosing?)

In terms of the permutations given above, I could ask questions like

How many special permutations (with multiplicity) ...

• ... of $\phantom{45}123$ begin with $\phantom{495}2$? Answer: $\phantom{00}3$
• ... of $\phantom{45}123$ begin with $\phantom{49}31$? Answer: $\phantom{00}0$*
• ... of $\phantom{5}1234$ begin with $\phantom{459}3$? Answer: $\phantom{0}20$
• ... of $\phantom{5}1234$ begin with $\phantom{59}42$? Answer: $\phantom{00}5$
• ... of $\phantom{5}1234$ begin with $\phantom{9}123$? Answer: $\phantom{00}3$
• ... of $12345$ begin with $\phantom{999}3$? Answer: $217$
• ... of $12345$ begin with $\phantom{99}15$? Answer: $\phantom{4}42$
• ... of $12345$ begin with $\phantom{9}321$? Answer: $\phantom{42}8$
• ... of $12345$ begin with $2431$? Answer: $\phantom{42}0$*

*The first $(n-2)$ entries in the permutation determine the last $2$ (this is clear from parity), so it's possible to specify length-$(n-1)$ beginning strings that never occur. (Not that that really matters to us. In our investigation, we want to specify beginning strings of length far less than $n$.)

If all we wanted was to know the number of ways item $i$ can move into position $j$, then a fairly straightforward analysis of products of permutation matrices would do. Here are resulting tabulations for $n=3,4,5,6$, where the $(i,j)$th element counts the number of permutations (with multiplicity) that move item $i$ into position $j$. $$\left( \begin{array}{ccc} 3 & 3 & 2 \\ 3 & 2 & 3 \\ 2 & 3 & 3 \\ \end{array} \right)\qquad \left( \begin{array}{cccc} 19 & 26 & 20 & 16 \\ 23 & 14 & 24 & 20 \\ 21 & 20 & 14 & 26 \\ 18 & 21 & 23 & 19 \\ \end{array} \right)\qquad \left( \begin{array}{ccccc} 175 & 273 & 225 & 189 & 162 \\ 229 & 138 & 252 & 216 & 189 \\ 220 & 201 & 126 & 252 & 225 \\ 208 & 204 & 201 & 138 & 273 \\ 192 & 208 & 220 & 229 & 175 \\ \end{array} \right)$$ $$\left( \begin{array}{cccccc} 2101 & 3524 & 3024 & 2624 & 2304 & 2048 \\ 2869 & 1732 & 3280 & 2880 & 2560 & 2304 \\ 2805 & 2564 & 1552 & 3200 & 2880 & 2624 \\ 2725 & 2580 & 2464 & 1552 & 3280 & 3024 \\ 2000 & 2100 & 2180 & 2244 & 1476 & 2500 \\ 2500 & 2625 & 2725 & 2805 & 2869 & 2101 \\ \end{array} \right)$$

One observes that the matrices are symmetric across the secondary diagonal. Less obviously, they indicate that there are $(n-1)^{n-1}-(n-2)^{n-1}$ ways for item $1$ to stay put, and $2(n-2)^{n-1}$ ways for item $1$ to move to position $n$. General formulas for other entries are somewhat trickier to express.

These independent tallies are one thing, but I'm at a loss for how to count "compound" circumstances, such as (in the simplest case)

$$\text{"# of ways ( item i moves to position 1 ) AND ( item j moves to position 2 )"}$$

Of course, "brute force" enumeration ---generating all the permutations, and counting the ones we want--- already becomes computationally intractable once $n$ nears $10$. Our suspicion is that there's effectively no good solution here. That said, it seems possible that the specific nature of the recipe $(\star)$ provides enough structure to facilitate such enumeration, perhaps through clever recursion or exploitation of some aspect of the symmetric group, $S_n$ (or, maybe, the alternating group, $A_n$). So, before my colleague shelves this particular puzzle, I thought I'd ask for pointers here. It would even be helpful to know

Have these "special permutations" been studied in the literature?

If it's true that the recipes $(\star)$ always give us half of the permutations in $S_n$, then this problem can be broken into two parts

• Find the $n$'s-parity members of $S_n$ that begin with a specified sequence.
• Count the number of ways a member of $S_n$ can be decomposed into form $(\star)$.
• The question apears trivial on first reading, so I must be misinterpreting it. Firstly, the product of n transpositions, as you write it, seems to decompose the permutation into n 2-cycles, which is a permutation of 2n (not of n). Secondly, of all 26! permutations of the letters of the alphabet, we can fix k letters into a pre-defined position, and all (n-k) others can be freely permuted, giving (n-k)! permutations. Could you please give a few brute-force counts upto say n=7 and a more elaborate example on n=3 or 4 to illustrate the selection of permutations you seek to count. – Wouter M. Apr 26 '14 at 16:22
• @WouterM.: The transposition formula doesn't represent the permutation's decomposition into orbits. (It's possible, for instance, that the first factors are $(1,2)(2,1)$, which reduce to $(1)(2)$. So, $(1,2)$ isn't an orbit.) The transpositions simply give the "recipe" for a special permutation: Move the item in position $1$, then move the item in position $2$, then move the item in position $3$, ..., then move the item in position $n$. There are, therefore, $(n−1)^n$ recipes, which must map to some subset of all $n!$ permutations. I'll update my question to be more clear and to give examples. – Blue Apr 26 '14 at 21:37
• Does oeis.org/A001710 help any? – Wouter M. Apr 27 '14 at 12:53
• The 'multiplicity' of the resulting permutations equals the class size of the partitions encoding their cycle structure: for n=5 I get 20 x (32) + 30 x (41) + 10 x (2111) – Wouter M. Apr 27 '14 at 13:55
• The partitions mentioned above are exactly those having an even number of parts. – Wouter M. Apr 27 '14 at 15:18

I don't see an analytical solution for this. Since you write that brute force enumeration becomes computationally intractable once $n$ nears $10$, I'm assuming that you're interested in a computational solution. This can easily be done by keeping track, in each of the $n$ steps, of the number of ways the items of interest could have been permuted so far. Here's Java code that does this. I tested it against some of your results.
The numbers of recipes for permutations of the alphabet that result in strings starting with "cat" or "dog" are $171114214080872315853377269465088$ and $226062155864710562305001318569480$, respectively. (Note that, since the code keeps track of the positions of the letters of interest, not the letters at the positions of interest, you need to use e.g. "cat" for the from variable and "abc" for the to variable.)