login
Partial sums of A056272.
1

%I #26 Mar 11 2021 03:03:24

%S 1,3,8,23,75,277,1132,4977,22979,109451,531456,2610931,12917683,

%T 64181625,319695980,1594859885,7963472187,39784944799,198827606704,

%U 993846943839,4968361974491,24839192686973,124188113975628

%N Partial sums of A056272.

%C 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*).

%H Nelma Moreira and Rogerio Reis, <a href="https://web.archive.org/web/20170810170007/http://www.dcc.fc.up.pt/dcc/Pubs/TReports/TR04/dcc-2004-07.pdf">On the density of languages representing finite set partitions</a>, Technical Report DCC-2004-07, August 2004, DCC-FC & LIACC, Universidade do Porto.

%H Nelma Moreira and Rogerio Reis, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Moreira/moreira8.html">On the Density of Languages Representing Finite Set Partitions</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.

%F a(5,n) = (1/96)*5^n + (1/8)*3^n + (1/3)*2^n + (3/8)*n - 15/32.

%F 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).

%F 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.

%F 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]

%p with (combinat):seq(sum(sum(stirling2(k, j),j=1..5), k=1..n), n=1..23); # _Zerinvary Lajos_, Dec 04 2007

%o (PARI) a(n) = sum(m=1, n, sum(i=1, 5, stirling(m, i, 2))) \\ _Petros Hadjicostas_, Mar 10 2021

%Y Cf. A008277, A047926, A056272, A099264, A099266.

%K easy,nonn

%O 1,2

%A _Nelma Moreira_, Oct 10 2004

%E Name and Formula section edited by _Petros Hadjicostas_, Mar 10 2021