A351200 Number of patterns of length n with all distinct runs.

1, 1, 3, 11, 53, 305, 2051, 15731, 135697, 1300869, 13726431, 158137851, 1975599321, 26607158781, 384347911211, 5928465081703, 97262304328573, 1691274884085061, 31073791192091251, 601539400910369671, 12238270940611270161, 261071590963047040241

Offset: 0

Author

Gus Wiseman, Feb 09 2022

Keywords

• nonn

Comments

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.

Examples

			The a(1) = 1 through a(3) = 11 patterns:
  (1)  (1,1)  (1,1,1)
       (1,2)  (1,1,2)
       (2,1)  (1,2,2)
              (1,2,3)
              (1,3,2)
              (2,1,1)
              (2,1,3)
              (2,2,1)
              (2,3,1)
              (3,1,2)
              (3,2,1)
The complement for n = 3 counts the two patterns (1,2,1) and (2,1,2).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

Crossrefs

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

A000670 counts patterns, ranked by A333217.

A005649 counts anti-run patterns, complement A069321.

A005811 counts runs in binary expansion.

A032011 counts patterns with distinct multiplicities.

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

A060223 counts Lyndon patterns, necklaces A019536, aperiodic A296975.

A131689 counts patterns by number of distinct parts.

A238130 and A238279 count compositions by number of runs.

A297770 counts distinct runs in binary expansion.

A345194 counts alternating patterns, up/down A350354.

Counting words with all distinct runs:

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

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

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

- A351202 = permutations of prime factors.

- A351642 = word structures.

Row sums of A351640.

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

Programs

Mathematica

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]] /@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],UnsameQ@@Split[#]&]],{n,0,6}]

PARI

\\ here LahI is A111596 as row polynomials.
LahI(n,y)={sum(k=1, n, y^k*(-1)^(n-k)*(n!/k!)*binomial(n-1, k-1))}
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))}
R(q)={[subst(serlaplace(p), y, 1) | p<-Vec(q)]}
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

Extensions

Terms a(10) and beyond from Andrew Howroyd, Feb 12 2022