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, after Alois P. Heinz *)
CROSSREFS
The version for patterns is A001339.
The version for prime indices is A333175.
The complement (i.e., the matching version) is A335548.
Anti-run compositions are A003242.
(1,2,1)- and (2,1,2)-matching permutations of prime indices are A335462.
(1,2,1)-matching compositions are A335470.
(1,2,1)-avoiding compositions are A335471.
(2,1,2)-matching compositions are A335472.
(2,1,2)-avoiding compositions are A335473.
KEYWORD
nonn
AUTHOR
Gregory L. Simay, Jun 12 2016
EXTENSIONS
Terms a(9) and beyond from Joerg Arndt, Jun 12 2016
STATUS
approved