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,3

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)

Links

Table of n, a(n) for n=0..50.

Example

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.

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 *)

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.

Sequence in context: A067588 A003402 A328863 * A346634 A034748 A069916

Adjacent sequences: A218001 A218002 A218003 * A218005 A218006 A218007

Keyword

nonn

Author

Geoffrey Critzer, Oct 17 2012

Status

approved