|
%I #16 Dec 07 2019 12:18:29
%S 0,0,1,3,9,25,71,205,607,1833,5635,17577,55515,177191,570699,1852571,
%T 6055079,19910729,65823751,218654099,729459551,2443051213,8210993363,
%U 27685671843,93625082139,317470233149,1079183930827,3676951654519,12554734605495,42952566314235
%N Number of permutations p of [n] such that in 0p the largest up-jump equals 2 and no down-jump is larger than 2.
%C An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here.
%C All positive terms are odd.
%H Alois P. Heinz, <a href="/A291683/b291683.txt">Table of n, a(n) for n = 0..1000</a>
%e a(2) = 1: 21.
%e a(3) = 3: 132, 213, 231.
%e a(4) = 9: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2413, 2431.
%e a(5) = 25: 12354, 12435, 12453, 13245, 13254, 13425, 13452, 13524, 13542, 21345, 21354, 21435, 21453, 23145, 23154, 23415, 23451, 23514, 23541, 24135, 24153, 24315, 24351, 24513, 24531.
%p b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
%p add(b(u-j, o+j-1, k), j=1..min(2, u))+
%p add(b(u+j-1, o-j, k), j=1..min(k, o)))
%p end:
%p a:= n-> b(0, n, 2)-b(0, n, 1):
%p seq(a(n), n=0..30);
%t b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, k], {j, 1, Min[2, u]}] + Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];
%t a[n_] := b[0, n, 2] - b[0, n, 1];
%t Array[a, 30, 0] (* _Jean-François Alcover_, May 31 2019, from Maple *)
%o (Python)
%o from sympy.core.cache import cacheit
%o @cacheit
%o def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(2, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])
%o def a(n): return b(0, n, 2) - b(0, n, 1)
%o for n in range(31): print (a(n)) # _Indranil Ghosh_, Aug 30 2017
%Y Column k=2 of A291680.
%K nonn
%O 0,4
%A _Alois P. Heinz_, Aug 29 2017
|
