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

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.

-
Note: curly brackets are usually used to denote sets; in sets, order and repetition do not matter; that is, most mathematicians will see $\{1,4\}$ and $\{4,1\}$ and $\{1,1,4,4,4,4\}$ as representing the same object. If you want to take into account order, then one usually uses the "ordered tuple notation" which uses parentheses, not curly brackets. –  Arturo Magidin Apr 4 '12 at 16:41
They are called "combinations with repetitions" and "permtuations with repetitions". $\binom{n}{m}$ ($n$ choose $m$) counts the number of $m$-element subsets from a set of $n$ (distinct) elements; as I noted above, this does not take into account repetitions or order. $P^n_m$ (permutations) counts the number of $m$-length strings from an $n$-letter alphabet, without repetition allowed. To allow repetitions you need slightly different formulas. –  Arturo Magidin Apr 4 '12 at 16:43
@ArturoMagidin... mea culpa. Spot the programmer with array notation :-) I'll fix the formatting in the question to use ( & ) –  Eoin Campbell Apr 4 '12 at 16:47
Look also for multiset in Wikipedia. –  André Nicolas Apr 4 '12 at 17:49
If your set of values is S, and you want all n value permutations with repetition, create the cross-product of S for n times. See stackoverflow.com/questions/3099987/… –  Konstantin Weitz Jun 30 at 21:03

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}$.

-
Thank you for this excellent explanation! :) –  Anne Lagang Jan 19 at 1:23

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 .

-
but the second formula is what I'm looking for. Thanks Pedja. –  Eoin Campbell Apr 4 '12 at 16:50
@EoinCampbell "trycatch.me" - excellent name for web site... –  pedja Apr 4 '12 at 17:02
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).