0,3

a(n) = number of permutations on [n] that avoid nonconsecutive instances of the patterns 321 and 312. For example, a(4) does not count pi=4231 because 431 forms a 321 pattern in pi but 431 is not a consecutive (that is, contiguous) string in pi; also, the first 3 letters form a 312 pattern but that's not disqualifying because they do occur consecutively. Counting these permutations by various statistics yields the listed formulas/recurrences. - David Callan (callan(AT)stat.wisc.edu), Oct 26 2006

a(n) = term (1,1) of M^n, M = the 4x4 matrix [1,0,1,1; 1,1,0,0; 0,1,0,1; 1,0,0,1]. a(n)/a(n-1) tends to 2.3593040859,...an eigenvalue of the matrix and a root to the characteristic polynomial x^4 - 3x^3 + 2x^2 - 2x + 2. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 01 2008]

S. R. Finch, "Several Constants Arising in Statistical Mechanics", arXiv:Math/9810155, 1-29-99, p.8 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 01 2008]

a[n] = 2(a[n-1] + a[n-3]) counts the above permutations by first entry. a[n] = a[n-1] + a[n-2] + 3*Sum[a[k],{k,0,n-3}] counts by last entry. a[n] = 2^(n-1) + Sum[2^(n-2-k)a[k],{k,0,n-3}] counts by location of first 3xx pattern. a[n] = Sum[(n-k)/(n-2k)binomial[n-2k,k]2^(n-2k-1),{k,0,Floor[n/3]}] counts by number of 3xx patterns. - David Callan (callan(AT)stat.wisc.edu), Oct 26 2006

Sequence in context: A065495 A131352 A051485 this_sequence A110524 A083404 A089351

Adjacent sequences: A077996 A077997 A077998 this_sequence A078000 A078001 A078002

nonn

N. J. A. Sloane (njas(AT)research.att.com), Nov 17 2002