2
$\begingroup$

Suppose $I\subseteq\{1,\dots,n\}$, and let $\{1,\dots,n\}\setminus I=\{j_1,\dots,j_m\}$ be an enumeration of the complement of $I$ with $j_r<j_{r+1}$ for each $r\in\{1,\dots,m-1\}$. To $I$ I can attach the sequence $p(I)=(p_1,\dots,p_m)$ of non-negative integers with $p_r=|\{i\in I:i<j_r\}|$, which is such that $0\leq p_1\leq\cdots\leq p_m\leq n-m$. Conversely. each such sequence arises from exactly one $I$.

This bijection arises in a homological computation I am trying to do. I have something parametrized in terms of the $I$'s and I want to single out those that satify a condition best expressed in terms of the $p(I)$'s, and this is turning to be somewhat incovenient... It would probably be useful to me to know:

Has this bijection showed up in some other context?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I didn't realize that was the collective word for subsets, as a pride of lions, a murder of crows, or an exaltation of larks. $\endgroup$
    – Will Jagy
    Commented Jul 7, 2014 at 23:52
  • $\begingroup$ For "...$\setminus U$..." did you mean "...$\setminus I$..."? $\endgroup$
    – Joseph O'Rourke
    Commented Jul 8, 2014 at 0:08
  • $\begingroup$ There is a well-known correspondence between compositions of $n$ and subsets of $[n-1]$ that is important (at least for notation) in the theory of quasisymmetric functions: see the third paragraph of section 7.19 of Stanley's EC2. But your bijection is slightly different than this. $\endgroup$
    – Sam Hopkins
    Commented Jul 8, 2014 at 1:11

1 Answer 1

Reset to default
2
$\begingroup$

In computability theory, the function $r\mapsto j_r$ is called the principal function of the set $J=\{j_1<\dots<j_m\}$ and denoted $p_J$. The relation with your function being that $p_r=j_r-r$, i.e., you're just subtracting the identity function from the principal function of the complement of $I$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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