|
|
A361648
|
|
Number of permutations p of [n] such that p(i), p(i+2), p(i+4),... form an up-down sequence for i in {1,2}.
|
|
2
|
|
|
1, 1, 2, 3, 6, 20, 80, 350, 1750, 10080, 64512, 450912, 3438204, 28471872, 253913088, 2424193200, 24687555750, 267199961600, 3062092267520, 37037541651968, 471565937953396, 6304419553216512, 88298062293762048, 1292879475255280640, 19753693667117055100
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Number of permutations p of [n] such that p(i) < p(i+2) > p(i+4) < ... for i <= 2.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
a(0) = 1: (), the empty permutation.
a(1) = 1: 1.
a(2) = 2: 12, 21.
a(3) = 3: 123, 132, 213.
a(4) = 6: 1234, 1243, 1324, 2134, 2143, 3142.
a(5) = 20: 12453, 12534, 12543, 13452, 13542, 14352, 21453, 21534, 21543, 23451, 23541, 24351, 31452, 31524, 31542, 32451, 32541, 41523, 41532, 42531.
a(6) = 80: 124635, 125634, 125643, 126453, ..., 526413, 526431, 536412, 536421.
|
|
MAPLE
|
b:= proc(u, o) option remember; `if`(u+o=0, 1,
add(b(o-1+j, u-j), j=1..u))
end:
a:= n-> (h-> b(h, 0)*b(n-h, 0)*binomial(n, h))(iquo(n, 2)):
seq(a(n), n=0..30);
|
|
MATHEMATICA
|
b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[o-1+j, u-j], {j, 1, u}]];
a[n_] := With[{h = Quotient[n, 2]}, b[h, 0] b[n-h, 0] Binomial[n, h]];
|
|
PROG
|
(Python)
from math import comb
from itertools import accumulate
if n<=1:
return 1
blist = (0, 1)
for _ in range((m:=n>>1)-1):
blist = tuple(accumulate(reversed(blist), initial=0))
return blist[-1]*sum(blist)*comb(n, m) if n&1 else blist[-1]**2*comb(n, m) # Chai Wah Wu, Apr 16 2023
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|