cp's OEIS Frontend

A355387 Number of ways to choose a distinct subsequence of an integer composition of n.

%I A355387 #19 May 06 2025 10:04:23
%S A355387 1,2,5,14,37,98,259,682,1791,4697,12303,32196,84199,220087,575067,
%T A355387 1502176,3923117,10244069,26746171,69825070,182276806,475804961,
%U A355387 1241965456,3241732629,8461261457,22084402087,57640875725,150442742575,392652788250,1024810764496
%N A355387 Number of ways to choose a distinct subsequence of an integer composition of n.
%C A355387 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.
%H A355387 Christian Sievers, <a href="/A355387/b355387.txt">Table of n, a(n) for n = 0..2000</a>
%F A355387 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
%e A355387 The a(3) = 14 pairings of a composition with a chosen subsequence:
%e A355387   (3)()     (3)(3)
%e A355387   (21)()    (21)(1)   (21)(2)    (21)(21)
%e A355387   (12)()    (12)(1)   (12)(2)    (12)(12)
%e A355387   (111)()   (111)(1)  (111)(11)  (111)(111)
%t A355387 Table[Sum[Length[Union[Subsets[y]]],{y,Join@@Permutations/@IntegerPartitions[n]}],{n,0,6}]
%o A355387 (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
%Y A355387 For partitions we have A000712, composable A339006.
%Y A355387 The homogeneous version is A011782, without containment A000302.
%Y A355387 With multiplicity we have A025192, for partitions A070933.
%Y A355387 The strict case is A032005.
%Y A355387 The case of strict subsequences is A236002.
%Y A355387 The composable case is A355384, homogeneous without containment A355388.
%Y A355387 A075900 counts compositions of each part of a partition.
%Y A355387 A304961 counts compositions of each part of a strict partition.
%Y A355387 A307068 counts strict compositions of each part of a composition.
%Y A355387 A336127 counts compositions of each part of a strict composition.
%Y A355387 Cf. A011782, A022811, A032020, A063834, A133494, A181591, A323583, A331330, A336128, A336130, A336139, A355382, A355383.
%K A355387 nonn
%O A355387 0,2
%A A355387 _Gus Wiseman_, Jul 04 2022
%E A355387 a(16) and beyond from _Christian Sievers_, May 06 2025