1. |
- Eriksen, Niklas, 1974, et al.
(författare)
-
Enumeration of derangements with descents in prescribed positions
- 2009
-
Ingår i: Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1077-8926 .- 1097-1440. ; 16:1
-
Tidskriftsartikel (refereegranskat)abstract
- We enumerate derangements with descents in prescribed positions. A generating function was given by Guo-Niu Han and Guoce Xin in 2007. We give a combinatorial proof of this result, and derive several explicit formulas. To this end, we consider fixed point $\lambda$-coloured permutations, which are easily enumerated. Several formulae regarding these numbers are given, as well as a generalisation of Euler's difference tables. We also prove that except in a trivial special case, if a permutation $\pi$ is chosen uniformly among all permutations on $n$ elements, the events that $\pi$ has descents in a set $S$ of positions, and that $\pi$ is a derangement, are positively correlated.
|
|
2. |
- Freij, Ragnar, 1984, et al.
(författare)
-
Partially ordered secretaries
- 2010
-
Ingår i: Electronic Communications in Probability. - 1083-589X. ; 15, s. 504-507
-
Tidskriftsartikel (refereegranskat)abstract
- The elements of a finite nonempty partially ordered set are exposed at independent uniform times in [0, 1] to a selector who, at any given time, can see the structure of the induced partial order on the exposed elements. The selector’s task is to choose online a maximal element. This generalizes the classical linear order secretary problem, for which it is known that the selector can succeed with probability 1=e and that this is best possible. We describe a strategy for the general problem that achieves success probability at least 1=e for an arbitrary partial order.
|
|