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

1, 0, 1, 1, 0, 19, 0, 41, 110, 70, 13696, 1, 44796, 155, 411064, 2122802, 251746, 1057634441, 4404368, 25043183, 44848672, 19725545894, 106293316, 307873058001, 50194102, 8305023165502, 65808841818130, 33715371370134, 115625740201672616, 78940089764191

Offset: 0

Author

Alois P. Heinz, Jul 28 2018

Keywords

• nonn

Links

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

Crossrefs

Cf. A000040, A317131, A317444, A317445, A317446, A317448.

Programs

Maple

g:= (n, s)-> `if`(n in s or not (n=0 or isprime(n)), 0, 1):
b:= proc(u, o, t, s) option remember; `if`(u+o=0, g(t, s),
      `if`(g(t, s)=1, add(b(u-j, o+j-1, 1, s union {t})
       , j=1..u), 0)+ add(b(u+j-1, o-j, t+1, s), j=1..o))
    end:
a:= n-> b(n, 0$2, {}):
seq(a(n), n=0..40);

Mathematica

g[n_, s_] := If[MemberQ[s, n] || Not [n == 0 || PrimeQ[n]], 0, 1];
b[u_, o_, t_, s_] := b[u, o, t, s] = If[u + o == 0, g[t, s],
     If[g[t, s] == 1, Sum[b[u - j, o + j - 1, 1, s ~Union~ {t}],
     {j, 1, u}], 0] + Sum[b[u + j - 1, o - j, t + 1, s], {j, 1, o}]];
a[n_] := b[n, 0, 0, {}];
a /@ Range[0, 40] (* Jean-François Alcover, Mar 29 2021, after Alois P. Heinz *)

Python

from functools import lru_cache
from sympy import isprime
def g(n, s): return int((n == 0 or isprime(n)) and not n in s)
@lru_cache(maxsize=None)
def b(u, o, t, s):
  if u + o == 0: return g(t, s)
  c1 = sum(b(u-j, o+j-1, 1, tuple(sorted(s+(t,)))) for j in range(1, u+1)) if g(t, s) else 0
  return c1 + sum(b(u+j-1, o-j, t+1, s) for j in range(1, o+1))
def a(n): return b(n, 0, 0, tuple())
print([a(n) for n in range(41)]) # Michael S. Branicky, Mar 29 2021 after Alois P. Heinz