definition of stirling numbers

83 Views Asked by At

Here is a definition without partition about Stirling numbers of second kind.

"Let $S(n,k)$ be Stirling numbers of second kind.

$1 \leq k \leq n$, and let $k$ and $n$ be positive integers. Let $h(n, k)$ be the sum of all $\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)$ products that consist of $(n-k)$ factors, so that all these factors are elements of $[k]$ So; $$ h(n, k)=S(n, k) $$ For Example $n=4$, and $k=2$. Then $$ h(4,2)=1 \cdot 1+1 \cdot 2+2 \cdot 2=7=S(4,2) $$ $$ h(4,3)=1+2+3=6=S(4,3) $$

Repetition of factors is allowed, but the factors of each product are to be written in increasing order. Note that the definition of $h(n, k)$ means that $h(n, n)$ is a product with no factors, which we will set to be equal to $1$"

I try to understand this nice definition. Here $h(n, k)$ is the sum of all $\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)$ products that consist of $(n-k)$ factors but how?Can you give a hint about it? Thanks for your comment.

1

There are 1 best solutions below

0
On BEST ANSWER

This is just a description of the generating function, mainly that $$\frac{1}{\displaystyle \prod _{i=1}^k(1-i\cdot x)}=\sum _{n = k}^{\infty}{n\brace k}x^{n-k}.$$ For a proof, consider the following: $\pi$ be a partition in normal form (elements in the blocks are increasing, for example the partition $\{\{2,4\},\{1,5,3\}\}$ is $135/24$ in normal form), say $\pi = B_1/B_2/ \cdots /B_k $ with $m_i=\min (B_i)$ then notice that if you fix the minimal elements, this partition can be any of $1^{m_2-m_1-1}2^{m_3-m_2-1}\cdots k^{n-m_k}$ because for example say that the minimal elements are $1,3,5$ and $n=10$ then $2$ has to go in the block of $1$ so as $3$, but now $4$ can be in the block of $3$ or the block of $1$ so there are $2^{3-1-1}=2$ options, etc. Notice that this process can be reversed, you just count how many times you saw a $1$ and a $2$ etc.

For example in the $1\cdot 2$ case in $h(4,2)$ you have $1^12^1$ so the minimal elements are $1$ and $3$ and the possible permutations are $12/34$ and $124/3$.