Let $L(n,k)$ be the increasing $k$-tuples from $\{1,\dots,n\}$, listed in lexicographic order. 


Eg, for $n=9$, $k=3$, the sequence $L(n,k)$ would be:


$$(1,2,3), (1, 2, 4), (1, 2, 5),\dots,(7, 8, 9).$$


The question is: given that a $k$-tuple $(a\_1,\dots,a\_k)$ is in position $N$ in $L(n,k)$, with $a\_k<n$, is there a formula for the position of 
$(a\_1,\dots,a\_k,a\_k+1)$ in $L(n,k+1)$ in terms of $N$?


(The original post asked about the case $n=9$, $k=3$, and was a bit difficult to understand, so I have edited it. Please feel free to revert the changes if you wish.)


EDIT [JMP]: Original formula said $n$, but $(7,8,9)\to(7,8,9,10)$ for example.


EDIT [HT]: Rather than change $n$ to $n+1$, I explicitly required $a\_k<n$, which seems to have been what the OP intended.



Lexicographic order on increasing $k$-tuples
Write all $k$-tuples from $\lbrace 0,\dots,n-1\}$ in *reverse*
lex order. E.g., for $n=5$ and $k=3$ we get $012, 013, 023, 123, 014,
024, 124, 034, 134, 234$. Call the terms $x\_0,x\_1,\dots$, so for the
above example $x\_5=024$ (short for $(0,2,4)$). Now suppose that
$(a\_1,a\_2,\dots,a\_k)=x\_N$. Then $N={a\_k\choose k}+{a\_{k-1}\choose k-1}
+ \cdots+{a\_1\choose 1}$. This is essentially due to Macaulay. See for
instance <http://arxiv.org/pdf/1403.4862.pdf>.


Let $x\_0,x\_1,\dots,x\_{t-1}$ (where $t={n\choose k}$) be the reverse
lex order of $k$-tuples from $\lbrace 0,\dots, n-1\rbrace$. Then
$x\_{t-1}, x\_{t-2},\dots, x\_0$ is the lex order of the same set, with
respect to the order $n-1<n-2<\cdots<0$. Thus it is easy to compute
the position of $(a\_1,\dots,a\_k,a\_k+1)$ in $L(n,k+1)$, but it won't be
a formula just in terms of $N$.


