login
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.
9

%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