login
Word structures of length n using a 6-ary alphabet.
21

%I #87 Aug 31 2023 11:02:19

%S 1,1,2,5,15,52,203,876,4111,20648,109299,601492,3403127,19628064,

%T 114700315,676207628,4010090463,23874362200,142508723651,852124263684,

%U 5101098232519,30560194493456,183176170057707

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

%C Set partitions of the n-set into at most 6 parts; also restricted growth strings (RGS) with six letters s(1),s(2),...,s(6) where the first occurrence of s(j) precedes the first occurrence of s(k) for all j < k. - _Joerg Arndt_, Jul 06 2011

%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,5,6}^* (i.e., number of strings of length n in L) described by regular expression with c=6: Sum_{i=1..c}(Product_{j=1..i} (j(1+..+j)*) where Sum stands for union and Product for concatenation. - _Nelma Moreira_, Oct 10 2004

%C Word structures of length n using an N-ary alphabet are generated by taking M^n* the vector [(N 1's),0,0,0,...], leftmost column term = a(n+1). In the case of A056273, the vector = [1,1,1,1,1,1,0,0,0,...]. As the vector approaches all 1's, the leftmost column terms approach A000110, the Bell sequence. - _Gary W. Adamson_, Jun 23 2011

%C From _Gary W. Adamson_, Jul 06 2011: (Start)

%C Construct an infinite array of sequences representing word structures of length n using an N-ary alphabet as follows:

%C .

%C 1, 1, 1, 1, 1, 1, 1, 1, ...; N=1, A000012

%C 1, 2, 4, 8, 16, 32, 64, 128, ...; N=2, A000079

%C 1, 2, 5, 14, 41, 122, 365, 1094, ...; N=3, A007051

%C 1, 2, 5, 15, 51, 187, 715, 2795, ...; N=4, A007581

%C 1, 2, 5, 15, 52, 202, 855, 3845, ...; N=5, A056272

%C 1, 2, 5, 15, 52, 203, 876, 4111, ...; N=6, A056273

%C ...

%C The sequences tend to A000110. Finite differences of columns reinterpreted as rows generate A008277 as a triangle: (1; 1,1; 1,3,1; 1,7,6,1; ...). (End)

%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="/A056273/b056273.txt">Table of n, a(n) for n = 0..1275</a>

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

%H Olli-Samuli Lehmus, <a href="https://aaltodoc.aalto.fi/bitstream/handle/123456789/122822/master_Lehmus_Olli-Samuli_2023.pdf">Optimized Static Allocation of Signal Processing Tasks onto Signal Processing Cores</a>, Master's Thesis, Aalto Univ. (Finland, 2023). See p. 35.

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

%H Nelma Moreira and Rogerio Reis, <a href="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="https://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_05">Index entries for linear recurrences with constant coefficients</a>, signature (16,-95,260,-324,144).

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

%F For n > 0, a(n) = (1/6!)*(6^n + 15*4^n + 40*3^n + 135*2^n + 264). - _Vladeta Jovovic_, Aug 17 2003

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

%F For n > 0 and c = 6:

%F 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. For 2 <= k <= c: g(k, c) = g(k-1, c-1)/k if c>1. (End)

%F G.f.: (1 - 15*x + 81*x^2 - 192*x^3 + 189*x^4 - 53*x^5)/((1-x)*(1-2x)*(1-3x)*(1-4x)*(1-6x)). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 26 2009 [corrected by _R. J. Mathar_, Sep 16 2009] [Adapted to offset 0 by _Robert A. Russell_, Nov 06 2018]

%F G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=6. - _Robert A. Russell_, Apr 25 2018

%F E.g.f.: (265 + 264*exp(x) + 135*exp(x*2) + 40*exp(x*3) + 15*exp(x*4) + exp(6*x))/6!. - _Peter Luschny_, 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 egf := (265+264*exp(x)+135*exp(x*2)+40*exp(x*3)+15*exp(x*4)+exp(6*x))/6!:

%p ser := series(egf,x,30): seq(n!*coeff(ser,x,n),n=0..22); # _Peter Luschny_, Nov 06 2018

%t Table[Sum[StirlingS2[n,k],{k,0,6}],{n,0,30}] (* or *) LinearRecurrence[ {16,-95,260,-324,144},{1,1,2,5,15,52},30] (* _Harvey P. Dale_, Jun 05 2015 *)

%o (PARI) Vec((1 - 15*x + 81*x^2 - 192*x^3 + 189*x^4 - 53*x^5)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)*(1-6*x)) + O(x^30)) \\ _Michel Marcus_, Nov 07 2018

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

%o (Magma) [(&+[StirlingSecond(n, i): i in [0..6]]): n in [0..30]]; // _Vincenzo Librandi_, Nov 07 2018

%Y A row of the array in A278984 and A320955.

%Y Cf. A000351, A000400, A007581, A056272, A008290, A007051, A099263, A099262, A000110, A008277.

%Y Cf. A056325 (unoriented), A320936 (chiral), A305752 (chiral).

%K nonn,easy

%O 0,3

%A _Marks R. Nester_

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