How many way to partition a set of n number into k subsets (empty subset is allowed)

Question

I am working on finding the upper bound iterations of k-means algorithm. Many research show that the trivial upper bound is $O(k^n)$ since it can be shown that no clustering occurs twice during the course of the algorithm. So the upper bound can be calculated by counting the number of way to partition n points into k subset (empty subset is allowed). How to calculate this number? Why does it equal $k^n$?

For example:

Partition {1,2,3} into 2 subsets (n = 3, and k = 2)

1. Subset 1: {1,2,3} - Subset 2: {}
2. Subset 1: {1} - Subset 2: {2, 3}
3. Subset 1: {2} - Subset 2: {1, 3}
4. Subset 1: {3} - Subset 2: {1, 2}

Then multiply by 2! (swapping between subsets)

The total is 8 = $2^3$

Answer 1

It equals $k^n$ because each number can be put into any of the $k$ subsets. You have $n$ numbers, so you multiply $n\ k$s together. It would be harder if you didn't care about the order of the subsets because you might have more than one empty set.