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,2

Links

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

Example

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}

Mathematica

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

Prog

(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

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.

Sequence in context: A128742 A318748 A107281 * A006744 A054175 A305442

Adjacent sequences: A384172 A384173 A384174 * A384176 A384177 A384178

Keyword

nonn

Author

Gus Wiseman, Jun 16 2025

Extensions

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

Status

approved