A355384 Number of pairs (y, v) where y is a composition of n and v is a (not necessarily contiguous) subsequence of y whose length equals the number of distinct parts in y.

1, 1, 2, 4, 12, 30, 66, 164, 419, 1049, 2625, 6372, 15451, 37335, 89855, 216523, 518714, 1235897, 2930050, 6911149, 16217817, 37914515, 88304358, 204971388, 474172899, 1093547574, 2513959446, 5761735383, 13165908506, 29998936859, 68164839887, 154478212575

Offset

0,3

Comments

If a composition is regarded as an arrow from the number of parts to the number of distinct parts, this sequence counts composable containments of compositions.

Links

Christian Sievers, Table of n, a(n) for n = 0..59

Example

The initial terms count the following containments:
  ()()  (1)(1)  (2)(2)   (3)(3)    (4)(4)
                (11)(1)  (21)(21)  (31)(31)
                         (12)(12)  (13)(13)
                         (111)(1)  (22)(2)
                                   (211)(11)
                                   (211)(21)
                                   (121)(11)
                                   (121)(12)
                                   (121)(21)
                                   (112)(11)
                                   (112)(12)
                                   (1111)(1)

Mathematica

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

Crossrefs

The homog. case is A032020, w/o containment A355388 (partitions A355385).

For partitions we have A355383, homog. A000009, w/ multiplicity A339006.

A000244 counts splittings of compositions, for partitions A323583.

Cf. A001970, A022811, A063834, A070933, A072706, A133494, A336139.

Sequence in context: A130135 A048618 A083554 * A059412 A079472 A366590

Adjacent sequences: A355381 A355382 A355383 * A355385 A355386 A355387

Keyword

nonn

Author

Gus Wiseman, Jul 01 2022

Extensions

a(21) and beyond from Christian Sievers, May 08 2025

Status

approved