Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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