6

I am working on a project and this is a mathematical issue I have encountered. Combinatorics is not my strong point so some help would be most welcome.

The idea is you have 81 elements to pick from and you pick 6 of them, no repeats, order does matter. I know then that the number of combinations that can be picked is $$\frac{81!}{(81-6)!}=233‚668‚955‚520$$ So far that is not an issue. Now I want to give each of these a numberic idea from 1 to almost 234 billion based on their "order". So starting with the lowest being 1, second lowest 2 etc We'd get

1-2-3-4-5-6 = 1

1-2-3-4-5-7 = 2

1-2-3-4-5-8 = 3

...

1-2-3-4-5-81 = 75

1-2-3-4-6-5 = 76

and so on in a similar fashion. Where it ticks up in a similar fashion over and over further and further left until it finally ends with

81-80-79-78-77-76=233‚668‚955‚520

My issue is, I am entirely unable to figure out a good formula to achieve this. I am seeking a formula $$f:\mathbb{N}_{81}^6\to\mathbb{N}$$

such that $$f(a,b,c,d,e,f)=\text{id}$$

Is tehre any good way to find this or do I need ot use other methods?

Zelos Malum
  • 6,570

1 Answers1

3

In Python, in less than 20 lines of code:

def perms(n, m):
    result = 1
    for i in range(0, m):
        result *= (n - i)
    return result

def id(alphabet, numbers):
    head = numbers[0]
    index = alphabet.index(head)
    m = len(numbers)
    if m == 1:
        return 1 + index 
    p = perms(len(alphabet) - 1, m - 1)
    alphabet.remove(head)
    numbers.remove(head)
    return index * p + id(alphabet, numbers)

def fun(a, b, c, d, e, f):
    # alphabet goes from 1 to 81
    alphabet = [i for i in range(1, 82)]
    numbers = [a, b, c, d, e, f]
    return id(alphabet, numbers)

print(fun(1,2,3,4,5,6))
print(fun(1,2,3,4,6,5))
print(fun(81,80,79,78,77,76))
print(fun(23,80,49,26,15,11))

The code prints:

1
77
233668955520
66299919067

The code is recursive. Basically, it finds the alphabet index of the first symbol in the permutation. Based on that it calculates the number of permutations starting with symbols coming earlier in the alphabet. On top of that it adds the index of permutation wth its first symbol removed in an alphabet with the same symbol removed as well.

If you need code in some other programming language, please let me know.

(Note the error that you have in line: 1-2-3-4-6-5=76; it should be 77)

Saša
  • 15,906