A355387 Number of ways to choose a distinct subsequence of an integer composition of n.

1, 2, 5, 14, 37, 98, 259, 682, 1791, 4697, 12303, 32196, 84199, 220087, 575067, 1502176

Offset

0,2

Comments

By "distinct" we mean equal subsequences are counted only once. For example, the pair (1,1)(1) is counted only once even though (1) is a subsequence of (1,1) in two ways. The version with multiplicity is A025192.

Links

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

Example

The a(3) = 14 pairings of a composition with a chosen subsequence:
  (3)()     (3)(3)
  (21)()    (21)(1)   (21)(2)    (21)(21)
  (12)()    (12)(1)   (12)(2)    (12)(12)
  (111)()   (111)(1)  (111)(11)  (111)(111)

Mathematica

Table[Sum[Length[Union[Subsets[y]]], {y, Join@@Permutations/@IntegerPartitions[n]}], {n, 0, 6}]

Crossrefs

For partitions we have A000712, composable A339006.

The homogeneous version is A011782, without containment A000302.

With multiplicity we have A025192, for partitions A070933.

The strict case is A032005.

The case of strict subsequences is A236002.

The composable case is A355384, homogeneous without containment A355388.

A075900 counts compositions of each part of a partition.

A304961 counts compositions of each part of a strict partition.

A307068 counts strict compositions of each part of a composition.

A336127 counts compositions of each part of a strict composition.

Cf. A022811, A032020, A063834, A133494, A181591, A323583, A336128, A336130, A336139, A355382, A355383.

Sequence in context: A248733 A099485 A038990 * A077938 A077987 A143141

Adjacent sequences: A355384 A355385 A355386 * A355388 A355389 A355390

Keyword

nonn,more

Author

Gus Wiseman, Jul 04 2022

Status

approved