1
$\begingroup$

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). $$

$\endgroup$
6
  • $\begingroup$ How are we supposed to guess how these numbers came about when you just give a bunch of examples? $\endgroup$ Sep 23, 2016 at 18:27
  • $\begingroup$ @Tobias: Fair enough; I'll edit the question. $\endgroup$
    – Steve
    Sep 23, 2016 at 18:30
  • $\begingroup$ Did you mean to have $c(\lambda) = 1$ for $n=1,2$? $\endgroup$ Sep 23, 2016 at 18:38
  • $\begingroup$ Sorry, it should read $c(\lambda)=1$ for $n=1,2$. $\endgroup$
    – Steve
    Sep 23, 2016 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, 2016 at 18:41

1 Answer 1

2
$\begingroup$

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.

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

You must log in to answer this question.

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