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.


You must log in to answer this question.

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