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

1, 1, 2, 5, 15, 52, 203, 876, 4111, 20648, 109299, 601492, 3403127, 19628064, 114700315, 676207628, 4010090463, 23874362200, 142508723651, 852124263684, 5101098232519, 30560194493456, 183176170057707, 1098318779272060, 6586964947803695, 39510014478620232, 237013033135668883

Offset: 0

Author

Marks R. Nester

Keywords

• nonn
• easy

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

...

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)

Examples

			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.
		

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

Crossrefs

A row of the array in A278984 and A320955.

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

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

Programs

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

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

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

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

Extensions

a(0)=1 prepended by Robert A. Russell, Nov 06 2018