OFFSET
0,3
COMMENTS
Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.
Density of regular language L over {1,2,3,4}^* (i.e., number of strings of length n in L) described by regular expression 11* + 11*2(1+2)* + 11*2(1+2)*3(1+2+3)* + 11*2(1+2)*3(1+2+3)*4(1+2+3+4)* + 11*2(1+2)*3(1+2+3)*4(1+2+3+4)*5(1+2+3+4+5)* - Nelma Moreira, Oct 10 2004
Number of set partitions of [n] into at most 5 parts. - Joerg Arndt, Apr 18 2014
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
LINKS
Muniru A Asiru, Table of n, a(n) for n = 0..1400 (first 200 terms from Vincenzo Librandi)
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
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 (11,-41,61,-30).
FORMULA
a(n) = Sum_{k=0..5} Stirling2(n, k).
a(n) = (5^n + 10*3^n + 20*2^n + 45)/5! for n >= 1. - Vladeta Jovovic, Aug 17 2003
From Nelma Moreira, Oct 10 2004: (Start)
For c=5, a(n) = c^n/c! + Sum_{k=0..c-2} (k^n/k!*(Sum_{j=2..c-k} (-1)^j/j!)).
a(n) = Sum_{k=1..c} g(k, c)*k^n where g(1, 1) = 1, g(1, c) = g(1, c-1) + (-1)^(c-1)/(c-1)! if c > 1; g(k, c) = g(k-1, c-1)/k if c > 1, 2 <= k <= c and n >= 1. (End)
a(n+1) is the top entry of the vector M^n*[1,1,1,1,1,0,0,0,...], where M is an infinite bidiagonal matrix with M(r,r+1)=1 in the superdiagonal and M(r,r)=r, r>=1 as the main diagonal, and the rest zeros. The n-th power of the matrix is multiplied from the right with a column vector starting with 5 1's. - Gary W. Adamson, Jun 24 2011
G.f.: (1 - 10x + 32x^2 - 37x^3 + 11x^4)/((1 - x)*(1 - 2x)*(1 - 3x)*(1 - 5x)). - R. J. Mathar, Jul 06 2011 [Adapted to offset 0 by Robert A. Russell, Oct 30 2018]
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=5. - Robert A. Russell, Apr 25 2018
E.g.f.: (1/120)*(44 + 45*exp(x) + 20*exp(2*x) + 10*exp(3*x) + exp(5*x)). - Stefano Spezia, Nov 06 2018
EXAMPLE
For a(4)=15, the 7 achiral patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD; the 8 chiral patterns are the 4 pairs AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.
MAPLE
seq(add(combinat:-stirling2(n, j), j=0..5), n=0..23); # Zerinvary Lajos, Dec 04 2007
# Alternative:
(x*(x*(x*(11*x-37)+32)-10)+1)/(x*(x*(x*(30*x-61)+41)-11)+1):
series(%, x, 32): seq(coeff(%, x, n), n=0..23); # Peter Luschny, Nov 05 2018
MATHEMATICA
CoefficientList[Series[(1 - 10 x + 32 x^2 - 37 x^3 + 11 x^4)/((x - 1) (3 x - 1) (2 x - 1) (5 x - 1)), {x, 0, 30}], x] (* Vincenzo Librandi, Apr 19 2014 *)
LinearRecurrence[{11, -41, 61, -30}, {1, 1, 2, 5, 15}, 30] (* Harvey P. Dale, Feb 25 2018 *)
Table[Sum[StirlingS2[n, k], {k, 0, 5}], {n, 0, 30}] (* Robert A. Russell, Apr 25 2018 *)
CoefficientList[Series[1/120 (44 + 45 E^x + 20 E^(2 x) + 10 E^(3 x) + E^(5 x)), {x, 0, 30}], x]*Table[k!, {k, 0, 30}] (* Stefano Spezia, Nov 06 2018 *)
PROG
(PARI) a(n) = sum(k=0, 5, stirling(n, k, 2) ); \\ Joerg Arndt, Apr 18 2014
(Magma) I:=[1, 1, 2, 5, 15]; [n le 5 select I[n] else 11*Self(n-1)-41*Self(n-2)+61*Self(n-3)-30*Self(n-4): n in [1..30]]; // Vincenzo Librandi, Apr 19 2014
(GAP) List([0..25], n->Sum([0..5], k->Stirling2(n, k))); # Muniru A Asiru, Oct 30 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
a(0)=1 prepended by Robert A. Russell, Nov 06 2018
STATUS
approved