cp's OEIS Frontend

A218004 Number of equivalence classes of compositions of n where two compositions a,b are considered equivalent if the summands of a can be permuted into the summands of b with an even number of transpositions.

%I A218004 #22 Oct 21 2020 22:47:39
%S A218004 1,1,2,4,6,9,14,19,27,37,51,67,91,118,156,202,262,334,430,543,690,867,
%T A218004 1090,1358,1696,2099,2600,3201,3939,4820,5899,7181,8738,10590,12821,
%U A218004 15467,18644,22396,26878,32166,38450,45842,54599,64870,76990,91181,107861,127343,150182,176788,207883
%N A218004 Number of equivalence classes of compositions of n where two compositions a,b are considered equivalent if the summands of a can be permuted into the summands of b with an even number of transpositions.
%C A218004 a(n) = A000041(n) + A000009(n) - 1  where A000041 is the partition numbers and A000009 is the number of partitions into distinct parts.
%C A218004 From _Gus Wiseman_, Oct 14 2020: (Start)
%C A218004 Also the number of compositions of n that are either strictly increasing or weakly decreasing. For example, the a(1) = 1 through a(6) = 14 compositions are:
%C A218004   (1)  (2)   (3)    (4)     (5)      (6)
%C A218004        (11)  (12)   (13)    (14)     (15)
%C A218004              (21)   (22)    (23)     (24)
%C A218004              (111)  (31)    (32)     (33)
%C A218004                     (211)   (41)     (42)
%C A218004                     (1111)  (221)    (51)
%C A218004                             (311)    (123)
%C A218004                             (2111)   (222)
%C A218004                             (11111)  (321)
%C A218004                                      (411)
%C A218004                                      (2211)
%C A218004                                      (3111)
%C A218004                                      (21111)
%C A218004                                      (111111)
%C A218004 A007997 counts only compositions of length 3.
%C A218004 A329398 appears to be the weakly increasing version.
%C A218004 A333147 is the strictly decreasing version.
%C A218004 A333255 union A114994 ranks these compositions using standard compositions (A066099).
%C A218004 A337482 counts the complement.
%C A218004 (End)
%e A218004 a(4) = 6 because the 6 classes can be represented by: 4, 3+1, 1+3, 2+2, 2+1+1, 1+1+1+1.
%t A218004 nn=50;p=CoefficientList[Series[Product[1/(1-x^i),{i,1,nn}],{x,0,nn}],x];d= CoefficientList[Series[Sum[Product[x^i/(1-x^i),{i,1,k}],{k,0,nn}],{x,0,nn}],x];p+d-1
%t A218004 (* second program *)
%t A218004 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Less@@#||GreaterEqual@@#&]],{n,0,15}] (* _Gus Wiseman_, Oct 14 2020 *)
%Y A218004 A000009 counts strictly increasing compositions, ranked by A333255.
%Y A218004 A000041 counts weakly decreasing compositions, ranked by A114994.
%Y A218004 A001523 counts unimodal compositions (strict: A072706).
%Y A218004 A007318 and A097805 count compositions by length.
%Y A218004 A032020 counts strict compositions, ranked by A233564.
%Y A218004 A332834 counts compositions not increasing nor decreasing (strict: A333149).
%Y A218004 Cf. A115981, A225620, A332578, A332833, A332874, A333150, A333190, A333191, A333256, A337483, A337484.
%K A218004 nonn
%O A218004 0,3
%A A218004 _Geoffrey Critzer_, Oct 17 2012