simple recursion help

[Thorsten Kampe]

* Hung Jung Lu (2004-10-24 04:16 +0100)
> Steven Bethard <steven.bethard at gmail.com> wrote:
>> Does anyone know what this operation is called?  It's not permutations or
>> combinations as I understand them since permutations and combinations do
>> not allow repetition.  I assume there was already a solution for this
>> somewhere, but I didn't know what term to google for.
> ---------------------------------------------------
> aleaxit at yahoo.com (Alex Martelli) wrote:
>> There's been a recent thread where the OP called them 'permutations',
>> somebody commented they're 'variations'.  In that thread you'll find a
>> bazillion solutions, recursive and non, with or without itertools, &c.
> ---------------------------------------------------
> 
> (1) "Variation" is the same as "permutation".

Sorry, no.

> It's matter of semantics. 

It's a matter of definition and the definitions of both don't have
anything in common.

> Some people use the notation V(n, k), some people use the notation
> P(n, k). For people that use the term "variation", the term
> "permutation" is reserved for the special case V(n, n).

That's misleading: the special case of a variation without repetition
of the nth degree is the same as a permutation without repetition of
that set. But the definitions of both are very different.

Variations /with/ repetition are also equal to the "cartesian product"
of the set with itself. But that doesn't mean that "cartesian product"
and variation (with repetition) are the same.

Let me explain:
In combinatorics there are two distinct kinds of "operations":
permutations and combinations[1].

PERMUTATIONS
____________
A permutation is a "bijective mapping on itself" which means that each
permutation has the same length and consists of all elements of the
original set.

Permutations are divided into
* permutations without repetition = n!
* permutations with    repetition = n! / (s1! * ... * sr!)

For instance:
[11, 22, 33, 44, 55, 66, 77] has 7! = 5040 different permutations
(without repetition)

[11, 22, 22, 33, 44, 44, 44] has 7! / (2! * 3!) = 420 different
permutations (with repetition)

COMBINATIONS
____________
A combination is a subset of the original set (also sometimes
described as "ball picking". "Repetition" is sometimes called "putting
back").

Combinations are divided into
* unordered combinations without repetition
* unordered combinations with    repetition
* ordered   combinations without repetition
* ordered   combinations with    repetition

Of course that was too difficult to remember even for a mathematician
so it was decided (about one hundred years ago) that ordered
combinations should now be called "variations" and unordered
combinations should now be called "combinations".

So since then there are:
* combinations without repetition = n! / (k! * (n - k)!)
* combinations with    repetition = (n + k - 1)! / ((n - 1)! * k!)
* variations   without repetition = n! / (n - k)!
* variations   with    repetition = n ** k

And this is where the confusion starts:

* the binomial coefficient "(n over k) = n! / (k! * (n - k)!)" is
sometimes called C(n, k).

* "n! / (n - k)!" is sometimes called P(n, k)

So you can also give the number of different combinations and
variations like this:
* combinations without repetition = C(n, k)
* combinations with    repetition = C(n + k - 1, k)
* variations   without repetition = P(n, k)


Thorsten

[1] For a quick overview have a look at
http://www.eco.uc3m.es/stefan/phd-sum/probl2004.pdf