Entangled permutations of a multiset

Question

Let $M=\{1^{a_1},\dots,m^{a_m}\}$ be a multiset of numbers of cardinality $n$. Call a permutation of $M$ an $M$-word. We say that an $M$-word $w$ is entangled it cannot be written as a concatenation of two nonempty words $u,v$ such that $w=u.v$ and the sets of numbers/characters used in $u$ and $v$ are disjoint.

Examples: let $M=\{1^2,2^3,3^4\}$.

The words 122123333, 112323332 are not entagled:

• 122123333 = 12212.3333
• 112323332 = 11.2323332

The words 123213332, 311322233 are entangled.

Question: given a multiset $M$, how many entangled $M$-words are there?

Of course, it is possible to find a horrible-looking formula. But I feel that this problem should have a nice answer, maybe in a form of a generating function of some sort.

EDIT:

Another way how one can view entangled $M$-words: as lattice paths from $s=(0,\dots,0)$ to $e=(a_1,\dots,a_m)$ that avoid all extremal points of the box except for $s$ and $e$.

Answer 1

Edit. The answer below is incorrect, but I'll leave it here for others to avoid the same pitfall.

Here is a formula that I would rate $\epsilon$ less than horrible. Let $M=\{1^{a_1},\dots,m^{a_m}\}$ be a multiset of numbers of cardinality $n$. The total number of permutations of $M$ is the multinomial coefficient

\[ \binom{n}{a_1, \dots, a_m}:=\frac{n!}{a_1!\cdots a_m!}:=t(M) \]

It is also easy to count the unentangled permutations in this way. For a non-empty subset $X:=\{x_1, \dots, x_k\}$ of $[m]$, define

\[ f_M(X):=\binom{a_{x_1}+ \dots + a_{x_k}}{a_{x_1}, \dots, a_{x_k}}. \]

Note that $f_M(X)$ is the total number of permutations of the numbers in $M$ corresponding to $X$. So, the total number of entangled permutations is

\[ g(M):= t(M) - \sum_{\emptyset \neq X \subset [m]} f_M(X) f_M ( X^C), \] where $X^C$ is the complement of $X$.

For your example with $M=\{1^2,2^3,3^4\}$, we have $g(M)=1234$. That looks like a weird number, but if my math is correct, only 26 of the 1260 permutations are untangled.