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

Author

Gus Wiseman, Jul 04 2022

Keywords

• nonn

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.

Examples

			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)
		

Links

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

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.

Programs

Mathematica

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

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

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

Extensions

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