A317131 Number of permutations of [n] whose lengths of increasing runs are prime numbers.

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

Alois P. Heinz, Table of n, a(n) for n = 0..400

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

Crossrefs

Cf. A000040, A097597, A218002, A317111, A317128, A317129, A317130, A317132, A317447.

Sequence in context: A146030 A098041 A346817 * A149780 A149781 A149782

Adjacent sequences: A317128 A317129 A317130 * A317132 A317133 A317134

Keyword

nonn

Author

Alois P. Heinz, Jul 21 2018

Status

approved