A350824 -id:A350824 - cp's OEIS frontend

A351292 Number of patterns of length n with all distinct run-lengths.

1, 1, 1, 5, 5, 9, 57, 61, 109, 161, 1265, 1317, 2469, 3577, 5785, 43901, 47165, 86337, 127665, 204853, 284197, 2280089, 2398505, 4469373, 6543453, 10570993, 14601745, 22502549, 159506453, 171281529, 314077353, 462623821, 742191037, 1031307185, 1580543969, 2141246229

Offset: 0

Gus Wiseman, Feb 10 2022

nonn

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.

			The a(1) = 1 through a(5) = 9 patterns:
  (1)  (1,1)  (1,1,1)  (1,1,1,1)  (1,1,1,1,1)
              (1,1,2)  (1,1,1,2)  (1,1,1,1,2)
              (1,2,2)  (1,2,2,2)  (1,1,1,2,2)
              (2,1,1)  (2,1,1,1)  (1,1,2,2,2)
              (2,2,1)  (2,2,2,1)  (1,2,2,2,2)
                                  (2,1,1,1,1)
                                  (2,2,1,1,1)
                                  (2,2,2,1,1)
                                  (2,2,2,2,1)
The a(6) = 57 patterns grouped by sum:
  111111  111112  111122  112221  111223  111233  112333  122333
          111211  111221  122211  111322  111332  113332  133322
          112111  122111  211122  112222  112223  122233  221333
          211111  221111  221112  211222  113222  133222  223331
                                  221113  122222  211333  333122
                                  222112  211133  222133  333221
                                  222211  221222  222331
                                  223111  222113  233311
                                  311122  222122  331222
                                  322111  222221  332221
                                          222311  333112
                                          233111  333211
                                          311222
                                          322211
                                          331112
                                          332111

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

The version for runs instead of run-lengths is A351200.
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.
A165413 counts distinct run-lengths in binary expansion, runs A297770.
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.
- A351638 = word structures.
Row sums of A350824.
Cf. A003242, A098504, A098859, A106356, A239455, A242882, A325545, A328592, A329740, A351014, A351293.

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@@Length/@Split[#]&]],{n,0,6}]

P(n) = {Vec(-1 + prod(k=1, n, 1 + y*x^k + O(x*x^n)))}
R(u,k) = {k*[subst(serlaplace(p)/y, y, k-1) | p<-u]}
seq(n)={my(u=P(n), c=poldegree(u[#u])); concat([1], sum(k=1, c, R(u, k)*sum(r=k, c, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Feb 11 2022

From Andrew Howroyd, Feb 12 2022: (Start)
a(n) = Sum_{k=1..n} R(n,k)*(Sum_{r=k..n} binomial(r, k)*(-1)^(r-k)), where R(n,k) = Sum_{j=1..floor((sqrt(8*n+1)-1)/2)} k*(k-1)^(j-1) * j! * A008289(n,j).
G.f.: 1 + Sum_{r>=1} Sum_{k=1..r} R(k,x) * binomial(r, k)*(-1)^(r-k), where R(k,x) = Sum_{j>=1} k*(k-1)^(j-1) * j! * [y^j](Product_{k>=1} 1 + y*x^k).
(End)

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

A351637 Triangle read by rows: T(n,k) is the number of length n word structures with all distinct run-lengths using exactly k different symbols, n >= 0, k = 0..floor(sqrt(8*n+1)-1/2).

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 4, 0, 1, 10, 6, 0, 1, 12, 6, 0, 1, 18, 12, 0, 1, 26, 18, 0, 1, 56, 96, 24, 0, 1, 64, 102, 24, 0, 1, 100, 186, 48, 0, 1, 132, 264, 72, 0, 1, 192, 420, 120, 0, 1, 350, 1344, 864, 120, 0, 1, 434, 1572, 936, 120

Offset: 0

Andrew Howroyd, Feb 15 2022

Permuting the symbols will not change the structure.

Equivalently, T(n,k) is the number of restricted growth strings [s(0), s(1), ..., s(n-1)] where s(0)=0 and s(i) <= 1 + max(prefix) for i >= 1, the maximum value is k and every run has a different length.

			Triangle begins:
  1;
  0, 1;
  0, 1;
  0, 1,   2;
  0, 1,   2;
  0, 1,   4;
  0, 1,  10,   6;
  0, 1,  12,   6;
  0, 1,  18,  12;
  0, 1,  26,  18;
  0, 1,  56,  96, 24;
  0, 1,  64, 102, 24;
  0, 1, 100, 186, 48;
  0, 1, 132, 264, 72;
  ...
The T(6,1) = 1 word is 111111.
The T(6,2) = 10 words are 111112, 111122, 111211, 111221, 112111, 112221, 112222, 122111, 122211, 122222.
The T(6,3) = 6 words are 111223, 111233, 112333, 112223, 122333, 122233.

Andrew Howroyd, Table of n, a(n) for n = 0..958 (rows 0..100)

Row sums are A351638.
Partial row sums include A000007, A000012, A032020, A351639.
Column k=2 is A216695.
Cf. A000142, A000217, A003056, A008289, A350824, A351641.

P(n) = {Vec(-1 + prod(k=1, n, 1 + y*x^k + O(x*x^n)))}
R(u, k) = {k*[subst(serlaplace(p)/y, y, k-1) | p<-u]}
T(n)={my(u=P(n), v=concat([1], sum(k=1, n, R(u, k)*sum(r=k, n, y^r*binomial(r, k)*(-1)^(r-k)/r!) ))); [Vecrev(p) | p<-v]}
{ my(A=T(16)); for(n=1, #A, print(A[n])) }

T(n,k) = Sum_{j=1..k} R(n,j)*binomial(k, j)*(-1)^(k-j)/k! for n > 0, where R(n,k) = Sum_{j=1..A003056(n)} k*(k-1)^(j-1) * j! * A008289(n,j).
T(n,k) = A350824(n,k)/k!.
T(A000217(n),n) = A000142(n). - Alois P. Heinz, Feb 15 2022

A351640 Triangle read by rows: T(n,k) is the number of patterns of length n with all distinct runs and maximum value k.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 4, 6, 0, 1, 10, 18, 24, 0, 1, 16, 72, 96, 120, 0, 1, 34, 168, 528, 600, 720, 0, 1, 52, 486, 1632, 4200, 4320, 5040, 0, 1, 90, 1062, 6024, 16200, 36720, 35280, 40320, 0, 1, 152, 2460, 16896, 73200, 169920, 352800, 322560, 362880

Offset: 0

Andrew Howroyd, Feb 15 2022

A pattern is a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670.

			Triangle begins:
  1,
  0, 1;
  0, 1,  2;
  0, 1,  4,   6;
  0, 1, 10,  18,  24;
  0, 1, 16,  72,  96, 120;
  0, 1, 34, 168, 528, 600, 720;
  ...
The T(3,1) = 1 pattern is 111.
The T(3,2) = 4 patterns are 112, 122, 211, 221.
The T(3,3) = 6 patterns are 123, 132, 213, 231, 312, 321.

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Row sums are A351200.
Main diagonal is A000142.
Cf. A000670, A111596, A350824, A351641.

\\ 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)]}
T(n)={my(q=S(n), v=concat([1], sum(k=1, n, R(q^k-1)*sum(r=k, n, y^r*binomial(r, k)*(-1)^(r-k)) ))); [Vecrev(p) | p<-v]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) }

T(n,k) = k! * A351641(n,k).

A351645 Triangle read by rows: T(n,k) is the number of length n word structures using exactly k different symbols with all distinct run-lengths and the first run length of a symbol less than that of previous symbols, n >= 0, k = 0..floor(sqrt(8*n+1)-1/2).

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 0, 1, 5, 1, 0, 1, 6, 1, 0, 1, 9, 2, 0, 1, 13, 3, 0, 1, 28, 16, 1, 0, 1, 32, 17, 1, 0, 1, 50, 31, 2, 0, 1, 66, 44, 3, 0, 1, 96, 70, 5, 0, 1, 175, 224, 36, 1, 0, 1, 217, 262, 39, 1, 0, 1, 308, 428, 71, 2, 0, 1, 425, 619, 105, 3

Offset: 0

Andrew Howroyd, Feb 16 2022

Permuting the symbols will not change the structure.

The k-th column of A351637 is divisible by k!.

			Triangle begins:
  1;
  0, 1;
  0, 1;
  0, 1,  1;
  0, 1,  1;
  0, 1,  2;
  0, 1,  5,  1;
  0, 1,  6,  1;
  0, 1,  9,  2;
  0, 1, 13,  3;
  0, 1, 28, 16, 1;
  0, 1, 32, 17, 1;
  0, 1, 50, 31, 2;
  0, 1, 66, 44, 3;
  0, 1, 96, 70, 5;
  ...
The T(8,1) = 1 word is 11111111.
The T(8,2) = 9 words are 11111112, 11111122, 11111211, 11111221, 11111222, 11112111, 11112221, 11121111, 11211111.
The T(8,3) = 2 words are 11111223, 11112223.
In the last example, the word 11111223 corresponds with 6 words in A351637 which are 11111223, 11111233, 11222223, 11233333, 12222233, 12233333.

Andrew Howroyd, Table of n, a(n) for n = 0..958 (rows 0..100)

Row sums are A351732.

Cf. A000217, A003056, A008289, A350824, A351637.

P(n) = {Vec(-1 + prod(k=1, n, 1 + y*x^k + O(x*x^n)))}
R(u, k) = {k*[subst(serlaplace(p)/y, y, k-1) | p<-u]}
T(n)={my(u=P(n), v=concat([1], sum(k=1, n, R(u, k)*sum(r=k, n, y^r*binomial(r, k)*(-1)^(r-k)/(r!)^2) ))); [Vecrev(p) | p<-v]}
{ my(A=T(16)); for(n=1, #A, print(A[n])) }

T(n,k) = Sum_{j=1..k} R(n,j)*binomial(k, j)*(-1)^(k-j)/(k!)^2 for n > 0, where R(n,k) = Sum_{j=1..A003056(n)} k*(k-1)^(j-1) * j! * A008289(n,j).
T(n,k) = A351637(n,k)/k! = A350824(n,k)/(k!)^2.
T(A000217(n),n) = 1.

cp's OEIS Frontend

A351292 Number of patterns of length n with all distinct run-lengths.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A351637 Triangle read by rows: T(n,k) is the number of length n word structures with all distinct run-lengths using exactly k different symbols, n >= 0, k = 0..floor(sqrt(8*n+1)-1/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A351640 Triangle read by rows: T(n,k) is the number of patterns of length n with all distinct runs and maximum value k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A351645 Triangle read by rows: T(n,k) is the number of length n word structures using exactly k different symbols with all distinct run-lengths and the first run length of a symbol less than that of previous symbols, n >= 0, k = 0..floor(sqrt(8*n+1)-1/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula