In doing some "research" I came across the following numbers $c(\lambda)$ associated to a partition $\lambda$. I'm sure these are not new numbers and are probably counting some type of Young tableaux, but I can't find any sort of formula (explicit, combinatorial, or otherwise) for them. So,

Question: What are these numbers?

For partitions of $n=1$ and $n=2$ every $c(\lambda)=1$.

For partitions of $n=3$:

  • $c(1,1,1)=1$
  • $c(2,1)=3$
  • $c(3)=1$

For partitions of $n=4$:

  • $c(1,1,1,1)=1$
  • $c(2,1,1)=6$
  • $c(2,2)=3$
  • $c(3,1)=4$
  • $c(4)=1$

For partitions of $n=5$:

  • $c(1,1,1,1,1)=1$
  • $c(2,1,1,1)=10$
  • $c(2,2,1)=15$
  • $c(3,1,1)=10$
  • $c(3,2)=10$
  • $c(4,1)=5$
  • $c(5)=1$

For some context these numbers arise in calculating derivatives of functions of the form $f(x)=\exp(p(x))$ where $p(x)$ is a polynomial: $$ f^{(n)}(x)=f(x)\left(\sum_{\lambda:\, |\lambda|=n}c(\lambda)\prod_{\lambda_i\in\lambda}p^{(\lambda_i)}(x)\right). $$

  • $\begingroup$ How are we supposed to guess how these numbers came about when you just give a bunch of examples? $\endgroup$ Sep 23 '16 at 18:27
  • $\begingroup$ @Tobias: Fair enough; I'll edit the question. $\endgroup$
    – Steve
    Sep 23 '16 at 18:30
  • $\begingroup$ Did you mean to have $c(\lambda) = 1$ for $n=1,2$? $\endgroup$ Sep 23 '16 at 18:38
  • $\begingroup$ Sorry, it should read $c(\lambda)=1$ for $n=1,2$. $\endgroup$
    – Steve
    Sep 23 '16 at 18:39
  • $\begingroup$ This looks quite interesting. It feels like the sort of thing that must have been studied before, but combinatorics is not my area of expertise. $\endgroup$ Sep 23 '16 at 18:41

It's the number of partitions of a set of size $n$ with the given shape.

The multinomial coefficients $\binom{n}{\lambda_1 \, \lambda_2 \, \cdots\, \lambda_m}$ count the number of partitions of a set of size $n$ into labelled subsets of the given sizes $\lambda_i$. But there may be multiple subsets of the same size, so to account for symmetry, divide by $m_k!$, where $m_k$ is the number of subsets of size $k$ (i.e. $m_k = \#\{i : \lambda_i = k\}$).

$$c(\lambda_1, \ldots, \lambda_m) = \binom{n}{\lambda_1 \; \lambda_2 \; \cdots\; \lambda_m} \prod_{k \in \mathbb{N}} \frac{1}{m_k!} = \frac{n!}{\prod_i \lambda_i! \prod_k m_k!}.$$

I don't know of a name for these.

  • $\begingroup$ Fantastic! This is definitely the kind of answer I was hoping for. $\endgroup$
    – Steve
    Sep 23 '16 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.