# How to compute $T'=\{n + 1 - i : i \in T \}$ for lexicographic ordering?

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'$$?

• Should that be $T'=\{n-i+1:i\in T\}?$ – saulspatz Feb 26 at 16:17
• @saulspatz in the textbook I'm using it has the formula as $T'=\{n + 1 - i : i \in T \}$ – Ted Feb 26 at 16:21
• That looks like a typo to me. If you use the formula I suggest, you'll see how to compute $T'.$ – saulspatz Feb 26 at 16:22
• @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\}$ – Ted Feb 26 at 16:26
• "$\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\}$. – darij grinberg Feb 26 at 17:00