A384175 Number of subsets of {1..n} with all distinct lengths of maximal runs (increasing by 1).

1, 2, 4, 7, 13, 24, 44, 77, 135, 236, 412, 713, 1215, 2048, 3434, 5739, 9559, 15850, 26086, 42605, 69133, 111634, 179602, 288069, 460553, 733370, 1162356, 1833371, 2878621, 4501856, 7016844, 10905449, 16904399, 26132460, 40279108, 61885621, 94766071, 144637928

Offset: 0

Author

Gus Wiseman, Jun 16 2025

Keywords

• nonn

Examples

			The subset {2,3,5,6,7,9} has maximal runs ((2,3),(5,6,7),(9)), with lengths (2,3,1), so is counted under a(9).
The a(0) = 1 through a(4) = 13 subsets:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {2}    {2}      {2}
           {1,2}  {3}      {3}
                  {1,2}    {4}
                  {2,3}    {1,2}
                  {1,2,3}  {2,3}
                           {3,4}
                           {1,2,3}
                           {1,2,4}
                           {1,3,4}
                           {2,3,4}
                           {1,2,3,4}
		

Links

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

Crossrefs

For equal instead of distinct lengths we have A243815.

These subsets are ranked by A328592.

The complement is counted by A384176.

For anti-runs instead of runs we have A384177, ranks A384879.

For partitions instead of subsets we have A384884, A384178, A384886, A384880.

For permutations instead of subsets we have A384891, equal instead of distinct A384892.

A034839 counts subsets by number of maximal runs, for strict partitions A116674.

A098859 counts Wilf partitions (distinct multiplicities), complement A336866.

A384893 counts subsets by number of maximal anti-runs, for partitions A268193, A384905.

Cf. A000009, A010027, A044813, A047993, A242882, A325325, A329739, A351202, A383013, A384889, A384890.

Programs

Mathematica

Table[Length[Select[Subsets[Range[n]],UnsameQ@@Length/@Split[#,#2==#1+1&]&]],{n,0,10}]

PARI

lista(n)={my(o=(1-x^(n+1))/(1-x)*O(y^(n+2)),p=prod(i=1,n,1+o+x*y^(i+1)/(1-y),1/(1-y)));p=subst(serlaplace(p),x,1);Vec(p-1)} \\ Christian Sievers, Jun 18 2025

Extensions

a(21) and beyond from Christian Sievers, Jun 18 2025