# Entangled permutations of a multiset

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$.

-
For the record: the horrible-looking formula I found is based on the Moebius inversion of polynomial coefficients with respect to the poset of set partition of $\{1,\dots,m\}$ . –  Gejza Jenča Jul 23 '11 at 12:35
Does anything nice happen to the horrible-looking formula if $a_1 = a_2 = \ldots = a_m$? –  mhum Jul 26 '11 at 6:49
@mhum: First impression is that nothing really nice happens, but I have to think about it more. –  Gejza Jenča Jul 27 '11 at 18:17
Why do you "feel that this problem should have a nice answer" in the sense of a nice formula? -- I would probably rather be looking for an efficient algorithm. Note also that a "nice" formula, even if it exists, might not be quite efficient to evaluate. –  Stefan Kohl Feb 10 at 13:57
@StefanKohl I am hoping for a nice formula, because the number arises in a natural context. My colleague and I have managed to prove that the number of linear extensions $E(P)$ of a connected finite poset $P$ is equal to the Euler characteristic of some space $X(P)$. If $P$ is not connected, the Euler characteristic of $X(P)$ is strictly smaller than $E(P)$, but we can show that the connection between $E(P)$ and $\chi(X(P))$ can be expressed in terms of the number of entangled permutations of a multiset $M$ as in my question, $a_i$ are the sizes of connected blocks of $P$. –  Gejza Jenča Feb 10 at 19:30
show 1 more comment

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.

-
In your sum, you count the untangled permutation 112223333 twice, once for $X=\{1\}$ and second time for $X=\{1,2\}$. –  Gejza Jenča Jul 23 '11 at 12:28
Yes, you are right. I am another victim of overcounting. I'll leave the answer up for a little while if others find it useful, but will delete it if I can't repair it. –  Tony Huynh Jul 23 '11 at 13:28
@Tony Hyunh: Please, do not delete the answer. The mistake is typical -- everyone I asked (3 people) made exactly this mistake at first before realizing that the problem is a bit more complicated. So I think it is better to keep the answer here, but to mark it as wrong. –  Gejza Jenča Jul 23 '11 at 14:11
@Gejza Jenča: OK, I left the answer as is, but with a warning at the top. I think one can repair the formula using inclusion/exclusion, but this is probably equivalent to the ugly formula you derived via Moebius inversion. –  Tony Huynh Jul 24 '11 at 10:07