Below is Mathematica code based on Igor Pak's answer. To get a random downup permutation on $[n]$, start by choosing the first entry $p_1$ with the appropriate probability; then randomly choose an updown permutation of size $n-1$ from the updown permutations <em>with first entry $< p_1$</em>; then join them together (incrementing entries $\ge p_1$ in the updown permutation).

To implement this method, we actually need code to generate a random downup permutation with first entry $\ge$ a specified number $k$ and the code below does so. It uses the ComplementPermutation operation to interchange updown and downup permutations.


(* e[n,k] is the Entringer number *)

e[0,0] = 1; <BR>
e[n_,0]/;n>=1 := 0; <BR>
e[n_,k_]/;k>n || k<0 := 0 <BR>
e[n_,k_] := e[n,k] = e[n,k-1] + e[n-1,n-k] 

 
ComplementPermutation[perm_] := Module[{n=Length[perm]}, n+1-perm];<BR>

incrementSpecifiedAndUp[perm_,k_]:=perm/.{i_/;i>=k :> i+1};

partialSums[list_] := Drop[FoldList[Plus,0,list],1];

RandomUpDownPermFirstEntryAtMostk[n_,k_]/;k==n :=   
    RandomUpDownPermFirstEntryAtMostk[n,n-1];<BR>
RandomUpDownPermFirstEntryAtMostk[n_,k_]/;1<=k&lt;n := <BR>
    ComplementPermutation[RandomDownUpPermFirstEntryAtLeastk[n,n+1-k]]

RandomDownUpPermFirstEntryAtLeastk[1,1]={1};
RandomDownUpPermFirstEntryAtLeastk[2,2]={2,1};

RandomDownUpPermFirstEntryAtLeastk[n_,k_]/; n>=3 && 2<=k<=n := 
Module[{keys,m,i,firstEntry,restOfPerm},

(* pick first entry using the Entringer distribution *)<BR>
keys=partialSums[Table[e[n-1,j],{j,k-1,n-1}]];<BR>
m=Random[Integer,{1,Last[keys]}];<BR>
i=1;<BR>
While[Not[ m<=keys[[i]] ],i=i+1];<BR>
firstEntry=k-1+i;<BR>

(* choose restOfPerm uniformly from updowns with <em>their</em> first entry < firstEntry *)<BR>
restOfPerm=RandomUpDownPermFirstEntryAtMostk[n-1,k-2+i];<BR>

(* amalgamate firstEntry and restOfPerm *)<BR>
Join[{firstEntry},incrementSpecifiedAndUp[restOfPerm,firstEntry]] ]<BR>

RandomDownUpPerm[1]={1};<BR>
RandomDownUpPerm[n_]/;n>=2 := RandomDownUpPermFirstEntryAtLeastk[n,2]<BR>
 
Sample output:<BR>
In[264]:=RandomDownUpPerm[15]<BR>
Out[264]=<BR>
{8, 2, 4, 1, 15, 6, 7, 3, 10, 9, 13, 11, 14, 5, 12}