Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

In the theory of cumulants of vector-valued random variables, the following types of formulas appear: \begin{equation} \theta^i \theta^{jk} [3] = \theta^i \theta^{jk} + \theta^j \theta^{ik} + \theta^k \theta^{ij} \end{equation} This is supposed to mean as follows: sum over all possible permutations (in this case 3) of the indices. The indices of a given theta are symmetric and need not be counted twice.

Another example would be $\theta^i \theta^j \theta^{kl}$ [6]. In this case there is a total of 6 terms:

$i\;|\;j\;|\;kl$

$i\;|\;k\;|\;jl$

$i\;|\;l\;|\;jk$

$j\;|\;k\;|\;il$

$j\;|\;l\;|\;ik$

$k\;|\;l\;|\;ij$

Going to even higher order, $\theta^{ij} \theta^{kl} \theta^{mn}$ [15] has 15 terms, and etc.

I am unaware of any closed expressions for the number of terms. Thus, I was trying to use Mathematica to numerically compute all terms involved in a given permutation.

However, so far I have been entirely unsuccessful. Any ideas?

Here are some (failed) attempts, made with 4 indices and the combination $\theta^i \theta^j \theta^{kl}$. This lists all permutations of four terms.

perm = Permutations[{a, b, c, d}]

I can use Mr. Wizard's dynP to partition in the size I want. For instance,

dynP[{a,b,c,d},{1,1,2}]
{{a},{b},{c,d}}

So, an alternative, would be to do this for all members of perm, and then eliminate duplicates according to the above-specified criteria. This, however, I failed to do.

I appreciate any help in advance.

Best regards,

Gabriel

share|improve this question

3 Answers 3

up vote 10 down vote accepted

If I'm not mistaken, we can do this in closed form. Suppose we have $n$ indices split up into $n_1$ one-index variables, $n_2$ two-index variables, etc. Then the total number of distinct permutations is just $N=\dfrac{n!}{\prod\limits_{i}n_i!(i!)^{n_i}}$.

This accounts for the $n_i!$ permutations of $i$-index variables and the $i!$ permutations of each of their indices.

This can be implemented pretty simply. With x being a list of the $n_i$ (including zeros),

numDistinct[x_] :=
  Plus@@(x.Range@Length@x)!/Product[x[[i]]! (i!)^x[[i]], {i, Length@x}]

This yields numDistinct[{2, 1}] = 6 and numDistinct[{0, 3}] = 15, as it should.

share|improve this answer
    
This works great and also agrees with Carraher's answer. Thank you very much. Do you have any references in which I could learn more from these types of calculations. I think I will soon encounter more complicated combinations. Thank you very much for the help. –  Gabriel Landi Mar 13 '13 at 2:23
    
Glad to help. I don't know of any references offhand; I've really just picked up what little combinatorics knowledge I have from various stat mech problems. Maybe others can chime in with more info. –  Eric Thewalt Mar 13 '13 at 3:05
2  
Richard Stanley, Enumerative Combinatorics. –  whuber Mar 13 '13 at 4:45
ClearAll[numtermsF];
numtermsF = Coefficient[MomentConvert[Moment[Total@{##}], Cumulant], 
  Times @@ (Cumulant[#[[1]]]^(#[[2]]) & /@ Tally[{##}])] &
numtermsF @@ # & /@ {{1, 1, 2}, {2, 2, 2}, {1, 1, 3}, {3, 1, 2}, {1, 2, 3}}
(* {6, 15, 10, 60, 60} *)

see also: Documentation Center MomentConvert>Applications>Combinatorial Uses of MomentConvert

share|improve this answer
    
+1 There's quite a bit I can learn from your approach. –  David Carraher Mar 13 '13 at 2:40
    
thank you for the vote @David. –  kguler Mar 13 '13 at 3:02
    
Yes, there's a lot of depth to this! "Tally" in particular is practically built for this problem, and I hadn't seen it before. –  Eric Thewalt Mar 13 '13 at 3:08

Sorry for this seat-of-the-pants approach. I was too rushed to figure out the underlying combinatorics. f produces all the permutations (including equivalent cases), sorts them at Level 2, and then delete duplicates. dynP is by Mr.Wizard.

dynP[l_,p_]:=MapThread[l[[#;;#2]]&,{{0}~Join~Most@#+1,#}&@Accumulate@p]

f[p_]:=DeleteDuplicates[Map[Sort(dynP[#,p]&/@
  Permutations[FromCharacterCode/@Range[97,96+Plus@@p]]),2]]//Length


f /@ {{1, 1, 3}, {2, 2, 2}, {1, 2, 3}, {3, 1, 2}}

{10, 15, 60, 60}

Remove //Length from function to see the permutations.

share|improve this answer
    
This is precisely the type of Sort syntax that I was trying to figure out. Thanks for the help. –  Gabriel Landi Mar 13 '13 at 2:30
    
Glad to hear that. Sort seemed to be the key to avoiding equivalent permutations (equivalent in a special sense here). There are likely to be more elegant or efficient ways of doing it. –  David Carraher Mar 13 '13 at 2:37

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.