MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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 2011 at 12:35
Does anything nice happen to the horrible-looking formula if $a_1 = a_2 = \ldots = a_m$? – mhum Jul 26 2011 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 2011 at 18:17

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 2011 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 2011 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 2011 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 2011 at 10:07