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.

Improve this question
$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 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, 2015 at 15:52

1 Answer 1

Reset to default
7
$\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$.

Improve this answer
$\endgroup$
4
  • 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, 2015 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, 2015 at 23:12
  • $\begingroup$ I don't understand what is i ? $\endgroup$
    – Alessandro
    Oct 21, 2015 at 10:28
  • 1
    $\begingroup$ $i$ is any number $0,1,\dots,n-1$. $\endgroup$
    – Richard Stanley
    Oct 22, 2015 at 12:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .