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.

1, 1, 2, 4, 6, 9, 14, 19, 27, 37, 51, 67, 91, 118, 156, 202, 262, 334, 430, 543, 690, 867, 1090, 1358, 1696, 2099, 2600, 3201, 3939, 4820, 5899, 7181, 8738, 10590, 12821, 15467, 18644, 22396, 26878, 32166, 38450, 45842, 54599, 64870, 76990, 91181, 107861, 127343, 150182, 176788, 207883

Offset: 0

Author

Geoffrey Critzer, Oct 17 2012

Keywords

• nonn

Comments

a(n) = A000041(n) + A000009(n) - 1 where A000041 is the partition numbers and A000009 is the number of partitions into distinct parts.

From Gus Wiseman, Oct 14 2020: (Start)

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:

(1) (2) (3) (4) (5) (6)

(11) (12) (13) (14) (15)

(21) (22) (23) (24)

(111) (31) (32) (33)

(211) (41) (42)

(1111) (221) (51)

(311) (123)

(2111) (222)

(11111) (321)

(411)

(2211)

(3111)

(21111)

(111111)

A007997 counts only compositions of length 3.

A329398 appears to be the weakly increasing version.

A333147 is the strictly decreasing version.

A333255 union A114994 ranks these compositions using standard compositions (A066099).

A337482 counts the complement.

(End)

Examples

			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.
		

Crossrefs

A000009 counts strictly increasing compositions, ranked by A333255.

A000041 counts weakly decreasing compositions, ranked by A114994.

A001523 counts unimodal compositions (strict: A072706).

A007318 and A097805 count compositions by length.

A032020 counts strict compositions, ranked by A233564.

A332834 counts compositions not increasing nor decreasing (strict: A333149).

Cf. A115981, A225620, A332578, A332833, A332874, A333150, A333190, A333191, A333256, A337483, A337484.

Programs

Mathematica

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
(* second program *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Less@@#||GreaterEqual@@#&]],{n,0,15}] (* Gus Wiseman, Oct 14 2020 *)