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

Author

Gus Wiseman, Jul 01 2022

Keywords

• nonn

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.

Examples

			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)
		

Links

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

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.

Programs

Mathematica

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

Extensions

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