[proofplan] We prove the interval formula directly, so the case $[1,n]$ follows by taking the interval to be the whole word. The proof starts from the moment-cumulant formula for free cumulants and groups the noncrossing partitions according to the block containing the left endpoint $a$. For a fixed left-endpoint block, noncrossingness gives a bijection between the remaining blocks and independent noncrossing partitions of the gaps between consecutive elements of that block. Applying the moment-cumulant formula again on each gap turns those independent sums into the interval moments appearing in the product. [/proofplan]

[step:Expand the interval moment by the free moment-cumulant formula] Fix integers $a,b$ with $1\leq a\leq b\leq n$. Let $I:=\{a,a+1,\dots,b\}$, and let $NC(I)$ denote the set of noncrossing partitions of $I$ with respect to the natural order inherited from $\mathbb N$. For a block $V=\{v_1<\cdots<v_m\}\subseteq I$, define its cumulant weight by \begin{align*} K(V):=\kappa_m(x_{v_1},\dots,x_{v_m}). \end{align*} For a partition $\pi\in NC(I)$, define \begin{align*} K(\pi):=\prod_{V\in\pi}K(V). \end{align*} Since the functionals $\kappa_k$ are the free cumulants associated to $\varphi$, the moment-cumulant formula for free cumulants applies to the finite word $x_a,\dots,x_b$ and gives \begin{align*} M[a,b]=\sum_{\pi\in NC(I)}K(\pi). \end{align*} [/step]

[step:Describe the partitions with a fixed left-endpoint block]Let $k\geq 1$ and let $a=i_1<i_2<\cdots<i_k\leq b$. Put $i_{k+1}:=b+1$ and define the gap sets \begin{align*} I_j:=\{i_j+1,i_j+2,\dots,i_{j+1}-1\} \end{align*} for $1\leq j\leq k$. Empty gap sets are allowed. Let $V_0:=\{i_1,\dots,i_k\}$. The noncrossing partitions $\pi\in NC(I)$ whose block containing $a$ is $V_0$ are in bijection with tuples $(\pi_1,\dots,\pi_k)$, where $\pi_j\in NC(I_j)$ and $NC(\varnothing)$ consists of the single empty partition. Indeed, if $\pi\in NC(I)$ has left-endpoint block $V_0$, every block $W\in\pi$ different from $V_0$ lies inside one of the gap sets $I_j$. If not, there are elements $r<s$ in $W$ and some $j$ with $i_j<r<i_{j+1}<s$ after choosing two elements of $W$ separated by an element of $V_0$. Then $i_j<r<i_{j+1}<s$ displays a crossing between the blocks $V_0$ and $W$, contradicting $\pi\in NC(I)$. Therefore restriction to the gaps defines partitions $\pi_j\in NC(I_j)$. Conversely, given $\pi_j\in NC(I_j)$ for $1\leq j\leq k$, the collection consisting of $V_0$ together with all blocks of all $\pi_j$ is a noncrossing partition of $I$. Crossings cannot occur inside a single $I_j$ because $\pi_j$ is noncrossing; they cannot occur between two different gaps because the gaps are disjoint ordered intervals separated by points of $V_0$; and they cannot occur with $V_0$ because each other block is contained between two consecutive elements of $V_0$, or after the last element of $V_0$. These two constructions are inverse to each other.[/step]

[guided]Fix $k\geq 1$ and indices $a=i_1<i_2<\cdots<i_k\leq b$. We want to understand exactly which noncrossing partitions have $\{i_1,\dots,i_k\}$ as the block containing the left endpoint $a$. Define $i_{k+1}:=b+1$ and define the gap sets \begin{align*} I_j:=\{i_j+1,i_j+2,\dots,i_{j+1}-1\} \end{align*} for $1\leq j\leq k$. If $i_{j+1}=i_j+1$, then $I_j=\varnothing$; this is why the theorem needs the convention that empty intervals contribute the factor $1$. Let $V_0:=\{i_1,\dots,i_k\}$. Suppose $\pi\in NC(I)$ and the block of $\pi$ containing $a$ is $V_0$. We claim that every other block of $\pi$ must be contained in a single gap $I_j$. To see this, let $W$ be a block different from $V_0$. If $W$ were not contained in one gap, then two elements of $W$ would lie on opposite sides of some element $i_{j+1}$ of $V_0$. More precisely, for some $j$ there would be $r,s\in W$ with \begin{align*}\ni_j<r<i_{j+1}<s. \end{align*} The four points $i_j,r,i_{j+1},s$ then alternate between the two blocks $V_0$ and $W$. This is exactly a crossing of the two blocks, contradicting the assumption that $\pi$ is noncrossing. Hence each block other than $V_0$ lies in exactly one gap, and restricting $\pi$ to each $I_j$ gives a noncrossing partition $\pi_j\in NC(I_j)$. Conversely, choose arbitrary partitions $\pi_j\in NC(I_j)$ for $1\leq j\leq k$, with the convention that $NC(\varnothing)$ has one empty partition. Form a partition of $I$ by taking the block $V_0$ and adjoining all blocks of all $\pi_j$. This partition is noncrossing. A crossing inside one gap is impossible because $\pi_j$ is noncrossing. A crossing between two different gaps is impossible because the gaps are ordered disjoint intervals. A crossing between $V_0$ and a gap block is impossible because a gap block lies wholly between consecutive elements $i_j$ and $i_{j+1}$, or wholly after $i_k$, so its elements do not alternate with two elements of $V_0$. Thus, for the fixed block $V_0$, choosing a noncrossing partition of the whole interval is exactly the same thing as choosing one independent noncrossing partition in each gap $I_j$.[/guided]

[step:Factor the cumulant weight over the endpoint block and the gaps] For a partition $\pi$ corresponding to a tuple $(\pi_1,\dots,\pi_k)$ under the bijection above, multiplicativity of the partition cumulant weight over blocks gives \begin{align*} K(\pi)=\kappa_k(x_{i_1},\dots,x_{i_k})\prod_{j=1}^{k}K(\pi_j), \end{align*} where the empty partition has weight $1$. Therefore the contribution of all partitions with fixed left-endpoint block $\{i_1,\dots,i_k\}$ is \begin{align*} \kappa_k(x_{i_1},\dots,x_{i_k})\prod_{j=1}^{k}\sum_{\pi_j\in NC(I_j)}K(\pi_j). \end{align*} For each nonempty gap $I_j=\{i_j+1,\dots,i_{j+1}-1\}$, the moment-cumulant formula applied to the interval word $x_{i_j+1},\dots,x_{i_{j+1}-1}$ gives \begin{align*} \sum_{\pi_j\in NC(I_j)}K(\pi_j)=M[i_j+1,i_{j+1}-1]. \end{align*} For an empty gap, the sum over the single empty partition is $1$, and this equals $M[i_j+1,i_{j+1}-1]$ by the stated empty-interval convention. Hence the fixed-block contribution is \begin{align*} \kappa_k(x_{i_1},\dots,x_{i_k})\prod_{j=1}^{k}M[i_j+1,i_{j+1}-1]. \end{align*} [/step]

[step:Sum over all possible left-endpoint blocks] Every partition $\pi\in NC(I)$ has a unique block containing $a$. Writing that block uniquely as $\{a=i_1<i_2<\cdots<i_k\}$, the preceding steps partition the full moment-cumulant sum according to all possible choices of $k$ and $i_2,\dots,i_k$. Therefore \begin{align*} M[a,b]=\sum_{\substack{k\geq 1, \;a=i_1<i_2<\cdots<i_k\leq b}}\kappa_k(x_{i_1},\dots,x_{i_k})\prod_{j=1}^{k}M[i_j+1,i_{j+1}-1], \end{align*} with $i_{k+1}=b+1$. This proves the asserted interval formula. Taking $a=1$ and $b=n$ gives the stated decomposition for the whole word $x_1,\dots,x_n$. [/step]