i am new to combinatorics and just encountered stirling numbers of second kind
the book i am using does not provide much info about it except
number of ways of distributing "r" distinct objects into "n" identical boxes such that no box is empty
explain this "identical boxes"
and then it gives the recursive relation
now what i would like to know about stirling number of second type is
1 how to construct the formula for it (the recursive one) preferably using bijection principle and just using "box and objects language"
2 explain the same but now with " set partition language"
3 define and construct the explicit formula for it
(any intresting facts about it like a few tricky question which use the same)
i apologize if someone thinks this questions is too basic or vague but i have no where else to go and ask my doubts as i just completed schooling and i am interested in mathematics and here there is no one who can teach me also
though i am new to this topic i am familiar with
addition principle
multiplication principle
permutation
combination
circular permutation
principle of complementation
stirling number of first kind
so feel free to use them in answering but i would prefer much informal kind of language but if unavoidable use them
Thanks !
Best Answer
When we put distinguishable objects into "identical boxes", it means we put distinguishable objects into distinguishable boxes, but then we want to consider rearranging the boxes to arrive at an equivalent arrangement, and we count the number of equivalence classes. A better way of thinking about it is that we have a set of boxes (not a list), and each box is a nonempty set. So the order of the boxes doesn't matter, and the order of objects within each box doesn't matter. Perhaps an example will help. The number of ways to put $n$ distinguishable objects $1,2,3,\ldots, n$ into $k$ identical boxes when $n = 4$ and $k = 2$ is $7$:
Let's prove the recurrence relation $$ \newcommand{\stir}{\genfrac\{\}{0pt}{}} \stir{n+1}{k} = k \stir{n}{k} + \stir{n}{k-1}. $$ Consider an arrangement of $n+1$ objects $(1,2,3,\ldots,n+1)$ put in $k$ boxes, of the kind counted by $\stir{n+1}{k}$. There are two cases to consider: either object $n+1$ stands in its own box, or it shares its box with some other objects. If it stands in its own box, then we have to distribute the remaining $n$ objects into the remaining $k-1$ boxes, and there are $\stir{n}{k-1}$ ways to do so. If not, then we have to put $n$ remaining objects into $k$ boxes, one of them distinguished from the rest, such that each box is nonempty (the box that contained object $n+1$ has to be nonempty too, as that is the case we are considering). The number of ways to do this is $k \cdot \stir{n}{k}$: first $\stir{n}{k}$ ways to put the $n$ objects into $k$ identical boxes, and then $n$ ways to choose which box to select as the distinguished one, which we will put $n+1$ into. (Note that nonempty is key here: because all boxes are nonempty, despite being indistuishable boxes they are distinguishable once any object is put in them; thus, we cannot put object $n+1$ into two different boxes and end up with the same resulting arrangement.)
In a partition of $1,2,3,\ldots,n+1$ into $k$ sets, there are two possibilities: either $\{k\}$ is an element of the partition, or $\{k\}$ is not an element of the partition. In the forms case, there is a one-to-one, onto map (bijection) from all such partitions of $1,2,3,\ldots,n+1$ into $k$ parts to all partitions of $1,2,3,\ldots,n$ into $k-1$ parts, given by (for $P$ a partition of $\{1,2,3,\ldots,n+1\}$ $$ P \quad\mapsto\quad P \setminus \{\{n+1\}\}. $$ In the latter case, there is a $k$-to-one, onto map from all such partitions of $1,2,3\ldots,n+1$ into $k$ parts to all partitions of $1,2,3, \ldots, n$ into $k$ parts, given by $$ P \quad\mapsto\quad \{x \setminus \{n+1\} \;|\; x \in P\}. $$
Explicit formulas are not always that nice :) You can find a combinatorial answer to building an explicit formula here.