login
Number of compositions of n with some part repeated.
55

%I #26 Jun 24 2020 23:33:48

%S 0,0,1,1,5,11,21,51,109,229,455,959,1947,3963,7999,16033,32333,64919,

%T 130221,260967,522733,1045825,2093855,4189547,8382315,16768455,

%U 33543127,67093261,134193413,268404995,536829045,1073686083,2147408773,4294869253,8589803783

%N Number of compositions of n with some part repeated.

%C Also compositions matching the pattern (1,1). - _Gus Wiseman_, Jun 23 2020

%H Alois P. Heinz, <a href="/A261982/b261982.txt">Table of n, a(n) for n = 0..3322</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>

%H Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>

%F a(n) = A011782(n) - A032020(n).

%F 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

%e a(2) = 1: 11.

%e a(3) = 1: 111.

%e a(4) = 5: 22, 211, 121, 112, 1111.

%p b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,

%p `if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))

%p end:

%p a:= n-> ceil(2^(n-1))-add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):

%p seq(a(n), n=0..40);

%t 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 *)

%t Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>Length[Split[#]]&]],{n,0,10}] (* _Gus Wiseman_, Jun 24 2020 *)

%Y Row sums of A261981 and of A262191.

%Y Cf. A262047.

%Y The version for patterns is A019472.

%Y The (1,1)-avoiding version is A032020.

%Y The case of partitions is A047967.

%Y (1,1,1)-matching compositions are counted by A335455.

%Y Patterns matched by compositions are counted by A335456.

%Y (1,1)-matching compositions are ranked by A335488.

%Y Cf. A011782, A056986, A106356, A181796, A238279, A269134, A333755.

%K nonn

%O 0,5

%A _Alois P. Heinz_, Sep 07 2015