OFFSET
1,2
COMMENTS
Some previous names were a(6,n) := (1/600)*6^n + (1/36)*4^n + (1/12)*3^n + (3/8)*2^n + (11/30)*n - (439/900) = Sum_{m=1..n} Sum_{i=1..6} S(m,i), where S(n,i) = A008277(n,i) are the Stirling numbers of the second kind.
Density of the regular language L{0}* over {0, 1, 2, 3, 4, 5, 6} (i.e., the number of strings of length n), where L is described by regular expression with c = 6: Sum_{i=1..c} Prod_{j=1..i} (j(1+...+j)*), where "Sum" stands for union and "Product" for concatenation. I.e., L = L((11* + ... + 11*2(1 + 2)*3(1 + 2 + 3)*4(1 + 2 + 3 + 4)*5(1 + 2 + 3 + 4 + 5)*6(1 + 2 + 3 + 4 + 5 + 6)*)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.
Index entries for linear recurrences with constant coefficients, signature (17,-111,355,-584,468,-144).
FORMULA
For c = 6, 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*(91*x^4 - 135*x^3 + 68*x^2 - 14*x + 1) / ((x - 1)^2*(2*x - 1)*(3*x - 1)*(4*x - 1)*(6*x - 1)). - Colin Barker, Oct 28 2014
MAPLE
with (combinat):seq(sum(sum(stirling2(k, j), j=1..6), k=1..n), n=1..23); # Zerinvary Lajos, Dec 04 2007
PROG
(PARI) Vec(x*(91*x^4-135*x^3+68*x^2-14*x+1)/((x-1)^2*(2*x-1)*(3*x-1)*(4*x-1)*(6*x-1)) + O(x^100)) \\ Colin Barker, Oct 28 2014
(PARI) a(n) = sum(m=1, n, sum(i=1, 6, stirling(m, i, 2))) \\ Petros Hadjicostas, Mar 09 2021
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Nelma Moreira, Oct 10 2004
EXTENSIONS
Shorter name by Joerg Arndt, Oct 28 2014
Comments edited by Petros Hadjicostas, Mar 09 2021
STATUS
approved