# Computationally Employ Sum over Ordered Partitions?

I have the following function defined, with two inputs $g$ and $h$:

F[g_, h_] := (((-1)^h)/(2^(2*g - 2*h - 3)))*
Sum[((-1)^k)*
Binomial[2*g - 2, k]*((2*k - 2*g + 2)^(2*h + 2*g - 2))/((2*h + 2*g - 2)!),
{k, 0, g - 2}];


Now, what I want to consider mathematically are ordered partitions of an integer n, i.e. decomposing $n$ as a sum of smaller, positive integers such that order does matter. So $4+1$ and $1+4$ are distinct ordered patitions of $5$.

Let $\mathcal{P}_{n}$ denote the collection of ordered partitions of $n$. I want to think about such partitions in the following way: imagine $n$ objects. There will be $n-1$ slots between them. One can imagine possibly placing dividers in these slots. Therefore, one should think of an ordered partition as

$$\pi=\{ \, \pi_{1} \,| \, \pi_{2} \, | \, \cdots \, |\, \pi_{n-1} \, \}$$

where the $\pi_{i}$ are the number of the $n$ objects (possibly 0) lying in the $i$-th compartment. (I'm sorry for not phrasing this terribly well, but I hope it's clear what I mean). Now, using my function in Mathematica defined above, I would like to carry out the following sum over ordered partitions:

$$\sum_{\pi \in \mathcal{P}_{n}}(-1)^{\epsilon_{\pi}} F[g_{1}, \pi_{1}] \cdot F[g_{2}, \pi_{2}] \cdots F[g_{n-1}, \pi_{n-1}]$$

where the $g_{1}$ are really any integers larger or equal to 2, and $\epsilon_{\pi}$ is even if the number of non-zero components of $\pi$ is even, and odd otherwise.

Can someone please help me get Mathematica to compute these numbers? I'm getting better with numerics, but don't even know where to start when it comes to something as abstract as ordered partitions. Oh yeah, and this functions is every tame, so this sum really should just be a number which is very quick to output.

EDIT: I should clarify what I mean by $\pi$ above. So I imagine a set of $n$ objects, with "labeled" barriers between them. Meaning the $i$-th barrier, if it is present, is necessarily between the $i$ and $i+1$-th object. So for example, I want

$$\{ \cdot \,\ \cdot \,\,| \,\,\cdot \,\, | \,\,\cdot \}$$

to correspond to the partition $\pi = \{2 | 0 | 1 | 1\}$ of $4$; the $0$ is because the second barrier is not present.

• – Anjan Kumar Jun 12 '17 at 1:18
• @AnjanKumar Ah great, thank you. I think I could use that two generate a collection of ordered partitions. However, instead of, for example $\{4\}$ I would want something like $\{0,0,\ldots, 4\}$. Then I would need to figure out how to evaluate a function on this list, and sum. Any tips on how to get the lists to come out the right size? Thanks for your help – Benighted Jun 12 '17 at 2:50
• To get zero padding up-to a certain length, you can use PadLeft[{4}, 5]. To get all of the ordered partitions for a particular n, you may try this function: orderedPartitions[n_] := Flatten[#, 1] &@(Permutations /@ IntegerPartitions[n, {2, n - 1}]);. Does this give you what you want? – Anjan Kumar Jun 12 '17 at 3:16
• @AnjanKumar That helps a ton, thanks :) I made an edit above because I realized what I was asking for requires a sort of different packaging of an ordered partition. Once I figure out that subtlety, your comments will be extremely helpful! – Benighted Jun 12 '17 at 3:51
• I think your question is a duplicate of (21008), and if not it is probably answered in one of (19486), (22397), (43162), (44550), (62956), (86106), (92647). – Mr.Wizard Jun 12 '17 at 7:29