What is the correct terminology for Permutation & Combination formulae that allow repeating elements.

Question

Let me explain by example.

Q: Given four possible values, {1,2,3,4}, how many 2 value permutations are there ?

A: 16.

(1,1), (1,2), (1,3), (1,4)
(2,1), (2,2), (2,3), (2,4)
(3,1), (3,2), (3,3), (3,4)
(4,1), (4,2), (4,3), (4,4)

However, running 4P2 through Wolfram Alpha gives me an answer of 12.

Q: Similarly, given four possible values, {1,2,3,4}, how many 2 value combinations are there?

A: 10.

(1,1), (1,2), (1,3), (1,4)
       (2,2), (2,3), (2,4)
              (3,3), (3,4)
                     (4,4)

However, running 4C2 through Wolfram Alpha gives me an answer of 6.

I'm assuming because the implementations of nCm and nPm removed the element from the source set so it can't be chosen again. (similar to lottery balls picked from a drum).

Is there other terminology/formulae for the equivalent where it's possible to return each value. The real life situation would be dice-rolls, where all 6 options are still available on each subsequent roll of the dice.

Answer 1

In "permutations", the order matters. In "combinations", the order does not matter.

The basic rules of counting are the Product Rule and the Sum Rule. See here, for example.

1. Permutations with repetitions allowed:

   If you have $n$ objects, and you want to count how many permutations of length $m$ there are: there are $n$ possibilities for the first term, $n$ for the second term, $n$ for the third term, etc. So the total number is $n^m$.

2. Permutations without repetitions allowed:

   If you have $n$ objects, and you want to count permutations of length $m$ with no repetitions (sometimes called "no replacement"): there are $n$ possibilities for the first term, $n-1$ for the second (you've used up one), $n-2$ for the third, etc. So the total number is $$P^n_m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}.$$

3. Combinations without repetitions allowed:

   In combinations we don't care about the order. If you select $m$ objects from $n$ possibilities and they are all distinct, then there are $P^m_m = n!$ ways of ordering them. So if you count permutations instead, you will count each distinct choice of elements exactly $m!$ times. Therefore, $\binom{n}{m}$ (also denoted $nCm$, both read "$n$ choose $m$") is given by: $$\binom{n}{m} = \frac{1}{m!}P^n_m = \frac{n!}{m!(n-m)!}.$$

4. Combinations with repetitions allowed:

   You have $n$ objects, and you want to select $m$ of them, allowing repetitions. To simplify things, let us assume our $n$ objects are precisely the numbers $1$, $2,\ldots,n$. Given a selection of $m$ objects with possible repetitions, $a_1,\ldots,a_m$, order them in ascending order, $a_1\leq a_2\leq\cdots\leq a_m$, and think of them as an $m$-tuple: $(a_1,a_2,\ldots,a_m)$. We want to count the number of such tuples with entries between $1$ and $n$, repetitions allowed.

   Let us associate to each such tuple an $m$-tuple with no repetitions and with entries between $1$ and $n+m-1$ as follows: given $(a_1,a_2,\ldots,a_m)$, with $1\leq a_1\leq a_2\leq\cdots\leq a_m\leq n$, we associate the tuple $(a_1,a_2+1,a_3+2,\ldots,a_m+m-1)$. Note that $$1\leq a_1\lt a_2+1\lt\cdots \lt a_m+m-1\leq n+m-1.$$ Conversely, given a tuple $(b_1,b_2,\ldots,b_m)$ with $1\leq b_1\lt b_2\lt\cdots\lt b_m\leq n+m-1$, we have $b_i\geq n+i$; so this tuple "comes from" the tuple $(b_1,b_2-1,b_3-2,\ldots,b_m-m+1)$, which is a nondecreasing tuple with values between $1$ and $n$; i.e., it is one of our original $(a_1,\ldots,a_n)$s.

   That means that counting the nondecreasing tuples $(a_1,\ldots,a_m)$ with $1\leq a_1\leq\cdots\leq a_m\leq n$ is equivalent to counting the number of strictly increasing tuples $(b_1,b_2,\ldots,b_m)$ with $1\leq b_1\lt b_2\lt\cdots\lt b_m\leq n+m-1$. This is, in turn, equivalent to counting the number of ways of selecting $m$ objects from among $\{1,2,\ldots,n+m-1\}$, with no repetitions allowed. This is just $\binom{n+m-1}{m}$.

Answer 2

Formulae :

$n^k$ : number of permutations with repetition

$\frac{(n+k-1)!}{k! \cdot (n-1)!}$ :number of combinations with repetition

where $n$ is a number of elements of given set .

Answer 3

nPm and nCm give you the number ways to choose two elements (in either case no element can be chosen twice). nPm cares about the order (so $(1,2)\neq(2,1)$), nCm does not. So the answers correclty are 12 and 6. What you want is just an exponential. For n distinct elements (4) forming a sequence of m elements (2), there are $m^n$ possible combinations (16).