Help16:=proc(): print(` IsUD(pi), IsDU(pi), UDpers(n), DUpers(n), UDni(n,i), DU(n,i), UDn(n) `):end:

with(combinat):

IsUD:=proc(pi) local n:
n:=nops(pi):

if n=1 then
 RETURN(true):
fi:

if n=2 then
if pi[1]<pi[2] then
  RETURN(true):
 else
  RETURN(false):
 fi:
fi:

if pi[1]<pi[2] and IsDU([op(2..n,pi)]) then
 RETURN(true):
 else
  RETURN(false):
fi:
end:


IsDU:=proc(pi) local n:
n:=nops(pi):

if n=1 then
 RETURN(true):
fi:

if n=2 then
if pi[1]>pi[2] then
  RETURN(true):
 else
  RETURN(false):
 fi:
fi:

if pi[1]>pi[2] and IsUD([op(2..n,pi)]) then
 RETURN(true):
 else
  RETURN(false):
fi:

end:


#UDpers(n): the set of up-down permutations of {1,...n}
UDpers:=proc(n) local A,G,pi:
A:=permute(n):
G:={}:
for pi in A do
 if IsUD(pi) then
  G:=G union {pi}:
 fi:
 od:
 G:
 end:

#DUpers(n): the set of up-down permutations of {1,...n}
DUpers:=proc(n) local A,G,pi:
A:=permute(n):
G:={}:
for pi in A do
 if IsDU(pi) then
  G:=G union {pi}:
 fi:
 od:
 G:
end:


#UDni(n,i): the number of UD permutations of {1, ...,n} that start with i
UDni:=proc(n,i) local  j:
option remember:
if n=1 then
  RETURN(1):
fi:
add(DUni(n-1,j),j=i..n-1):
end:

#DU(n,i): the number of DU permutations of {1, ...,n} that start with i
DUni:=proc(n,i) local  j:
option remember:
if n=1 then
  RETURN(1):
fi:
add(UDni(n-1,j),j=1..i-1):
end:

UDn:=proc(n) local j:
add(UDni(n,j),j=1..n):
end: