1
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ if anyone starts answering it please notify me by commenting $\endgroup$ – user347954 Jul 6 '16 at 21:39
  • 1
    $\begingroup$ I answered it. $\;\;$. $\endgroup$ – 6005 Jul 6 '16 at 21:45
3
$\begingroup$

explain this "identical boxes"

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$:

Box 1   Box 2
123     4    
124     3
134     2
234     1
124     3
12      34
13      24
14      23

1 how to construct the formula for it (the recursive one) preferably using bijection principle and just using "box and objects language"

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

2 explain the same but now with " set partition language"

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\}. $$

3 define and construct the explicit formula for it

Explicit formulas are not always that nice :) You can find a combinatorial answer to building an explicit formula here.

$\endgroup$
  • $\begingroup$ You're welcome :) $\endgroup$ – 6005 Jul 6 '16 at 21:55

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.