login
Number of patterns of length n with all distinct runs.
25

%I #11 Feb 16 2022 16:03:41

%S 1,1,3,11,53,305,2051,15731,135697,1300869,13726431,158137851,

%T 1975599321,26607158781,384347911211,5928465081703,97262304328573,

%U 1691274884085061,31073791192091251,601539400910369671,12238270940611270161,261071590963047040241

%N Number of patterns of length n with all distinct runs.

%C We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217.

%H Andrew Howroyd, <a href="/A351200/b351200.txt">Table of n, a(n) for n = 0..200</a>

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/q/87559">What is a sequence run? (answered 2011-12-01)</a>

%e The a(1) = 1 through a(3) = 11 patterns:

%e (1) (1,1) (1,1,1)

%e (1,2) (1,1,2)

%e (2,1) (1,2,2)

%e (1,2,3)

%e (1,3,2)

%e (2,1,1)

%e (2,1,3)

%e (2,2,1)

%e (2,3,1)

%e (3,1,2)

%e (3,2,1)

%e The complement for n = 3 counts the two patterns (1,2,1) and (2,1,2).

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]] /@Subsets[Range[n-1]+1]];

%t Table[Length[Select[Join@@Permutations/@allnorm[n],UnsameQ@@Split[#]&]],{n,0,6}]

%o (PARI) \\ here LahI is A111596 as row polynomials.

%o LahI(n,y)={sum(k=1, n, y^k*(-1)^(n-k)*(n!/k!)*binomial(n-1, k-1))}

%o S(n)={my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); 1 + sum(i=1, (sqrtint(8*n+1)-1)\2, polcoef(p,i,y)*LahI(i,y))}

%o R(q)={[subst(serlaplace(p), y, 1) | p<-Vec(q)]}

%o seq(n)={my(q=S(n)); concat([1], sum(k=1, n, R(q^k-1)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ _Andrew Howroyd_, Feb 12 2022

%Y The version for run-lengths instead of runs is A351292.

%Y A000670 counts patterns, ranked by A333217.

%Y A005649 counts anti-run patterns, complement A069321.

%Y A005811 counts runs in binary expansion.

%Y A032011 counts patterns with distinct multiplicities.

%Y A044813 lists numbers whose binary expansion has distinct run-lengths.

%Y A060223 counts Lyndon patterns, necklaces A019536, aperiodic A296975.

%Y A131689 counts patterns by number of distinct parts.

%Y A238130 and A238279 count compositions by number of runs.

%Y A297770 counts distinct runs in binary expansion.

%Y A345194 counts alternating patterns, up/down A350354.

%Y Counting words with all distinct runs:

%Y - A351013 = compositions, for run-lengths A329739, ranked by A351290.

%Y - A351016 = binary words, for run-lengths A351017.

%Y - A351018 = binary expansions, for run-lengths A032020, ranked by A175413.

%Y - A351202 = permutations of prime factors.

%Y - A351642 = word structures.

%Y Row sums of A351640.

%Y Cf. A003242, A098504, A098859, A106356, A242882, A325545, A328592, A329740, A351014, A351204, A351291.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 09 2022

%E Terms a(10) and beyond from _Andrew Howroyd_, Feb 12 2022