Function Repository Resource:

ShuffleProductExpand

Expand products of symbolic word objects into their canonical shuffle sum

Contributed by: Jayanta Phadikar

ResourceFunction["ShuffleProductExpand"][expr]

expands products of symbolic word objects (e.g. w[{…}], Inactive[List][…] etc.) in expr into their canonical shuffle sum.

Details

A shuffle sum of two words is the sum of all the words formed by interlacing them according to riffle shuffle permutation.

ResourceFunction["ShuffleProductExpand"] algebraically converts products of symbolic word objects (e.g. w[{…}], Inactive[List][…] etc.) into the sum of all shuffles of their index words.

ShuffleProductExpand distributes over Plus, pulls out scalar factors, and acts independently on each multiplicative factor.

Shuffle counts grow combinatorially; limits on weight/depth/terms prevent blow-ups.

Words must appear under a symbolic head (e.g. w[{…}]). Bare lists such as {1,2} are not treated as words (to avoid list arithmetic e.g. {1,2}*{2,3}⟶{2,6}).

Handles products of any number of word objects; w[a]w[b]w[c]… expands to the full multi-shuffle (associative and multilinear).

Interprets w[u]^n (with integer n >=0) as the n-fold shuffle power of u i.e. the shuffle of u with itself n times.

Examples

Basic Examples (1)

Shuffle product of two words with an inert head:

In[1]:=

Out[1]=

Scope (5)

Expand the 3-way shuffle of words:

In[2]:=

Out[2]=

Expand a 2 × 3 shuffle:

In[3]:=

Out[3]=

An empty word is treated as an identity:

In[4]:=

Out[4]=

ShuffleProductExpand distributes an expression linearly before expanding:

In[5]:=

Out[5]=

Shuffle independently by head and multiply the results:

In[6]:=

Out[6]=

Applications (9)

Cellular Automaton (5)

Use ShuffleProductExpand to enumerate all t-step LR-paths. Shuffles of Parity by displacement gives the exact Rule-90 row, matching CellularAutomaton[90].

Define a function that enumerates all length-t words over {L, R} via shuffle powers, with an explicit empty word only when t==0:

In[7]:=

$allLRWords[t_Integer?NonNegative] := Module[{sum}, If[t == 0, Return[{{}}]]; sum = Total@Table[ ResourceFunction["ShuffleProductExpand"][ h[{L}]^i*h[{R}]^(t - i)], {i, 0, t}]; Cases[sum, h[w_List] :> w, \[Infinity]] ];$

Define a displacement functional that maps a word to its net shift:

In[8]:=

Build the length-(2t+1) parity row by counting words at each displacement k and taking Mod 2:

In[9]:=

$coeffParityRow[t_Integer?NonNegative] := Module[{w = allLRWords[t], k = Range[-t, t]}, Lookup[Mod[Counts[disp /@ w], 2], k, 0]];$

Construct a centered single-1 initial condition of length 2t+1 for comparison with CellularAutomaton:

In[10]:=

$CARow[rule_Integer, t_Integer?NonNegative] := Module[{init}, init = Normal@SparseArray[{t + 1 -> 1}, 2 t + 1]; CellularAutomaton[rule, init, t][[t + 1]]];$

Verify that every shuffle-predicted row equals the CellularAutomaton row over a range of times:

In[11]:=

Out[11]=

Game Theory (4)

Model a race i.e., a competition to act first by order, by encoding A and B moves as words (A has m moves, B has n). Use ShuffleProductExpand to enumerate all possible orderings, then compute the preemption probability by counting schedules that start with {A,A} (A wins the race).

Enumerate all interleavings of m A's and n B's via shuffle powers:

In[12]:=

$interleavings[m_Integer?NonNegative, n_Integer?NonNegative] := Module[{sum}, If[m == 0 && n == 0, Return[{{}}]]; sum = ResourceFunction["ShuffleProductExpand"][h[{A}]^m*h[{B}]^n]; Cases[List @@ sum, h[w_List] :> w, \[Infinity]]];$

Declare the preemption predicate - the schedule starts with (A,A):

In[13]:=

$twoABeforeAnyB[w_List] := MatchQ[w, {A, A, ___}];$

Compute the preemption probability for a concrete case m=3,n=8:

In[14]:=

Out[15]=

Confirm with the closed form:

In[16]:=

Out[16]=

Properties and Relations (10)

Shuffle product expansion is commutative:

In[17]:=

Out[17]=

Shuffle product expansion is associative:

In[18]:=

Out[18]=

Upon shuffling words of lengths m and n, every term has length m+n:

In[19]:=

Out[19]=

In[20]:=

$Union[Length /@ Cases[res, h[w_List] :> w, \[Infinity]]]$

Out[20]=

Relate term count to binomial/multinomial coefficients - for two words of lengths m and n, the shuffle product contains Binomial[m+n,m] (same as Binomial[m+n,n] or Multinomial[m,n]) terms:

In[21]:=

Out[21]=

In[22]:=

Out[22]=

In[23]:=

Out[23]=

Similarly for more factors - for words of lengths n₁, n₂, …, n_k, the shuffle product contains Multinomial[n₁,n₂,…,n_k] terms:

In[24]:=

Out[24]=

In[25]:=

Out[25]=

Expanding an already shuffled sum changes nothing (indempotence):

In[26]:=

Out[26]=

In[27]:=

Out[27]=

Reverse both inputs to reverse every shuffled word (reversal symmetry):

In[28]:=

$Sort[Reverse /@ Cases[ResourceFunction["ShuffleProductExpand"][h[{a, b}] h[{c, d}]], h[w_List] :> w]]$

Out[28]=

In[29]:=

$Sort[Cases[ ResourceFunction["ShuffleProductExpand"][ h[Reverse@{a, b}] h[Reverse@{c, d}]], h[w_List] :> w]]$

Out[29]=

In[30]:=

Out[30]=

Reproduce shuffles of two words via multiset permutations. Generate A/B slot "skeletons" with permutations of a multiset and fill them left-to-right:

In[31]:=

$shuffleByPermutations[u_List, v_List] := Module[{m = Length@u, n = Length@v, skels, fill}, skels = Permutations@ Join[ConstantArray["A", m], ConstantArray["B", n]]; fill[s_List] := Module[{i = 1, j = 1, res = {}}, Scan[If[# === "A", AppendTo[res, u[[i++]]], AppendTo[res, v[[j++]]]] &, s]; res]; fill /@ skels ]$

The filled lists match result from ShuffleProductExpand:

In[32]:=

Out[32]=

Reproduce two-word shuffles via Tuples: generate all length-m+n A/B slot sequences with exactly m A's, then fill them left → right from u/v:

In[33]:=

$shuffleByTuples[u_List, v_List] := Module[{m = Length@u, n = Length@v, skels, fill}, skels = Select[Tuples[{"A", "B"}, m + n], Count[#, "A"] == m &]; fill[s_List] := Module[{i = 1, j = 1, res = {}}, Scan[If[# === "A", AppendTo[res, u[[i++]]], AppendTo[res, v[[j++]]]] &, s]; res]; fill /@ skels ];$

In[34]:=

Out[34]=

Reproduce shuffles via choosing positions. Choose positions for the first word with Subsets[Range[m+n],{m}] and stream-fill A/B letters across the slots:

In[35]:=

$shuffleBySubsets[u_List, v_List] := Module[{m = Length@u, n = Length@v, posSets}, posSets = Subsets[Range[m + n], {m}]; Map[Function[pos, Module[{iu = 1, iv = 1}, Table[If[MemberQ[pos, k], u[[iu++]], v[[iv++]]], {k, 1, m + n}]]], posSets] ];$