OFFSET
0,3
COMMENTS
a(n^2) is odd. -Gregory L. Simay,Jun 23 2019
Also the number of compositions of n avoiding the patterns (1,2,1) and (2,1,2). -Gus Wiseman,Jul 07 2020
LINKS
Alois P. Heinz,Table of n, a(n) for n = 0..5000
FORMULA
a(n) = Sum_{k>=0} k! *A116608(n,k). -Joerg Arndt,Jun 12 2016
EXAMPLE
If the summand runs are blocked together, there are 22 compositions of a(6): 6; 5+1, 1+5, 4+2, 2+4, (3+3), 4+(1+1), (1+1)+4, 1+2+3, 1+3+2, 2+1+3, 2+3+1, 3+1+2, 3+2+1, (2+2+2), 3+(1+1+1), (1+1+1)+3, (2+2)+(1+1), (1+1)+(2+2), 2+(1+1+1+1), (1+1+1+1)+2, (1+1+1+1+1+1).
a(0)=1; a(1)= 1; a(4) = 7; a(9) = 97; a(16) = 2305; a(25) = 78113 and a(36) = 3536445. -Gregory L. Simay,Jun 23 19
MAPLE
b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50); #Alois P. Heinz,Jun 12 2016
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[Split[#]]==Length[Union[#]]&]], {n, 0, 10}] (*Gus Wiseman,Jul 07 2020 *)
b[n_, i_, p_]:= b[n, i, p] = If[n == 0, p!, If[i < 1, 0,
Sum[b[n - i*j, i - 1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
a[n_]:= b[n, n, 0];
Table[a[n], {n, 0, 50}] (*Jean-François Alcover,Jul 11 2021, afterAlois P. Heinz*)
CROSSREFS
The version for patterns isA001339.
The version for prime indices isA333175.
The complement (i.e., the matching version) isA335548.
Anti-run compositions areA003242.
(1,2,1)- and (2,1,2)-matching permutations of prime indices areA335462.
(1,2,1)-matching compositions areA335470.
(1,2,1)-avoiding compositions areA335471.
(2,1,2)-matching compositions areA335472.
(2,1,2)-avoiding compositions areA335473.
KEYWORD
nonn
AUTHOR
Gregory L. Simay,Jun 12 2016
EXTENSIONS
Terms a(9) and beyond fromJoerg Arndt,Jun 12 2016
STATUS
approved