|
Search: id:A077999
|
|
|
| A077999 |
|
Expansion of (1-x)/(1-2*x-2*x^3). |
|
+0 1
|
|
| 1, 1, 2, 6, 14, 32, 76, 180, 424, 1000, 2360, 5568, 13136, 30992, 73120, 172512, 407008, 960256, 2265536, 5345088, 12610688, 29752448, 70195072, 165611520, 390727936, 921846016, 2174915072, 5131286016, 12106264064, 28562358272, 67387288576, 158987105280
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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]
|
|
REFERENCES
|
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]
|
|
FORMULA
|
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
|
|
CROSSREFS
|
Sequence in context: A065495 A131352 A051485 this_sequence A110524 A083404 A089351
Adjacent sequences: A077996 A077997 A077998 this_sequence A078000 A078001 A078002
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Nov 17 2002
|
|
|
Search completed in 0.002 seconds
|