Applications to combinatorics and probabilities Lehmer code

1 applications combinatorics , probabilities

1.1 independence of relative ranks
1.2 number of right-to-left minima , maxima
1.3 secretary problem

applications combinatorics , probabilities
independence of relative ranks

the lehmer code defines bijection symmetric group sn cartesian product



[
n
]
×
[
n
−
1
]
×
⋯
×
[
2
]
×
[
1
]


{\displaystyle [n]\times [n-1]\times \cdots \times [2]\times [1]}

, [k] designates k-element set



{
0
,
1
,
…
,
k
−
1
}


{\displaystyle \{0,1,\ldots ,k-1\}}

. consequence, under uniform distribution on sn, component l(σ)i defines uniformly distributed random variable on [n − i], , these random variables mutually independent, because projections on different factors of cartesian product.

number of right-to-left minima , maxima

definition : in sequence u=(uk)1≤k≤n, there right-to-left minimum (resp. maximum) @ rank k if uk strictly smaller (resp. strictly bigger) each element ui i>k, i.e., right.

let b(k) (resp. h(k)) event there right-to-left minimum (resp. maximum) @ rank k , i.e. b(k) set of permutations




 



s



n





{\displaystyle \scriptstyle \ {\mathfrak {s}}_{n}}

exhibit right-to-left minimum (resp. maximum) @ rank k. have

{
ω
∈
b
(
k
)
}
⇔
{
l
(
k
,
ω
)
=
0
}


and


{
ω
∈
h
(
k
)
}
⇔
{
l
(
k
,
ω
)
=
k
−
1
}
.


{\displaystyle \{\omega \in b(k)\}\leftrightarrow \{l(k,\omega )=0\}\quad {\text{and}}\quad \{\omega \in h(k)\}\leftrightarrow \{l(k,\omega )=k-1\}.}

thus number nb(ω) (resp. nh(ω)) of right-to-left minimum (resp. maximum) permutation ω can written sum of independent bernoulli random variables each respective parameter of 1/k :

n

b


(
ω
)
=

∑

1
≤
k
≤
n


 
1



1

b
(
k
)




and



n

b


(
ω
)
=

∑

1
≤
k
≤
n


 
1



1

h
(
k
)


.


{\displaystyle n_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{b(k)}\quad {\text{and}}\quad n_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{h(k)}.}

indeed, l(k) follows uniform law on




 
[

[
1
,
k
]

]
,



{\displaystyle \scriptstyle \ [\![1,k]\!],}

p

(
b
(
k
)
)
=

p

(
l
(
k
)
=
0
)
=

p

(
h
(
k
)
)
=

p

(
l
(
k
)
=
k
−
1
)
=



1
k



.


{\displaystyle \mathbb {p} (b(k))=\mathbb {p} (l(k)=0)=\mathbb {p} (h(k))=\mathbb {p} (l(k)=k-1)={\tfrac {1}{k}}.}

the generating function bernoulli random variable



1



1

b
(
k
)




{\displaystyle 1\!\!1_{b(k)}}

is

g

k


(
s
)
=



k
−
1
+
s

k


,


{\displaystyle g_{k}(s)={\frac {k-1+s}{k}},}

therefore generating function of nb is

g
(
s
)
=

∏

k
=
1


n



g

k


(
s
)
 
=
 



(
s

)

↑
n




n
!



,


{\displaystyle g(s)=\prod _{k=1}^{n}g_{k}(s)\ =\ {\frac {(s)_{\uparrow n}}{n!}},}

which allow find again product form generative series of stirling numbers of first kind (unsigned).

the secretary problem

this optimal stop problem, classic in decision theory, statistics , applied probabilities, random permutation gradually revealed through first elements of lehmer code, , goal stop @ element k such σ(k)=n, whereas available information (the k first values of lehmer code) not sufficient compute σ(k).

in less mathematical words : series of n applicants interviewed 1 after other. interviewer must hire best applicant, must make decision (“hire” or “not hire”) on spot, without interviewing next applicant (and fortiori without interviewing applicants).

the interviewer knows rank of k applicant, therefore, @ moment of making k decision, interviewer knows k first elements of lehmer code whereas need know of them make informed decision. determine optimal strategies (i.e. strategy maximizing probability of win), statistical properties of lehmer code crucial.

allegedly, johannes kepler exposed secretary problem friend of @ time when trying make mind , choose 1 out eleven prospective brides second wife. first marriage had been unhappy one, having been arranged without himself being consulted, , concerned reach right decision.