Re: Help with Permutations

In article <3dl1s19rt3nbisanmh2rosr0gvta7eifgv@xxxxxxx>,
quasi@xxxxxxxx writes:
>On Sun, 8 Jan 2006 02:31:26 +0100, "Jonas" <asdf@xxxxxxxxxxxxxxx>
>wrote:
>
>>
>><mareg@xxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
>>news:dpolh3$im4$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>>> In article <1136584344.300707.31850@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
>>> "barliow" <jack.c.barlow@xxxxxxxxx> writes:
>>>>Hi all,
>>>>
>>>>I'm not mathematically fantastic so I hope this makes sense.
>>>>
>>>>I've written an algorithm to generate all permutations of words from a
>>>>given alphabet.
>>>>
>>>>Alphabet:
>>>>
>>>>"abc"
>>>>
>>>>Gives permutations:
>>>>
>>>>a, b, c, ab, ac, ba, bc, ca, cb, abc, acb, bac, bca, cab, cba
>>>>
>>>>In order to keep track of the progress through the algorithm, I need to
>>>>be able to calculate the total number of permutations in advance. I can
>>>>do this using the following formula:
>>>>
>>>>Number of permutations of size k taken from n objects is:
>>>>
>>>> n!
>>>>n_P_k = --------
>>>> (n - k)!
>>>>
>>>>So I can calculate the total number of permutations off all lengths as:
>>>>
>>>>P = (3! / (3! - 1!)) + (3! / (3! - 2!)) + (3! / (3! - 3!)) = 15
>>>>
>>>>However, the algorithm is designed to eliminate repeated permutations
>>>>that arise as a result of having repeated letters:
>>>>
>>>>Alphabet:
>>>>
>>>>"acc"
>>>>
>>>>Gives permutations:
>>>>
>>>>a, c, ac, ca, cc, acc, cac, cca
>>>>
>>>>This means that the formula above no longer works. I'm wondering if
>>>>someone can provide a formula to calculate the total of number of
>>>>permutations of *all* lengths that will be outputted in the following
>>>>scenarios:
>>>>
>>>>"abc" (should = 15)
>>>>
>>>>"accd" (should = 34)
>>>>
>>>>"acccdde" (uncertain as to what the result should be)
>>>>
>>>
>>> I don't know a closed formula for this total number (which is not to say
>>> that there isn't one!) but it is not difficult to calculate it.
>>>
>>> Suppose k1, k2, ..., kr are the numbers of each of the distinct letters
>>> in your string. (For example, for "acccddee", k1=1, k2=3, k3=k4=2.)
>>> Then the total number of what you describe above as "permutations" is
>>> (view this in fixed width font):
>>>
>>> k1 k2 kr
>>> -- -- --
>>> \ \ \ (i1 + i2 + ... + ik)!
>>> > > . . . > ---------------------- - 1
>>> / / / i1! i2! ... ik!
>>> -- -- --
>>> i1=0 i2=0 ik=0
>>>
>>> (The -1 at the end is to avoid counting the empty string, which
>>> corresponds
>>> to i1=i2=...ir=0 in the sum.)
>>>
>>> You should be able to write a program to evaluate this expression for
>>> given
>>> k1, k2, ..., kr. Doing it for the example above, k1=1, k2=3, k3=k4=2
>
>I think you meant k1=1, k2=3, k3=2, k4=1.

Yes, indeed I did!

>>> gives 1265, as quasi reported.
>>>
>>> Derek Holt.
>>
>>I have calculated your sum and I get 4952 or 5023 depending on if the one
>>is inside the sum or outside but not 1265.
>>
>
>The "1" is outside since it's intended to remove one case from the
>count.
>
>However Derek Holt's formula does correctly give a result of 1265 for
>the example in question, so check your program.
>

His program is probably correct, since the formula gives 5023 when
k1=2, k2=3, k3=k4=2.

Derek Holt.
.

Relevant Pages

  • Re: Summation of Reciprocals of Primes
    ... >>It sure does, especially given that the sum of the first 200,000,000 ... > Now that I find really suprising! ... Can you sketch the proof? ... > Derek Holt. ...
    (sci.math)
  • Re: Can any one help?
    ... If it has no root, then adjoining one gives an extension of degree p, so ... the degree of the splitting field of x^p-a over K must be divisible by p, ... Derek Holt. ... Prev by Date: ...
    (sci.math)