A384889 Number of subsets of {1..n} with all equal lengths of maximal anti-runs (increasing by more than 1).

1, 2, 4, 8, 14, 23, 37, 59, 93, 146, 230, 365, 584, 940, 1517, 2450, 3959, 6404, 10373, 16822, 27298, 44297, 71843, 116429, 188550, 305200, 493930, 799422, 1294108, 2095291, 3392736, 5493168, 8892148, 14390372, 23282110, 37660759, 60914308, 98528312, 159386110

Offset

0,2

Links

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

Formula

G.f.: ( Sum_{i>=1} (1/(1-x^(2*i-1)/(1-x)^(i-1))-1) + 1-x ) / (1-x)^2. - Christian Sievers, Jun 21 2025

Example

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

Mathematica

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

Prog

(PARI) lista(n)=Vec(sum(i=1, (n+1)\2, 1/(1-x^(2*i-1)/(1-x)^(i-1))-1, 1-x+O(x*x^n))/(1-x)^2) \\ Christian Sievers, Jun 20 2025

Crossrefs

For runs instead of anti-runs we have A243815, distinct A384175, complement A384176.

For distinct instead or equal lengths we have A384177, ranks A384879.

For partitions instead of subsets we have A384888.

A034296 counts flat or gapless partitions, ranks A066311 or A073491.

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

A047966 counts uniform partitions (equal multiplicities), ranks A072774.

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

Cf. A010027, A044813, A047993, A356606, A384880, A384886, A384890.

Sequence in context: A055291 A091773 A393514 * A107055 A202840 A018153

Adjacent sequences: A384886 A384887 A384888 * A384890 A384891 A384892

Keyword

nonn

Author

Gus Wiseman, Jun 18 2025

Extensions

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

Status

approved