cp's OEIS Frontend

A056823 Number of compositions minus number of partitions: A011782(n) - A000041(n).

%I A056823 #55 Jul 02 2025 16:02:00
%S A056823 0,0,0,1,3,9,21,49,106,226,470,968,1971,3995,8057,16208,32537,65239,
%T A056823 130687,261654,523661,1047784,2096150,4193049,8387033,16775258,
%U A056823 33551996,67105854,134214010,268430891,536865308,1073734982,2147475299,4294957153,8589922282
%N A056823 Number of compositions minus number of partitions: A011782(n) - A000041(n).
%C A056823 Previous name was: Counts members of A056808 by number of factors.
%C A056823 A056808 relates to least prime signatures (cf. A025487)
%C A056823 a(n) is also the number of compositions of n that are not partitions of n. - _Omar E. Pol_, Jan 31 2009, Oct 14 2013
%C A056823 a(n) is the number of compositions of n into positive parts containing pattern [1,2]. - _Bob Selcoe_, Jul 08 2014
%H A056823 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A056823 Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F A056823 a(n) = A011782(n) - A000041(n).
%F A056823 a(n) = 2*a(n-1) + A117989(n-1). - _Bob Selcoe_, Apr 11 2014
%F A056823 G.f.: (1 - x) / (1 - 2*x) - Product_{k>=1} 1 / (1 - x^k). - _Ilya Gutkovskiy_, Jan 30 2020
%e A056823 A011782 begins     1 1 2 4 8 16 32 64 128 256 ...;
%e A056823 A000041 begins     1 1 2 3 5  7 11 15  22  30 ...;
%e A056823 so sequence begins 0 0 0 1 3  9 21 49 106 226 ... .
%e A056823 For n = 3 the factorizations are 8=2*2*2, 12=2*2*3, 18=2*3*3 and 30=2*3*5.
%e A056823 a(5) = 9: {[1,1,1,2], [1,1,2,1], [1,1,3], [1,2,1,1], [1,2,2], [1,3,1], [1,4], [2,1,2], [2,3]}. - _Bob Selcoe_, Jul 08 2014
%p A056823 a:= n-> ceil(2^(n-1))-combinat[numbpart](n):
%p A056823 seq(a(n), n=0..37);  # _Alois P. Heinz_, Jan 30 2020
%t A056823 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!GreaterEqual@@#&]],{n,0,10}] (* _Gus Wiseman_, Jun 24 2020 *)
%t A056823 a[n_] := If[n == 0, 0, 2^(n-1) - PartitionsP[n]];
%t A056823 a /@ Range[0, 37] (* _Jean-François Alcover_, May 23 2021 *)
%Y A056823 Cf. A025487, A056808, A117989.
%Y A056823 The version for patterns is A002051.
%Y A056823 (1,2)-avoiding compositions are just partitions A000041.
%Y A056823 The (1,1)-matching version is A261982.
%Y A056823 The version for prime indices is A335447.
%Y A056823 (1,2)-matching compositions are ranked by A335485.
%Y A056823 Patterns matched by compositions are counted by A335456.
%Y A056823 Cf. A011782, A056986, A106356, A144300, A238279, A269134, A333755.
%K A056823 easy,nonn
%O A056823 0,5
%A A056823 _Alford Arnold_, Aug 29 2000
%E A056823 More terms from _James Sellers_, Aug 31 2000
%E A056823 New name from _Joerg Arndt_, Sep 02 2013