How many ordered sets there are with k elements (with limitation )

162 Views Asked by At

How many ordered sets there are with k elements such that every element is a subset of $[n]$. so that $\{T_1,T_2,T_3, \dots,T_k\} \subseteq [n]^k$ and $T_1 \cap T_2 \cap \dots \cap T_k= \emptyset$ and $T_1 \cup T_2 \cup \dots \cup T_k =[n]$.

$[n]=\{1,2,\dots,n\}$

2

There are 2 best solutions below

0
On

If I understood your question right then this number is exactly the number of all $k$-colorings of the set $[n]$, that is maps from $[n]$ to $[k]$, which is, clearly $k^n$.

0
On

The Stirling numbers $S(n, k)$ count the number of ways to partition $[n]$ into $k$ nonempty subsets. Since the $T_i$ are ordered, for each partition $\{T_1, \cdots, T_k\}$ you can permute these $k$ subsets in $k!$ ways, giving $k!S(n, k)$ ordered partitions. If the $T_i$ are allowed to be empty then you should sum $k!S(n, j)$ for $j = 1, \cdots, k$.