Writing a recursive definition of the set permutation function

  • Thread starter W3bbo
  • Start date
  • #1
31
0
(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:

TTR, TRT, RTT

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".

KSsTC.png


...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?

Thanks!
 

Answers and Replies

  • #2
703
13
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.
 

Related Threads on Writing a recursive definition of the set permutation function

Replies
1
Views
1K
Replies
3
Views
938
  • Last Post
Replies
12
Views
4K
Replies
2
Views
2K
Replies
9
Views
2K
Replies
9
Views
1K
  • Last Post
Replies
9
Views
5K
Replies
3
Views
1K
Replies
5
Views
1K
  • Last Post
Replies
10
Views
7K
Top