Let $T_n$ denote the set of $n$-tuples $\left(b_1, \ldots, b_n \right)$ of non-negative integers such that $\sum_{i=1}ib_i=n.$ I am trying to simplify the sum

\begin{align*} \sum_{\underset{b_{j}=k}{\left(b_{i}\right)_{i\le n}\in T_{n}}}\frac{n\left(n-1\right)\cdots\left(n-k-\sum_{i\not=j}b_{i}+2\right)}{\prod_{l\not = j}\left(b_l !\right)}, \end{align*}

where the sum is over all tuples in $T_n$ such that the $j$th entry $b_j$ is equal to $k$.

Is there a way to enumerate the elements of $T_n$ satisfying $b_j=k$? Equivalently, is there a way to enumerate the $n$-tuples $\left(b_1, \ldots, b_j=k, \ldots, b_n\right)$ such that $\sum_{i\not =j} ib_i = n-jk$?

Background: This sum divided by $k!$ equals the number of non-crossing partitions on the set $\lbrace 1, 2, \ldots, n\rbrace$ with exactly $k$ blocks of size $j$.


1 Answer 1


I don't think you can do better than an expression involving the partition function $p(n)$, the number of integer partitions of $n$, which has some complicated exact formulas or (what is actually used) an infinite recurrence due to Euler.

This $(b_1, \ldots, b_n)$ is the "multiplicity representation" of an integer partition of $n$: there are $b_1$ 1s, $b_2$ 2s, etc. Specifying $b_j = k$ means the rest of the partition is a partition of $n-jk$ with no parts $k$. The number of these is $p(n-jk) - p(n-jk-k)$ by the following result.

The number of partitions of $n$ with at least one part $m$ (with $m \le n$) is $p(n-m)$. Therefore the number of partitions of $n$ with no parts $m$ is $p(n) - p(n-m)$.

Regarding your motivating question about numbers and sizes of blocks in noncrossing partitions, you might look at the OEIS entry A303694.


This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .