CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Calculating serial number in a permutation"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #790
Reading Topic #790
John
guest
Sep-05-07, 08:14 AM (EST)
 
"Calculating serial number in a permutation"
 
   Let's say we have to find out what serial number takes a particular combination in an ordered permutation.
For example if we have to choose three numbers out of eight, the number of possible combinations is 56, starting from '123', '124', '125'... and ending with '678'. In such an order, serial combination number e.g. 36 is combination '278', 47 is '456' and the last serial 56 is '678'.

If I want to know what serial is the combination e.g. '267', what would be the best logical or algorithmical way of solving this, regardless of base system (in this case base 8).

Note that the numbers in a combination are always in ascending order e.g. '236', '458' etc, so something like '317' is not possible.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Sep-06-07, 07:54 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
1. "RE: Calculating serial number in a permutation"
In response to message #0
 
   Hi John,

Let's say N is the total number of different digits to choose from and n is the number of digits in your ordered string. Then in your example, N=8 and n=3. First, let's establish the total number of ordered strings of digits. Since the digits are all distinct, and you only count each choice of digits once, you are counting combinations, not permutations, and so the total is B(N,n), where B is the binomial coefficient. That is, B(N,n) = N!/(n!(N-n)!).

With this as a starting point, now let's calculate the number of combinations that start with a fixed initial choice of several digits. Let's call the digit'string d(1), d(2), ... d(n), and let k be the position within the digit string, so that d(k) is the digit at the kth position. Suppose you've already chosen d(1),...d(k). Since these digits are now fixed, you still have n-k digits to choose, and they must be larger than d(k). Therefore, this is just a smaller version of the counting problem in the first paragraph, with N-d(k) digits to choose from, and n-k choices to make. Therefore, the number to strings that start with the fixed set of digits d(1),...d(k) is B(N-d(k),n-k).

To make the calculation more convenient, let's next calculate the number of combinations where the first several digits are fixed and the next digit is allowed to grow from a fixed starting value. In other words, choose d(1),...,d(k), and then step the value of d(k) up from its initial value all the way to N, so that you consider strings starting with d(1),...,d(k)+1; d(1),...,d(k)+2; and so on. The easiest way to do this (instead of summing a bunch of binomial coefficients) is to step back one place in the sequence and consider that d(1),...,d(k-1) are truly fixed, while the kth digit can have any value greater than or equal to d(k). This makes the problem identical to the one in the previous paragraph, except that you are choosing the next digits from d(k) up to N (inclusive). Therefore, you are choosing n-k+1 digits from among N-d(k)+1, so the number of strings is B(N-d(k)+1,n-k+1).

From this you can get the numerical order of your digit strings as follows: Look at the digit d(1). The number of strings that start with d(1) or d(1)+1 or ... or N is given by the formula in the previous paragraph with k=1, i.e. B(N-d(1)+1,n). The total number of strings is B(N,n), and so the number of strings which start with a lower digit than d(1) is B(N,n) - B(N-d(1)+1,n). All of these strings came before your string, so its serial order position is at least this great.

Next, turn to d(2), and repeat the argument in the previous paragraph. The number of strings that start with d(1) and have the second digit at least as large as d(2) is B(N-d(2)+1,n-1, while the total number of strings that start with d(1) is B(N-d(1),n-1). Therefore, the number of strings that start with d(1) and have their second digit less than d(2) is B(N-d(1),n-1) - B(N-d(2)+1,n-1). These strings also come before your string.

Similarly, stepping through all the digits, the total number of strings that come before yours is
B(N,n) - B(N-d(1)+1,n) +
B(N-d(1),n-1) - B(N-d(2)+1,n-1) +
B(N-d(2),n-2) - B(N-d(3)+1,n-2) + ... +
B(N-d(n),n-n) - B(N-d(n)+1,n-n).

Now pair the right term on each line with the left term on the next line below it. The general form is
-B(N-d(k)+1,n-k+1) + B(N-d(k),n-k), which is of the form
-B(x+1,y+1) + B(x,y). It is simple to check the identity (which can be seen from Pascal's triangle)
B(x,y) + B(x,y+1) = B(x+1,y+1).
Therefore, -B(x+1,y+1) + B(x,y) = -B(x,y+1) =
-B(N-d(k),n-k+1).

Therefore the number of strings that come before yours is
B(N,n) - SUM from k=1 to k=n (B(N-d(k),n-k+1)) -1,
which means that the serial number of your string is one more than this,
B(N,n) - SUM from k=1 to k=n (B(N-d(k),n-k+1)).

For example, with N=8, n=3, d(1),d(2),d(3) = 278, you get
B(8,3) - B(8-2,3) - B(8-7,2) - B(8-8,1) =
B(8,3) = B(6,3) - 0 - 0 = 8*7*6/(1*2*3) - 6*5*4/(1*2*3) =
56 - 20 = 36, which matches your answer.

For the sequence 456, you get
B(8,3) - B(4,3) - B(3,2) - B(2,1) = 56 - 4 - 3 - 2 = 47, which also matches your answer.

Hope this helps!

Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
John
guest
Sep-07-07, 12:17 PM (EST)
 
2. "RE: Calculating serial number in a permutation"
In response to message #1
 
  
Thank you very much Stuart.
Could you please try to outline the other way around too?
So, if the sequence number (lets say '22') is known, what would be the best way to find out the right combination?


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Sep-07-07, 06:24 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
3. "RE: Calculating serial number in a permutation"
In response to message #2
 
   >
>Thank you very much Stuart.
>Could you please try to outline the other way around too?
>So, if the sequence number (lets say '22') is known, what
>would be the best way to find out the right combination?

Hi again John,

Glad to help! It was an interesting problem. Now as to the reverse calculation, this one is harder, I think. I do not immediately see a direct way to calculate the answer, although there is a fairly simple recursive method. It is basically similar to long division, except that instead of powers of a base number, you have the B(x,y) values.
Here is how I would do it:

Looking at the forward calculation, it is clear that it is easier to count the number of strings that come after your string instead of the number before it. The total number of strings is B(N,n), and so sum from k=1 to k=n (B(N-d(k),n-k+1)) is the number of strings that come later than yours. In fact, now that I'm thinking about it, I should have done it this way in my first post; then I wouldn't have needed the binomial identity to collect terms. I could have just stayed with finding the number of later strings until the end, and then subtracted that from B(N,n). It would have been a cleaner derivation. Oh, well.

Anyway, let the sequence number be s, and let t = B(N,n) - s. Then the result of my previous post can be expressed as
t = sum from k=1 to k=n (B(N-d(k),n-k+1)).
This sum has the same properties as the power sum expressing a number in a positional system, such as decimal or binary, namely that summing up the largest possible values of lower order terms can never reach the size of the next higher order term. By this I mean a property like 999 < 1000. The sum has this property because going up one step in a higher order term adds a set of strings to the count, and all the strings that are added by the lower order terms are subsets of this string, so the count cannot be larger.

This means that you can do "long division" as follows:
First, d(1) is the smallest value of x for which B(N-x,n) < t (because LOWER values of d(1) increase the number of strings that come later). Since this accounts for some of the strings which come after yours, subtract this amount from t to get t'. Next, d(2) is the smallest value of x for which B(N-x,n-1) < t'. Again, subtract this to get t'' and repeat as before to get the rest of the digits.

To find the value x each time, it is easiest to let N-x = y and just increment y until B(y,n) < t. If you do it this way, you can start with y=n and increment it from there, which means that you won't have to explicitly calculate B(y,n) at all. This is because B(n,n) = 1, and the ratio B(y+1,n)/B(y,n) = ((y+1)!/(n!(y+1-n)!))/(y!/(n!(y-n)!)) = (y+1)/(y-n+1).

The C language code for this algorithm would look something like this:


(void)stringmaker(int N, int n, int s, int* d)
{
int B, y, t, k;
t=N-s;
for(k=n; k>0; k--)
{
B=1;
for(y=k; B>=t; y++)
{
B=B*(y+1)/(y-k+1);
}
t=t-B;
d=N-y;
}
}

At least, I'm pretty sure that code will work. I haven't tried it out.

Hope this helps!

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
John
guest
Sep-08-07, 09:34 AM (EST)
 
4. "RE: Calculating serial number in a permutation"
In response to message #3
 
   Great!

Stuart you rock.
Thank you for spending your time and brain on this.

Cheers!


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Sep-08-07, 01:50 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
5. "RE: Calculating serial number in a permutation"
In response to message #4
 
   Hi John,

No problem! It was an interesting exercise. There is one more thing I should point out -- I forgot about the fact that the square brackets are used to enclosed html formatting tags even inside of preformatted code. That means that there are some square brackets missing from the computer code I wrote. The relevant lines should look like


(void)stringmaker(int N, int n, int s, int* d[n])

...

d[n-k]=N-y;
...


With these changes, it'should work.

Any time you come up with another interesting problem, just post it here. I really enjoy this kind of puzzle.

Cheers!

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK