4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by, "the number of the element $[1,2,5,6]$"? That's not in the list; it doesn't have $K=3$. $\endgroup$ – Gerry Myerson Oct 16 '15 at 12:02
  • $\begingroup$ I think the question might be "given the lexicographic index of a $k$-set, what can I say about the lexicographic index of some closely related $(k+1)$-set?". $\endgroup$ – Ben Barber Oct 16 '15 at 12:08
  • $\begingroup$ Given a sequence [1, 2, 5, 6] identifying a K-set (in this case K=4) from a n-set by means the combination (n,k), can I know the order of such sequence? $\endgroup$ – Alessandro Oct 16 '15 at 12:38
  • $\begingroup$ The heavily edited version of the question remains ill-posed: consider the case $a_k = n$. I now believe that Alessandro's question is "How can I calculated the lexicographic index of a $k$-set from $[n]$?" which is not of research level. $\endgroup$ – Ben Barber Oct 17 '15 at 15:52
6
$\begingroup$

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$.

$\endgroup$
  • 3
    $\begingroup$ Thank you. But can I ask you why for n=5 and k=3 we don't get 012, 013, 014, 023, 024, 034, 123, 124, 134, 234? I need to the relation with this order. $\endgroup$ – Alessandro Oct 19 '15 at 7:08
  • 1
    $\begingroup$ @Alessandro: to get your order from mine, read my order from right-to-left: $234, 134, 034, \dots, 012$. Then reverse each word: $432, 431, 430, \dots, 210$. Then replace $i$ with $n-1-i$: $012, 013, 014, \dots, 234$. $\endgroup$ – Richard Stanley Oct 19 '15 at 23:12
  • $\begingroup$ I don't understand what is i ? $\endgroup$ – Alessandro Oct 21 '15 at 10:28
  • 1
    $\begingroup$ $i$ is any number $0,1,\dots,n-1$. $\endgroup$ – Richard Stanley Oct 22 '15 at 12:56
  • $\begingroup$ A last thing: do you know how formula is changed? $\endgroup$ – Alessandro Oct 23 '15 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.