1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Writing a recursive definition of the set permutation function

  1. Feb 2, 2012 #1
    (Apologies for the lack of LaTeX formatting - I usually do my typesetting with MathType, but I only have Microsoft Equation Editor on this computer which doesn't have LaTeX export).

    This isn't a homework question, but is problem I've discovered I'm facing after diving into another problem, but I digress:

    Consider this set, A:

    A = { T, T, R }

    It has six proper permutations, but only three distinct permutations:


    The expression for the number of unique permutations (in this case) is:

    |A|! / ( |'T' elements| ! * |'R' elements| ! )

    So: 3! / 2! * 1! which is 6/2 == 3

    Due to certain requirements, I need to express this function recursively. Because the factorial function is used, I figured I could take it from there.

    The expressions below take the permutation-count formula and assumes that every set A is comprised of N 'T' elements, and M 'R' elements and is called "routes".


    ...but I can't figure out how to make it recursive. Note the huge error on the third line down, it does not follow from the line above.

    Is a recursive definition even possible?

  2. jcsd
  3. Feb 3, 2012 #2
    You can express a binomial coefficient recursively like this (see wikipedia article):
    [tex]\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ k \end{pmatrix}[/tex]

    You can interpret this as Pascal's triangle.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook