A291551 Number of permutations s_1,s_2,...,s_n of 1,2,...,n such that for all j=1,2,...,n, Sum_{i=1..j} s_i divides Product_{i=1..j} s_i.

1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26, 0, 262, 0, 10226, 43964, 139484, 0, 13936472, 59652396, 301235944, 1915640632, 7969506364, 0, 465804291196, 0

Offset

0,16

Comments

a(n) = 0 if n+1 does not divide 2*(n-1)!. This implies that a(p-1) = 0 for p > 2 prime. - Chai Wah Wu, Aug 26 2017

Links

Table of n, a(n) for n=0..30.

Example

a(15) = 26: [[10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 3, 7, 1, 9, 12], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 7, 1, 9, 4, 8], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 9, 4, 1, 7, 8], [10, 15, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 7, 1, 9, 4, 8], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 9, 4, 1, 7, 8], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 3, 7, 1, 9, 12], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 7, 1, 9, 4, 8], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 9, 4, 1, 7, 8], [15, 10, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 7, 1, 9, 4, 8], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 9, 4, 1, 7, 8]].

Prog

(Ruby)
def search(a, prod, sum, size, num)
  if num == size + 1
    @cnt += 1
  else
    (1..size).each{|i|
      p, s = prod * i, sum + i
      if a[i - 1] == 0 && p % s == 0
        a[i - 1] = 1
        search(a, p, s, size, num + 1)
        a[i - 1] = 0
      end
    }
  end
end
def A(n)
  a = [0] * n
  @cnt = 0
  search(a, 1, 0, n, 1)
  @cnt
end
def A291551(n)
  (0..n).map{|i| A(i)}
end
p A291551(20)
(Python)
from functools import cache
from math import prod
def a(n):
    @cache
    def c(t, s, p): # count valid permutations where items in t must be placed, sum is s, prod is p
        if s and p%s: return 0
        if len(t) == 0: return 1
        S = set(t)
        return sum(c(tuple(sorted(S-{i})), s+i, p*i) for i in t)
    if n == 0 or prod(range(1, n+1))%sum(range(1, n+1)): return int(n == 0)
    return c(tuple(range(1, n+1)), 0, 1)
print([a(n) for n in range(25)]) # Michael S. Branicky, May 02 2026

Crossrefs

Cf. A060462, A126328.

Sequence in context: A116197 A023924 A022066 * A217232 A040681 A040682

Adjacent sequences: A291548 A291549 A291550 * A291552 A291553 A291554

Keyword

nonn,more

Author

Seiichi Manyama, Aug 26 2017

Extensions

a(26)-a(28) from Alois P. Heinz, Aug 26 2017

a(29)-a(30) from Michael S. Branicky, May 02 2026

Status

approved