|
|
|
|
1, 3, 8, 23, 75, 277, 1132, 4977, 22979, 109451, 531456, 2610931, 12917683, 64181625, 319695980, 1594859885, 7963472187, 39784944799, 198827606704, 993846943839, 4968361974491, 24839192686973, 124188113975628
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Density of regular language L{0}* over {0, 1, 2, 3, 4, 5} (i.e., the number of strings of length n), where L is described by regular expression with c = 5: Sum_{i=1..c} (Product_{j=1..i} (j(1+...+j)*), where "Sum" stands for union and "Product" for concatenation. I.e., L = L((11* + 11*2(1 + 2)* + ... + 11*2(1 + 2)*3(1 + 2 + 3)*4(1 + 2 + 3 + 4)*5(1 + 2 + 3 + 4 + 5)*)0*).
|
|
LINKS
|
|
|
FORMULA
|
a(5,n) = (1/96)*5^n + (1/8)*3^n + (1/3)*2^n + (3/8)*n - 15/32.
a(n) = Sum_{m=1..n} Sum_{i=1..5} S(m,i), where S(m,i) = A008277(m,i) (i.e., partial sum of the sum of Stirling numbers of second kind S(n,i) for i = 1..5).
For c = 5, a(c,n) = g(1,c)*n + Sum_{k=2..c} g(k,c)*k*(k^n - 1)/(k - 1), where g(1,1) = 1, g(1,c) = g(1,c-1) + (-1)^(c-1)/(c-1)! for c > 1, and g(k,c) = g(k-1, c-1)/k for c > 1 and 2 <= k <= c.
G.f.: x*(-1 + 19*x^3 - 24*x^2 + 9*x)/((3*x-1)*(2*x-1)*(5*x-1)*(x-1)^2). [Maksym Voznyy (voznyy(AT)mail.ru), Jul 28 2009]
|
|
MAPLE
|
with (combinat):seq(sum(sum(stirling2(k, j), j=1..5), k=1..n), n=1..23); # Zerinvary Lajos, Dec 04 2007
|
|
PROG
|
(PARI) a(n) = sum(m=1, n, sum(i=1, 5, stirling(m, i, 2))) \\ Petros Hadjicostas, Mar 10 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|