login
Word structures of length n using a 5-ary alphabet.
24

%I #98 Sep 08 2022 08:45:01

%S 1,1,2,5,15,52,202,855,3845,18002,86472,422005,2079475,10306752,

%T 51263942,255514355,1275163905,6368612302,31821472612,159042661905,

%U 795019337135,3974515030652,19870830712482,99348921288655

%N Word structures of length n using a 5-ary alphabet.

%C Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.

%C 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

%C Number of set partitions of [n] into at most 5 parts. - _Joerg Arndt_, Apr 18 2014

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

%H Muniru A Asiru, <a href="/A056272/b056272.txt">Table of n, a(n) for n = 0..1400</a> (first 200 terms from Vincenzo Librandi)

%H Joerg Arndt and N. J. A. Sloane, <a href="/A278984/a278984.txt">Counting Words that are in "Standard Order"</a>

%H Nelma Moreira and Rogerio Reis, <a href="http://www.dcc.fc.up.pt/Pubs/TR04/dcc-2004-07.ps.gz">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.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (11,-41,61,-30).

%F a(n) = Sum_{k=0..5} Stirling2(n, k).

%F a(n) = (5^n + 10*3^n + 20*2^n + 45)/5! for n >= 1. - _Vladeta Jovovic_, Aug 17 2003

%F From _Nelma Moreira_, Oct 10 2004: (Start)

%F For c=5, a(n) = c^n/c! + Sum_{k=0..c-2} (k^n/k!*(Sum_{j=2..c-k} (-1)^j/j!)).

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

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

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

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

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

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

%p seq(add(combinat:-stirling2(n, j), j=0..5), n=0..23); # _Zerinvary Lajos_, Dec 04 2007

%p # Alternative:

%p (x*(x*(x*(11*x-37)+32)-10)+1)/(x*(x*(x*(30*x-61)+41)-11)+1):

%p series(%, x, 32): seq(coeff(%, x, n), n=0..23); # _Peter Luschny_, Nov 05 2018

%t 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 *)

%t LinearRecurrence[{11,-41,61,-30},{1,1,2,5,15},30] (* _Harvey P. Dale_, Feb 25 2018 *)

%t Table[Sum[StirlingS2[n, k], {k, 0, 5}], {n, 0, 30}] (* _Robert A. Russell_, Apr 25 2018 *)

%t 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 *)

%o (PARI) a(n) = sum(k=0,5, stirling(n, k, 2) ); \\ _Joerg Arndt_, Apr 18 2014

%o (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

%o (GAP) List([0..25],n->Sum([0..5],k->Stirling2(n,k))); # _Muniru A Asiru_, Oct 30 2018

%Y Cf. A000351, A007581, A056273, A008290, A007051.

%Y A row of the array in A278984.

%Y Cf. A056324 (unoriented), A320935 (chiral), A305751 (achiral).

%K nonn,easy

%O 0,3

%A _Marks R. Nester_

%E a(0)=1 prepended by _Robert A. Russell_, Nov 06 2018