exercise:4627c2636c: Difference between revisions
(Created page with "<div class="d-none"><math> \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}</math></div> Given any ordering <math>\sigma</math> of <math>\{1, 2, \ldots, n\}</math>, we can define <math>\sigma^{-1}</math>, the inverse ordering of <math>\sigma</math>, to be the ordering in which the <math>i</math>th element is the position occupied by <...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
Given any ordering <math>\sigma</math> of <math>\{1, 2, \ldots, n\}</math>, we can define | |||
define | |||
<math>\sigma^{-1}</math>, the inverse ordering of <math>\sigma</math>, to be the ordering in which the | <math>\sigma^{-1}</math>, the inverse ordering of <math>\sigma</math>, to be the ordering in which the | ||
<math>i</math>th element is the position occupied by | <math>i</math>th element is the position occupied by | ||
| Line 14: | Line 7: | ||
<math>\sigma</math>.) | <math>\sigma</math>.) | ||
A ''fall'' occurs between two positions in an ordering if the left position is occupied by a larger number than the right position. It will be convenient | |||
A ''fall'' occurs between two positions in an ordering if the left | |||
position is occupied by a larger number than the right position. It will be convenient | |||
to say that every ordering has a fall after the last position. In the above example, | to say that every ordering has a fall after the last position. In the above example, | ||
<math>\sigma^{-1}</math> has four falls. They occur after the second, fourth, sixth, and seventh | <math>\sigma^{-1}</math> has four falls. They occur after the second, fourth, sixth, and seventh | ||
positions. Prove that the number of rising sequences in an ordering <math>\sigma</math> equals | positions. Prove that the number of rising sequences in an ordering <math>\sigma</math> equals | ||
the number of falls in <math>\sigma^{-1}</math>. | the number of falls in <math>\sigma^{-1}</math>. | ||
Latest revision as of 23:28, 12 June 2024
Given any ordering [math]\sigma[/math] of [math]\{1, 2, \ldots, n\}[/math], we can define [math]\sigma^{-1}[/math], the inverse ordering of [math]\sigma[/math], to be the ordering in which the [math]i[/math]th element is the position occupied by [math]i[/math] in [math]\sigma[/math]. For example, if [math]\sigma = (1, 3, 5, 2, 4, 7, 6)[/math], then [math]\sigma^{-1} = (1, 4, 2, 5, 3, 7, 6)[/math]. (If one thinks of these orderings as permutations, then [math]\sigma^{-1}[/math] is the inverse of [math]\sigma[/math].)
A fall occurs between two positions in an ordering if the left position is occupied by a larger number than the right position. It will be convenient to say that every ordering has a fall after the last position. In the above example, [math]\sigma^{-1}[/math] has four falls. They occur after the second, fourth, sixth, and seventh positions. Prove that the number of rising sequences in an ordering [math]\sigma[/math] equals the number of falls in [math]\sigma^{-1}[/math].