login
A317131
Number of permutations of [n] whose lengths of increasing runs are prime numbers.
7
1, 0, 1, 1, 5, 19, 80, 520, 2898, 22486, 171460, 1509534, 14446457, 147241144, 1650934446, 19494460567, 248182635904, 3340565727176, 47659710452780, 718389090777485, 11381176852445592, 189580213656445309, 3305258537062221020, 60273557241570401742
OFFSET
0,5
LINKS
EXAMPLE
a(2) = 1: 12.
a(3) = 1: 123.
a(4) = 5: 1324, 1423, 2314, 2413, 3412.
a(5) = 19: 12345, 12435, 12534, 13245, 13425, 13524, 14235, 14523, 15234, 23145, 23415, 23514, 24135, 24513, 25134, 34125, 34512, 35124, 45123.
MAPLE
g:= n-> `if`(n=0 or isprime(n), 1, 0):
b:= proc(u, o, t) option remember; `if`(u+o=0, g(t),
`if`(g(t)=1, add(b(u-j, o+j-1, 1), j=1..u), 0)+
add(b(u+j-1, o-j, t+1), j=1..o))
end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..27);
MATHEMATICA
g[n_] := If[n == 0 || PrimeQ[n], 1, 0];
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, g[t],
If[g[t] == 1, Sum[b[u - j, o + j - 1, 1], {j, 1, u}], 0] +
Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 27] (* Jean-François Alcover, Mar 29 2021, after Alois P. Heinz *)
PROG
(Python)
from functools import lru_cache
from sympy import isprime
def g(n): return int(n == 0 or isprime(n))
@lru_cache(maxsize=None)
def b(u, o, t):
if u + o == 0: return g(t)
return (sum(b(u-j, o+j-1, 1) for j in range(1, u+1)) if g(t) else 0) +\
sum(b(u+j-1, o-j, t+1) for j in range(1, o+1))
def a(n): return b(n, 0, 0)
print([a(n) for n in range(28)]) # Michael S. Branicky, Mar 29 2021 after Alois P. Heinz
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 21 2018
STATUS
approved