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, 3923117, 10244069, 26746171, 69825070, 182276806, 475804961, 1241965456, 3241732629, 8461261457, 22084402087, 57640875725, 150442742575, 392652788250, 1024810764496

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

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

Formula

G.f.: (1-x)/((1-2*x)*(1-f)) where f = Sum_{k>=1} x^k/(1-x/(1-x)+x^k) is the generating function for A331330. - Christian Sievers, May 06 2025

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}]

Prog

(PARI) lista(n)=my(f=sum(k=1, n, (x^k+x*O(x^n))/(1-x/(1-x)+x^k))); Vec((1-x)/((1-2*x)*(1-f))) \\ Christian Sievers, May 06 2025

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. A011782, A022811, A032020, A063834, A133494, A181591, A323583, A331330, A336128, A336130, A336139, A355382, A355383.

Sequence in context: A248733 A099485 A038990 * A077938 A077987 A143141

Adjacent sequences: A355384 A355385 A355386 * A355388 A355389 A355390

Keyword

nonn

Author

Gus Wiseman, Jul 04 2022

Extensions

a(16) and beyond from Christian Sievers, May 06 2025

Status

approved