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