Number of possible outcomes for 2 numbers given that one number is greater than the other

I am trying to write an algorithm to calculate outcomes. But I need help with combinatorics.

Suppose I have to choose 2 numbers from 1 to 10. From the fundamental rule of counting, in the absence of any restriction, the number of possible outcomes is 10 * 10 = 100. (10 possible outcomes in choosing the first number x 10 possible outcomes in choosing the 开发者_如何学Gosecond).

What is the number of possible outcomes given that the first number has to be greater than the second number?

45.

Imagine your grid of 10x10 pairs. There's a diagonal line from 1,1 to 10,10 where A=B, so those aren't A>B. The line divides the other cases into two halves.. one with A>B and one with B < A. Each of these partitions are equal size. There's 90 values left (10 taken by the diagonal line) so there are 45 pairs where A > B.

If you choose:

• 1: 2 to 10 = 9 possibilities
• 2: 3 to 10 = 8 possibilities
• ...
• 9: 10 = 1 possibility

So

9 + 8 + ... + 2 + 1 = 45

This is called an arithmetic progression the sum is equal to:

f(n) = n * (n+1) / 2 = 9 * 10 / 2 = 45

I would say

f(n) = n * (n-1) / 2

where n is equal to the number of different numbers that needs to be combined. So for n = 10 it would be:

10 * (10-1) / 2 = 45

Your question falls under the binomial coefficient. To calculate the total number of unique combinations of 10 items taken 2 at a time, the formula N! / (K! (N - K)!) can be used. Plugging in 10 for N and 2 for K yields 45.

I have written a class to handle common functions for working with the binomial coefficient, which is the type of problem this falls under. It performs the following tasks:

1. Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial.

2. Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique, but I could be wrong.

3. Converts the index in a sorted binomial coefficient table to the corresponding K-indexes.

4. Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.

5. The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table.

6. There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

To read about this class and download the code, see Tablizing The Binomial Coeffieicent.

It should not be hard to convert this class to C++.