# Counting the number of a specific type of permutation

In the theory of cumulants of vector-valued random variables, the following types of formulas appear: $$\theta^i \theta^{jk} [3] = \theta^i \theta^{jk} + \theta^j \theta^{ik} + \theta^k \theta^{ij}$$ 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

-

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.

-
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
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} *)


-
+1 There's quite a bit I can learn from your approach. – DavidC Mar 13 '13 at 2:40
thank you for the vote @David. – kglr 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.

-
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. – DavidC Mar 13 '13 at 2:37