cp's OEIS Frontend

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).

%I A385572 #16 Jul 07 2025 12:04:33
%S A385572 1,2,3,4,7,12,19,34,63,112,207,394,739,1398,2687,5152,9891,19128,
%T A385572 37039,71754,139459,271522,528999,1032308,2017291,3945186,7723203,
%U A385572 15134440,29679407,58245068,114389683,224796210,442021743,869658304,1711914351,3371515306
%N 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).
%C A385572 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.
%H A385572 Christian Sievers, <a href="/A385572/b385572.txt">Table of n, a(n) for n = 0..3328</a>
%F A385572 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
%e A385572 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).
%e A385572 The a(0) = 1 through a(6) = 19 subsets:
%e A385572   {}  {}   {}   {}   {}       {}       {}
%e A385572       {1}  {1}  {1}  {1}      {1}      {1}
%e A385572            {2}  {2}  {2}      {2}      {2}
%e A385572                 {3}  {3}      {3}      {3}
%e A385572                      {4}      {4}      {4}
%e A385572                      {1,2,4}  {5}      {5}
%e A385572                      {1,3,4}  {1,2,4}  {6}
%e A385572                               {1,2,5}  {1,2,4}
%e A385572                               {1,3,4}  {1,2,5}
%e A385572                               {1,4,5}  {1,2,6}
%e A385572                               {2,3,5}  {1,3,4}
%e A385572                               {2,4,5}  {1,4,5}
%e A385572                                        {1,5,6}
%e A385572                                        {2,3,5}
%e A385572                                        {2,3,6}
%e A385572                                        {2,4,5}
%e A385572                                        {2,5,6}
%e A385572                                        {3,4,6}
%e A385572                                        {3,5,6}
%p A385572 a:= proc(n) option remember; `if`(n<5, [1, 2, 3, 4, 7][n+1], ((3*n-4)*a(n-1)-
%p A385572       (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))
%p A385572     end:
%p A385572 seq(a(n), n=0..35);  # _Alois P. Heinz_, Jul 06 2025
%t A385572 Table[Length[Select[Subsets[Range[n]],Length[Split[#,#2==#1+1&]]==Length[Split[#,#2!=#1+1&]]&]],{n,0,10}]
%o A385572 (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
%Y A385572 The LHS is counted by A034839 (for partitions A384881, strict A116674), rank statistic A069010.
%Y A385572 The case containing n + 1 is A217615.
%Y A385572 The RHS is counted by A384893 or A210034 (for partitions A268193, strict A384905), rank statistic A384890.
%Y A385572 Subsets of this type are ranked by A385575.
%Y A385572 A384175 counts subsets with all distinct lengths of maximal runs, complement A384176.
%Y A385572 A384877 gives lengths of maximal anti-runs in binary indices, firsts A384878.
%Y A385572 Cf. A000071, A000079, A001629, A010027, A053538, A384177, A384879, A384889.
%K A385572 nonn
%O A385572 0,2
%A A385572 _Gus Wiseman_, Jul 04 2025
%E A385572 a(21) and beyond from _Christian Sievers_, Jul 06 2025