login
A355387
Number of ways to choose a distinct subsequence of an integer composition of n.
1
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.
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.
Sequence in context: A248733 A099485 A038990 * A077938 A077987 A143141
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jul 04 2022
STATUS
approved