Bijective function between natural numbers and arrangements with repetition

Question

Assume I have a set S = {a, b, c}

I can then list all possible arrangements with repetition from set S as:

()
(a)
(b)
(c)
(a,a)
(a,b)
(a,c)
(b,a)
(b,b)
(b,c)
(c,a)
(c,b)
(c,c)
(a,a,a)
(a,a,b)
and so on...

Now, I am looking for a bijection from these arrangements to the natural numbers. For example:

()      <->    0        (0-tuple)
(a)     <->    1        (1-tuples)
(b)     <->    2
(c)     <->    3
(a,a)   <->    4        (2-tuples)
(a,b)   <->    5
(a,c)   <->    6
(b,a)   <->    7
(b,b)   <->    8
(b,c)   <->    9
(c,a)   <->   10
(c,b)   <->   11
(c,c)   <->   12
(a,a,a) <->   13        (3-tuples)
(a,a,b) <->   14
and so on ...

Is it possible to calculate this bijection in an efficient way? For example, if given (a,b,b,b,c,c,a) how could you calculate what natural number it maps to and vice versa?

Edit

This edit is in response to N. F. Taussig's comment.

Continuing with the set S = {a, b, c} as an example, the number of n-tuples for each n is 3^n. This means that:

          number of n-tuples    natural number mapping
0-tuple                0                  0
1-tuples               3           1  -   3
2-tuples               9           4  -  12
3-tuples              27          13  -  39
4-tuples              81          40  - 120
5-tuples             243         121  - 363

So that gets me part way there to my bijection. Just by looking at the chart I know that the tuple (a,a,a,a) maps to 40, and the tuple (c,c,c,c,c) maps to 363.

Now my problem is a bit simpler. I just need to know an easy way to number each n-tuple group.

Answer 1

Ok, I think I figured it out.

First, I can take each tuple and interpret it as a number written in base/radix of the cardinality of the set. For example, still assuming the set S = {a, b, c} I can convert the n-tuples into numbers using a=0, b=1, and c=3.

This means:

         base-3   decimal
()         0         0
(a)        0         0
(b)        1         1
(c)        2         2
(a,a)     00         0         
(a,b)     01         1
(a,c)     02         2
(b,a)     10         3
(b,b)     11         4
(b,c)     12         5
(c,a)     20         6
(c,b)     21         7
(c,c)     22         8
(a,a,a)  000         0
(a,a,b)  001         1

The problem is that (a), (a,a), and (a,a,a) all come out to zero. So I take this number and add to it the following:

$f(k) = \sum_{i=0}^{k-1}3^{i}$

where k is the length of the tuple.

This means that:

         base-3   dec        f(k)     dec+f(k)
()         0         0         0        0 
(a)        0         0         1        1
(b)        1         1         1        2
(c)        2         2         1        3
(a,a)     00         0         4        4
(a,b)     01         1         4        5
(a,c)     02         2         4        6
(b,a)     10         3         4        7
(b,b)     11         4         4        8
(b,c)     12         5         4        9
(c,a)     20         6         4       10
(c,b)     21         7         4       11
(c,c)     22         8         4       12
(a,a,a)  000         0        13       13
(a,a,b)  001         1        13       14

And that's my answer. Thanks to N.F.Taussig for pointing me in the right direction.