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.


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

  • $\begingroup$ 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\}$ . $\endgroup$ Jul 23, 2011 at 12:35
  • 1
    $\begingroup$ Does anything nice happen to the horrible-looking formula if $a_1 = a_2 = \ldots = a_m$? $\endgroup$
    – mhum
    Jul 26, 2011 at 6:49
  • $\begingroup$ @mhum: First impression is that nothing really nice happens, but I have to think about it more. $\endgroup$ Jul 27, 2011 at 18:17
  • $\begingroup$ 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. $\endgroup$
    – Stefan Kohl
    Feb 10, 2014 at 13:57
  • $\begingroup$ @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$. $\endgroup$ Feb 10, 2014 at 19:30

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

  • $\begingroup$ In your sum, you count the untangled permutation 112223333 twice, once for $X=\{1\}$ and second time for $X=\{1,2\}$. $\endgroup$ Jul 23, 2011 at 12:28
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Jul 23, 2011 at 13:28
  • $\begingroup$ @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. $\endgroup$ Jul 23, 2011 at 14:11
  • $\begingroup$ @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. $\endgroup$
    – Tony Huynh
    Jul 24, 2011 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.