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
    Jul 7, 2014 at 23:52
  • $\begingroup$ For "...$\setminus U$..." did you mean "...$\setminus I$..."? $\endgroup$
    – Joseph O'Rourke
    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
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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