|
|
A005251
|
|
a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1) + a(n-2) + a(n-4).
(Formerly M1059)
|
|
170
|
|
|
0, 1, 1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, 170625, 299426, 525456, 922111, 1618192, 2839729, 4983377, 8745217, 15346786, 26931732, 47261895, 82938844, 145547525, 255418101, 448227521
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
a(n+3) is the number of n-bit sequences that avoid 010. Example: For n=4 the 12 sequences are all 4-bit sequences except 0100, 0101, 0010, 1010. - David Callan, Mar 25 2004
a(n+2) is the number of compositions (ordered partitions) of n where no two adjacent parts are != 1, see example. - Joerg Arndt, Jan 26 2013
a(n+1) is the number of compositions of n avoiding the part 2. - Joerg Arndt, Jul 13 2014
Number of different positive braids with n crossings of 3 strands.
This is a_2(n) in the Doroslovacki reference. Note that there is a typo in the paper in the formula for a_2(n): the upper bound in the inner sum should be "n-i" not "i-1". - Max Alekseyev, Jun 26 2007
a(n) is the number of peakless Motzkin paths of length n-1 with no UHH...HD's starting at level > 0 (here n > 0 and U=(1,1), H=(1,0), D=(1,-1)). Example: a(5)=7 because from all 8 peakless Motzkin paths of length 5 (see A004148) only UUHDD does not qualify. - Emeric Deutsch, Sep 13 2004
Equals the INVERT transform of (1, 0, 1, 1, 1, ...); equivalent to a(n) = a(n-1) + a(n-3) + a(n-4) + ... - Gary W. Adamson, Apr 27 2009
a(n) is the number of length n-1 words on {0,1} such that each string of 1's is followed by a string of at least two 0's. For example, a(5) = 4 because we have: 0000, 0100, 1000, and 1100. - Geoffrey Critzer, Aug 09 2013
a(n+1) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 0; 0, 1, 1; 1, 0, 0] or [1, 0, 1; 1, 1, 0; 0, 1, 0] or [1, 1, 0; 0, 0, 1; 1, 0, 1] or [1, 0, 1; 1, 0, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014
For n >= 2, a(n) is the number of (n-2)-length binary words with no isolated zeros. - Milan Janjic, Mar 07 2015
Apart from the first three terms, the total number of bargraphs of semiperimeter n of height at most two for n >= 2 starts 1, 2, 4, 7, 12, ... - Arnold Knopfmacher, Nov 02 2016
Number of DD-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are DD-equivalent iff the positions of pattern DD are identical in these paths. - Sergey Kirgizov, Apr 08 2018
For n > 0, also the number of subsets of {1, ..., n - 3} such that if x and x + 2 are both in the subset, then so is x + 1. For example, the a(3) = 1 through a(7) = 12 subsets are:
{} {} {} {} {}
{1} {1} {1} {1}
{2} {2} {2}
{1,2} {3} {3}
{1,2} {4}
{2,3} {1,2}
{1,2,3} {1,4}
{2,3}
{3,4}
{1,2,3}
{2,3,4}
{1,2,3,4}
(End)
The two-dimensional version, which counts sets of pairs where, if two pairs are separated by graph-distance 2, then the intermediate pair or pairs are also in the set, is A329871. - Gus Wiseman, Nov 30 2019
a(n+1) is the number of ways to tile a strip of length n with squares, dominoes, and tetrominoes, where the first tile cannot be a domino. - Greg Dresden and Myanna Nash, Aug 18 2020
|
|
REFERENCES
|
S. Burckel, Efficient methods for three strand braids (submitted). [Apparently unpublished]
P. Chinn and S. Heubach, "Compositions of n with no occurrence of k", Congressus Numeratium, 2002, v. 162, pp. 33-51.
John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205.
R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
|
|
FORMULA
|
a(n) = 2*a(n-1) - a(n-2) + a(n-3).
23*a_n = 3*P_{2n+1} + 7*P_{2n} - 2*P_{2n-1}, where P_n are the Perrin numbers, A001608. - Don Knuth, Dec 09 2008
a(n) = (Sum_{j<n} a(j)) - a(n-2).
a(n+2) has g.f. (F_3(-x) + F_2(-x))/(F_4(-x) + F_3(-x)) = 1/(-x+1/(-x+1/(-x+1))) where F_n(x) is the n-th Fibonacci polynomial; see A011973. - Qiaochu Yuan (qchu(AT)mit.edu), Feb 19 2009
a(n) = hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4) for n > 1. - Peter Luschny, Apr 08 2018
G.f.: z/(1-z-z^3-z^4-z^5-...) for the compositions of n-1 avoiding 2. The g.f. for the number of compositions of n avoiding the part k is 1/(1-z-...-z^(k-1) - z^(k+1)-...). - Gregory L. Simay, Sep 09 2018
|
|
EXAMPLE
|
The a(5+2) = 12 compositions of 5 where no two adjacent parts are != 1 are
[ 1] [ 1 1 1 1 1 ]
[ 2] [ 1 1 1 2 ]
[ 3] [ 1 1 2 1 ]
[ 4] [ 1 1 3 ]
[ 5] [ 1 2 1 1 ]
[ 6] [ 1 3 1 ]
[ 7] [ 1 4 ]
[ 8] [ 2 1 1 1 ]
[ 9] [ 2 1 2 ]
[10] [ 3 1 1 ]
[11] [ 4 1 ]
[12] [ 5 ]
(End)
G.f. = x + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 21*x^8 + 37*x^9 + ...
|
|
MAPLE
|
a := n -> `if`(n<=1, n, hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4)):
|
|
MATHEMATICA
|
LinearRecurrence[{2, -1, 1}, {0, 1, 1}, 40] (* Harvey P. Dale, May 05 2011 *)
a[ n_]:= If[n<0, SeriesCoefficient[ -x(1-x)/(1 -x + 2x^2 -x^3), {x, 0, -n}], SeriesCoefficient[ x(1-x)/(1 -2x +x^2 -x^3), {x, 0, n}]] (* Michael Somos, Dec 13 2013 *)
a[0] = 1; a[1] = a[2] = 0; a[n_] := a[n] = a[n-2] + a[n-3]; Table[a[2 n-1], {n, 1, 20}] (* Rigoberto Florez, Oct 15 2019 *)
Table[If[n==0, 0, Length[DeleteCases[Subsets[Range[n-3]], {___, x_, y_, ___}/; x+2==y]]], {n, 0, 10}] (* Gus Wiseman, Nov 25 2019 *)
|
|
PROG
|
(Haskell)
a005251 n = a005251_list !! n
a005251_list = 0 : 1 : 1 : 1 : zipWith (+) a005251_list
(drop 2 $ zipWith (+) a005251_list (tail a005251_list))
(PARI) {a(n) = if( n<0, polcoeff( -x*(1-x)/(1 -x +2*x^2 -x^3) + x*O(x^-n), -n), polcoeff( x*(1-x)/(1 -2*x +x^2 -x^3) + x*O(x^n), n))} /* Michael Somos, Dec 13 2013 */
(Magma) I:=[0, 1, 1, 1]; [n le 4 select I[n] else Self(n-1)+Self(n-2)+Self(n-4): n in [1..45]]; // Vincenzo Librandi, Nov 30 2018
(Magma) R<x>:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1-x)/(1-2*x + x^2 - x^3) )); // Marius A. Burtea, Oct 24 2019
(SageMath) [sum( binomial(n-j-1, 2*j) for j in (0..floor((n-1)/3)) ) for n in (0..50)] # G. C. Greubel, Apr 13 2022
|
|
CROSSREFS
|
Bisection of Padovan sequence A000931.
Partial sums of A005314 shifted 3 times to the right, if we assume A005314(0) = 1.
Compositions without adjacent equal parts are A003242.
Compositions without isolated parts are A114901.
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|