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

Author

Gus Wiseman, Jul 04 2025

Keywords

• nonn

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.

Examples

			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}
		

Links

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

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.

Programs

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}]

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

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

Extensions

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