1
$\begingroup$

I have a question that came up during one of my combinatorial algorithm lectures, and could use some help. One of the theorems our book provides states that:

Let $S$ consist of all $k$-element subsets of the $n$-set $S=\{1,\dots,n\}$. Suppose that $\operatorname{rank}_L$ denotes rank in the lexicographic ordering, and $\operatorname{rank}_C$ denotes rank in the co-lexicographic ordering. Then, for any $k$-set $T\in S$, we have $$\operatorname{rank}_L(T)+\operatorname{rank}_C(T')=\binom{n}{k}-1,$$ where $T'=\{n+1-i : i \in T \}$.

There was also an example provided where one subset $T=\{1,2,3\}$ had the corresponding $T'=\{3,4,5\}$, and I'm not entirely sure how this conclusion was reached. In this example $n=5$ and $k=3$.

How was $T'$ computed in this instance, and what would $n$ and $i$ be in the equation for $T'$?

$\endgroup$
  • $\begingroup$ Should that be $T'=\{n-i+1:i\in T\}?$ $\endgroup$ – saulspatz Feb 26 at 16:17
  • $\begingroup$ @saulspatz in the textbook I'm using it has the formula as $T'=\{n + 1 - i : i \in T \}$ $\endgroup$ – Ted Feb 26 at 16:21
  • $\begingroup$ That looks like a typo to me. If you use the formula I suggest, you'll see how to compute $T'.$ $\endgroup$ – saulspatz Feb 26 at 16:22
  • $\begingroup$ @saulspatz just confirmed that the textbook did have a typo! I'll fix my post accordingly. Still, what would $i$ be? For example, for the set $\{1,2,3\}$, would $n$ be 5, and $i$ be 1? That still wouldn't yield $\{3,4,5\}$ $\endgroup$ – Ted Feb 26 at 16:26
  • 2
    $\begingroup$ "$\left\{n+1-i : i \in T\right\}$" is an instance of set-builder notation. Speaking in dynamical terms: you let $i$ run through $T$ and write down the resulting values of $n+1-i$; then you pack these resulting values into a set. So for $T = \left\{1,2,3\right\}$ and $n = 5$, you write down the values $5,4,3$ (obtained for $i$ being $1,2,3$, respectively) and pack them into a set; the resulting set is $\left\{5,4,3\right\} = \left\{3,4,5\right\}$. $\endgroup$ – darij grinberg Feb 26 at 17:00

Your Answer

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

Browse other questions tagged or ask your own question.