cp's OEIS Frontend

A261982 Number of compositions of n with some part repeated.

%I A261982 #26 Jun 24 2020 23:33:48
%S A261982 0,0,1,1,5,11,21,51,109,229,455,959,1947,3963,7999,16033,32333,64919,
%T A261982 130221,260967,522733,1045825,2093855,4189547,8382315,16768455,
%U A261982 33543127,67093261,134193413,268404995,536829045,1073686083,2147408773,4294869253,8589803783
%N A261982 Number of compositions of n with some part repeated.
%C A261982 Also compositions matching the pattern (1,1). - _Gus Wiseman_, Jun 23 2020
%H A261982 Alois P. Heinz, <a href="/A261982/b261982.txt">Table of n, a(n) for n = 0..3322</a>
%H A261982 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A261982 Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F A261982 a(n) = A011782(n) - A032020(n).
%F A261982 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 A261982 a(2) = 1: 11.
%e A261982 a(3) = 1: 111.
%e A261982 a(4) = 5: 22, 211, 121, 112, 1111.
%p A261982 b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
%p A261982       `if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))
%p A261982     end:
%p A261982 a:= n-> ceil(2^(n-1))-add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
%p A261982 seq(a(n), n=0..40);
%t A261982 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 A261982 Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>Length[Split[#]]&]],{n,0,10}] (* _Gus Wiseman_, Jun 24 2020 *)
%Y A261982 Row sums of A261981 and of A262191.
%Y A261982 Cf. A262047.
%Y A261982 The version for patterns is A019472.
%Y A261982 The (1,1)-avoiding version is A032020.
%Y A261982 The case of partitions is A047967.
%Y A261982 (1,1,1)-matching compositions are counted by A335455.
%Y A261982 Patterns matched by compositions are counted by A335456.
%Y A261982 (1,1)-matching compositions are ranked by A335488.
%Y A261982 Cf. A011782, A056986, A106356, A181796, A238279, A269134, A333755.
%K A261982 nonn
%O A261982 0,5
%A A261982 _Alois P. Heinz_, Sep 07 2015