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
Nelma Moreira and Rogerio Reis, On the density of languages representing finite set partitions, Technical Report DCC-2004-07, August 2004, DCC-FC & LIACC, Universidade do Porto.
Nelma Moreira and Rogerio Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
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
Nelma Moreira, Oct 10 2004
EXTENSIONS
Name and Formula section edited by Petros Hadjicostas, Mar 10 2021
More terms from Michel Marcus, Jan 05 2025
STATUS
approved