|
|
A351292
|
|
Number of patterns of length n with all distinct run-lengths.
|
|
25
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
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
|
|
|
FORMULA
|
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)
|
|
EXAMPLE
|
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
|
|
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@@Length/@Split[#]&]], {n, 0, 6}]
|
|
PROG
|
(PARI)
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
|
|
CROSSREFS
|
The version for runs instead of run-lengths is A351200.
A005811 counts runs in binary expansion.
A032011 counts patterns with distinct multiplicities.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A131689 counts patterns by number of distinct parts.
A165413 counts distinct run-lengths in binary expansion, runs A297770.
Counting words with all distinct runs:
- A351202 = permutations of prime factors.
Cf. A003242, A098504, A098859, A106356, A239455, A242882, A325545, A328592, A329740, A351014, A351293.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|