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,3

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

Example

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

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

Prog

(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

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.

Sequence in context: A074512 A005502 A305710 * A000255 A318912 A121580

Adjacent sequences: A351197 A351198 A351199 * A351201 A351202 A351203

Keyword

nonn

Author

Gus Wiseman, Feb 09 2022

Extensions

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

Status

approved