Variations of permutations and Combinations

Question

In my script about combinatorics, until now we have considered and studied the following cases:

1. Permutation without repetition and distinguished objects.
2. Permutation with repetition and distinguished objects.
3. Combination without repetition and distinguished objects.
4. Combination without repetition and distinguished objects.

Then, in the end we consider the case of:

1. Permutations without repetition and indistinguishable objects.

(Here I'd like to point out, that we considered the case when we want to find the nr. of permutations when we use n elements from a set with n elements, in other words all the elements of the set. The formula, which was given but I was also able to derive on my own, is: $\frac{n!}{n_1!n_2!...n_k!}$, where n_1 is the nr. of indistinguishable elements of type one in the set,etc etc. Would the formula be the same if we would want to find the nr. of permutations using r ($r \le n$) elements?)

Would it make sense to consider case 2-4 for when we have indistinguishable elements? How would the formulas change?

Answer 1

The first four cases fit neatly into the twelvefold way problems of enumerating the number of functions $f$ from a size-$n$ set $N$ to a size-$k$ set $X$ with certain properties and up to certain permutations of the sets. Using Wikipedia's table layout and your indexing:

perms	any $f$	injective $f$
none	(2)	(1)
$N$	(4)	(3)

It follows that the indistinguishable variants simply add "permute $X$" and have these formulas:

perms	any $f$	injective $f$
$X$	$\sum_{i=0}^kS(n,i)$	$[n\le k]$
$N,X$	$p_k(n+k)$	$[n\le k]$

Here $[\cdot]$ is the Iverson bracket, $S(n,k)$ is the Stirling number of the second kind and $p_k(n)$ is the number of partitions of $n$ into $k$ non-empty parts.