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

connectedfinite 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$. $\endgroup$ – Gejza Jenča Feb 10 '14 at 19:301more comment