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,6

Links

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

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A221749 A055967 A366110 * A202582 A292605 A338873

Adjacent sequences: A317444 A317445 A317446 * A317448 A317449 A317450

Keyword

nonn

Author

Alois P. Heinz, Jul 28 2018

Status

approved