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
Offset: 0
Examples
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]].
Programs
-
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)
Extensions
a(26)-a(28) from Alois P. Heinz, Aug 26 2017
Comments