A385572 Number of subsets of {1..n} with the same number of maximal runs (increasing by 1) as maximal anti-runs (increasing by more than 1).

1, 2, 3, 4, 7, 12, 19, 34, 63, 112, 207, 394, 739, 1398, 2687, 5152, 9891, 19128, 37039, 71754, 139459, 271522, 528999, 1032308, 2017291, 3945186, 7723203, 15134440, 29679407, 58245068, 114389683, 224796210, 442021743, 869658304, 1711914351, 3371515306

Offset

0,2

Comments

Also the number of subsets of {1..n} with the same number of adjacent elements increasing by 1 as adjacent elements increasing by more than 1.

Links

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

Formula

Let M be the matrix [1,0,0; 1,x,1/x; 0,1,1]. Then a(n) is the sum of the constant terms of the entries in the left column of M^n. - Christian Sievers, Jul 06 2025

Example

The set {2,3,5,6,8} has maximal runs ((2,3),(5,6),(8)) and maximal anti-runs ((2),(3,5),(6,8)) so is counted under a(8).
The a(0) = 1 through a(6) = 19 subsets:
  {}  {}   {}   {}   {}       {}       {}
      {1}  {1}  {1}  {1}      {1}      {1}
           {2}  {2}  {2}      {2}      {2}
                {3}  {3}      {3}      {3}
                     {4}      {4}      {4}
                     {1,2,4}  {5}      {5}
                     {1,3,4}  {1,2,4}  {6}
                              {1,2,5}  {1,2,4}
                              {1,3,4}  {1,2,5}
                              {1,4,5}  {1,2,6}
                              {2,3,5}  {1,3,4}
                              {2,4,5}  {1,4,5}
                                       {1,5,6}
                                       {2,3,5}
                                       {2,3,6}
                                       {2,4,5}
                                       {2,5,6}
                                       {3,4,6}
                                       {3,5,6}

Maple

a:= proc(n) option remember; `if`(n<5, [1, 2, 3, 4, 7][n+1], ((3*n-4)*a(n-1)-
      (3*n-5)*a(n-2)+(5*n-12)*a(n-3)-2*(4*n-11)*a(n-4)+4*(n-3)*a(n-5))/(n-1))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Jul 06 2025

Mathematica

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

Prog

(PARI) a(n)=polcoef([1, 1, 1]*[x, 0, 0; x, x^2, 1; 0, x, x]^n*[1, 0, 0]~, n) \\ Christian Sievers, Jul 06 2025

Crossrefs

The LHS is counted by A034839 (for partitions A384881, strict A116674), rank statistic A069010.

The case containing n + 1 is A217615.

The RHS is counted by A384893 or A210034 (for partitions A268193, strict A384905), rank statistic A384890.

Subsets of this type are ranked by A385575.

A384175 counts subsets with all distinct lengths of maximal runs, complement A384176.

A384877 gives lengths of maximal anti-runs in binary indices, firsts A384878.

Cf. A000071, A000079, A001629, A010027, A053538, A384177, A384879, A384889.

Sequence in context: A216604 A211695 A261396 * A357532 A018148 A084972

Adjacent sequences: A385569 A385570 A385571 * A385573 A385574 A385575

Keyword

nonn

Author

Gus Wiseman, Jul 04 2025

Extensions

a(21) and beyond from Christian Sievers, Jul 06 2025

Status

approved