Looking for a closed form to determine whether a symbol is part of the ith combination nCr Hi I'm new to this, feel free to correct or edit anything if I haven't done something properly.
This is a programming problem I'm having and finding a closed form instead of looping would help a lot.
The Problem
Given a list of N symbols say {0,1,2,3,4...}
And ${{N}\choose{r}}$ combinations of these
eg. ${{N}\choose{3}}$ will generate:
0 1 2
0 1 3
0 1 4
...
...
1 2 3
1 2 4
etc...  
For the ith combination ($i = [1 .. {{N}\choose{r}}]$) I want to determine Whether a symbol (s) is part of it.
Func(N, r, i, s) = True/False or 0/1
eg. Continuing from above
The 1st combination contains 0 1 2 but not 3
F(N,3,1,"0") = TRUE
F(N,3,1,"1") = TRUE
F(N,3,1,"2") = TRUE
F(N,3,1,"3") = FALSE  
Current approaches and tibits that might help or be related.
Relation to matrices
For r = 2 eg. {4}\choose{2} the combinations are the upper (or lower) half of a 2D matrix
1,2 1,3 1,4
----2,3 2,4
--------3,4  
For r = 3 its the corner of a 3D matrix or cube
for r = 4 Its the "corner" of a 4D matrix and so on.
Another relation
Ideally the solution would be of a form something like the answer to this:
https://stackoverflow.com/questions/5052688/calculate-combination-based-on-position
The question there is (i think) not well worded
The nth combination in the list of combinations of length r (with repitition allowed), the ith symbol can be calculated
Using integer division and remainder:
$\lfloor n/r^i\rfloor$ % r = (0 for 0th symbol, 1 for 1st symbol....etc)   
eg for the 6th comb of 3 symbols the 0th 1st and 2nd symbols are:
i = 0 => 6 / 3^0 % 3 = 0
i = 1 => 6 / 3^1 % 3 = 2
i = 2 => 6 / 3^2 % 3 = 0   
The 6th comb would then be 0 2 0
I need something similar but with repition not allowed.
Thank you for following this question this far :]
Kevin.
 A: Just for completeness, I'm posting as an answer an elaboration of my comment above. There is no "closed form" as far as I know, but there's a very efficient algorithm. All this is also in Knuth Volume 4A (section 7.2.1.3).
Since you don't care about the order in which the combinations are generated, let's instead use the lexicographic order of the combinations where each combination is listed in descending order. Thus for $r=3$, the first 10 combinations of 3 symbols would be: 210, 310, 320, 321, 410, 420, 421, 430, 431, 432. The advantage of this ordering is that the enumeration is independent of $n$; indeed it is an enumeration over all sets of 3 symbols from $\{0, 1, 2, \dots \}$.
Now, there is a standard method to directly generate the $i$th combination given $i$, so to test whether a symbol $s$ is part of the $i$th combination, you can simply generate it and check. The method is the following:
How many combinations of $r$ symbols start with a particular symbol $s$? Well, the remaining $r-1$ positions must come from the $s$ symbols $0, 1, 2, \dots, s-1$, so it's $\binom{s}{r-1}$. As this is true for all $s$, the first symbol of the $i$th combination is the smallest $s$ such that $\sum_{k=0}^{s}\binom{k}{r-1} \ge i$. Once you know the first symbol, the problem reduces to finding the $\left(i - \sum_{k=0}^{s-1}\binom{k}{r-1}\right)$th combination of $r-1$ symbols, where we've subtracted those combinations that start with a symbol less than $s$.
In Python code, where C(n,r) is a function that returns $n \choose r$:
def combination(r, k):
    '''Finds the kth combination of r letters.'''
    if r==0: return []
    sum = 0
    s = 0
    while True:
        if sum + C(s,r-1) < k:
            sum += C(s,r-1)
            s += 1
        else:
            return [s] + combination(r-1, k-sum)

def Func(N, r, i, s): return s in combination(r, i)

The complexity is a bit icky to calculate, but it finds the 10000000000000000000000000000000000000000000000000000000000000000th combination of 500 letters (it starts with 542) in less than 0.5 seconds.
A: what you're looking for is called Lehmer code
