OFFSET
0,5
COMMENTS
Also compositions matching the pattern (1,1). - Gus Wiseman, Jun 23 2020
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..3322
Wikipedia, Permutation pattern
FORMULA
G.f.: (1 - x) / (1 - 2*x) - Sum_{k>=0} k! * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j). - Ilya Gutkovskiy, Jan 30 2020
EXAMPLE
a(2) = 1: 11.
a(3) = 1: 111.
a(4) = 5: 22, 211, 121, 112, 1111.
MAPLE
b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
`if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))
end:
a:= n-> ceil(2^(n-1))-add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..40);
MATHEMATICA
b[n_, k_] := b[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], b[n-k, k] + k*b[n-k, k-1]]]; a[n_] := Ceiling[2^(n-1)]-Sum[b[n, k], {k, 0, Floor[ (Sqrt[8n+1]-1)/2]}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 08 2017, translated from Maple *)
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n], Length[#]>Length[Split[#]]&]], {n, 0, 10}] (* Gus Wiseman, Jun 24 2020 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Sep 07 2015
STATUS
approved