OFFSET
0,3
COMMENTS
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
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,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
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
From Gary W. Adamson, Jul 06 2011: (Start)
Construct an infinite array of sequences representing word structures of length n using an N-ary alphabet as follows:
.
1, 1, 1, 1, 1, 1, 1, 1, ...; N=1, A000012
1, 2, 4, 8, 16, 32, 64, 128, ...; N=2, A000079
1, 2, 5, 14, 41, 122, 365, 1094, ...; N=3, A007051
1, 2, 5, 15, 51, 187, 715, 2795, ...; N=4, A007581
1, 2, 5, 15, 52, 202, 855, 3845, ...; N=5, A056272
1, 2, 5, 15, 52, 203, 876, 4111, ...; N=6, A056273
...
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..1275
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Olli-Samuli Lehmus, Optimized Static Allocation of Signal Processing Tasks onto Signal Processing Cores, Master's Thesis, Aalto Univ. (Finland, 2023). See p. 35.
Nelma Moreira and Rogerio Reis, dcc-2004-07.ps
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 (16,-95,260,-324,144).
FORMULA
a(n) = Sum_{k=0..6} Stirling2(n, k).
For n > 0, a(n) = (1/6!)*(6^n + 15*4^n + 40*3^n + 135*2^n + 264). - Vladeta Jovovic, Aug 17 2003
From Nelma Moreira, Oct 10 2004: (Start)
For n > 0 and c = 6:
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. For 2 <= k <= c: g(k, c) = g(k-1, c-1)/k if c>1. (End)
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]
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
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
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
egf := (265+264*exp(x)+135*exp(x*2)+40*exp(x*3)+15*exp(x*4)+exp(6*x))/6!:
ser := series(egf, x, 30): seq(n!*coeff(ser, x, n), n=0..22); # Peter Luschny, Nov 06 2018
MATHEMATICA
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 *)
PROG
(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
(GAP) List([0..25], n->Sum([0..6], k->Stirling2(n, k))); # Muniru A Asiru, Oct 30 2018
(Magma) [(&+[StirlingSecond(n, i): i in [0..6]]): n in [0..30]]; // Vincenzo Librandi, Nov 07 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
a(0)=1 prepended by Robert A. Russell, Nov 06 2018
STATUS
approved