The Twelvefold Way

The "Twelvefold Way" is a name for a categorization of these types of problems, first

coined by Richard Stanley. When you solved combinatorial problems in this chapter, you

probably noticed that in some cases you need the "stones" to be considered distinct; in

others, you need them to be considered identical. Likewise, when we encounter tubs

that are considered identical, we need Stirling numbers of the second kind or partitions.

Stanley$$s Twelvefold Way organizes these ideas into twelve types of problems:

s Stones t Tubs No Restrictions At most $1$ Stone

per Tub

At Least $1$

Stone per Tub

Distinct Distinct ts

Identical Distinct

Distinct Identical

Identical Identical

Question $1$: Complete the chart above, using combinatorial techniques from this chapter.

For some of these twelve problems, you may have to combine techniques, use a

summation, or require piecewise$-$style $"$if$"$ clauses. Feel free to add restrictions such

as s $>=$ t$,$ s t$,$ or s $=$ t when necessary. The first entry has already been entered for

you, using the logic described in the previous section. You$$ll need to explain each

$1$

Math $586$ Project $2$

of the remaining solutions in a similar way, so below your chart you should have

eleven more paragraphs explaining each solution.

Question $2$: You have probably noticed that multinomial coefficients, of the form $($ t

s$1,$s$2,...,$si $),$

do not appear on this "twelvefold way". Are there any other types of problems that

you could make up that do not appear on this chart?

Question $3$: Suppose S and T are finite sets, with $|$S$|=$ s and $|$T$|=$ t$.$ How many possible

functions are there from S $->$ T$?$ How many one$-$to$-$one functions? How many onto

functions? $($The answers to Question $3$ are already in your chart from Question $1.$

You$$ll need to explain how can we go from "stones and tubs" to functions.$)$of the remaining solutions in a similar way, so below your chart you should have

eleven more paragraphs explaining each solution.

Question $2$: You have probably noticed that multinomial coefficients, of the form $(\frac{t}{s_1,s_2,\text{d}\text{o}\text{t}\text{s}\text{,}{s}_i}),$

do not appear on this "twelvefold way". Are there any other types of problems that

you could make up that do not appear on this chart?

Question $3$: Suppose $S$ and $T$ are finite sets, with $|S|=s$ and $|T|=t.$ How many possible

functions are there from $ST?$ How many one$-$to$-$one functions? How many onto

functions? $($The answers to Question $3$ are already in your chart from Question $1.$

You'll need to explain how can we go from "stones and tubs" to functions.$)$