Displaying 1-10 of 474 results found.
page
1
2
3
4
5
6
7
8
9
10
... 48
Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=a(1)=a(2)=1.
(Formerly M2454 N0975)
+0
148
1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745, 25281, 46499, 85525, 157305, 289329, 532159, 978793, 1800281, 3311233, 6090307, 11201821, 20603361, 37895489, 69700671, 128199521, 235795681, 433695873, 797691075, 1467182629
COMMENTS
The name "tribonacci number" is less well-defined than "Fibonacci number". The sequence A000073 (which begins 0, 0, 1) is probably the most important version, but the name has also been applied to A000213, A001590, and A081172. - N. J. A. Sloane, Jul 25 2024 Number of (n-1)-bit binary sequences with each one adjacent to a zero. - R. H. Hardin, Dec 24 2007 Equals INVERT transform of (1, 0, 2, 0, 2, 0, 2, ...). a(6) = 17 = (1, 1, 1, 3, 5, 9) dot (0, 2, 0, 2, 0, 1) = (0 + 2 + 0 + 6 + 0 + 9) = 17. - Gary W. Adamson, Apr 27 2009 Equals the number of tilings of a 2 X n grid using singletons and "S-shaped tetrominoes" (i.e., shapes of the form Polygon[{{0, 0}, {2, 0}, {2, 1}, {3, 1}, {3, 2}, {1, 2}, {1, 1}, {0, 1}}]).
Also equals the number of tilings of a 2 X n grid using singletons and "T-shaped tetrominoes" (i.e., shapes of the form Polygon[{{0, 0}, {3, 0}, {3, 1}, {2, 1}, {2, 2}, {1, 2}, {1, 1}, {0, 1}}]). (End)
Pisano period lengths: 1, 1, 13, 4, 31, 13, 48, 8, 39, 31, 110, 52, 168, 48, 403, 16, 96, 39, 360, 124, ... (differs from A106293). - R. J. Mathar, Aug 10 2012 a(n) is the number of compositions of n with no consecutive 1's. a(4) = 5 because we have: 4, 3+1, 1+3, 2+2, 1+2+1. Cf. A239791, A003242. - Geoffrey Critzer, Mar 27 2014 a(n+2) is the number of words of length n over alphabet {1,2,3} without having {11,12,22,23} as substrings. - Ran Pan, Sep 16 2015 a(n) is also the number of dominating sets on the (n-1)-path graph. - Eric W. Weisstein, Mar 31 2017 a(n) is also the number of maximal irredundant sets and minimal dominating sets in the (2n-3)-triangular snake graph. - Eric W. Weisstein, Jun 09 2019 a(n) is also the number of anti-palindromic compositions of n, where a composition (c(1), c(2),..., c(k)) is anti-palindromic if c(i) is not equal to c(k+1-i) whenever 1 <= i <= k/2. For instance, there are a(4) = 5 anti-palindromic compositions of 4: 4, 31, 13, 211, 112. - Jia Huang, Apr 08 2023
REFERENCES
Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
George E. Andrews, Matthew Just, and Greg Simay, Anti-palindromic compositions, arXiv:2102.01613 [math.CO], 2021. Also Fib. Q., 60:2 (2022), 164-176. See Table 1. B. G. Baumgart, Letter to the editor Part 1 Part 2 Part 3, Fib. Quart. 2 (1964), 260, 302.
FORMULA
G.f.: (1-x)*(1+x)/(1-x-x^2-x^3). - Ralf Stephan, Feb 11 2004 G.f.: 1 / (1 - x / (1 - 2*x^2 / (1 + x^2))). - Michael Somos, May 12 2012 a(n) = rightmost term of M^n * [1 1 1], where M is the 3 X 3 matrix [1 1 1 / 1 0 0 / 0 1 0]. M^n * [1 1 1] = [a(n+2) a(n+1) a(n)]. a(n)/a(n-1) tends to the tribonacci constant, 1.839286755...; an eigenvalue of M and a root of x^3 - x^2 - x - 1 = 0. - Gary W. Adamson, Dec 17 2004 a(n) = 2*a(n-1) - a(n-4), n > 3. - Gary Detlefs, Sep 13 2010 a(n) = Sum_{m=0..n/2} Sum_{i=0..m} binomial(n-2*m+1,m-i)*binomial(n-2*m+i, n-2*m). - Vladimir Kruchinin, Dec 17 2011 G.f.: 1+x/(U(0) - x) where U(k) = 1 - x^2/(1 - 1/(1 + 1/U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Nov 16 2012 G.f.: 1 + x + x^2/(G(0)-x) where G(k) = 1 - x*(2*k+1)/(1 - 1/(1 + (2*k+1)/G(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Nov 17 2012 G.f.: (1+x)*(1-x)*(1 + x*(G(0)-1)/(x+1)) where G(k) = 1 + (1+x+x^2)/(1-x/(x+1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 26 2013 G.f.: 1/(1+x-G(0)), where G(k) = 1 - 1/(1 - x/(x - 1/(1 + 1/(1 - x/(x + 1/G(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, Jun 20 2013
EXAMPLE
G.f. = 1 + x + x^2 + 3*x^3 + 5*x^4 + 9*x^5+ 17*x^6 + 31*x^7 + 57*x^8 + ...
MAPLE
K:=(1-z^2)/(1-z-z^2-z^3): Kser:=series(K, z=0, 45): seq((coeff(Kser, z, n)), n= 0..34); # Zerinvary Lajos, Nov 08 2007
MATHEMATICA
LinearRecurrence[{1, 1, 1}, {1, 1, 1}, 45] (* Harvey P. Dale, May 23 2011 *) Table[RootSum[-1 - # - #^2 + #^3 &, 2 #^n - 4 #^(n + 1) + 3 #^(n + 2) &]/11, {n, 0, 45}] (* Eric W. Weisstein, Apr 10 2018 *) CoefficientList[Series[(1-x)(1+x)/(1-x-x^2-x^3), {x, 0, 45}], x] (* Eric W. Weisstein, Apr 10 2018 *)
PROG
(PARI) a(n)=tn=[1, 1, 1; 1, 0, 0; 0, 1, 0]^n; tn[3, 1]+tn[3, 2]+tn[3, 3] \\ Charles R Greathouse IV, Feb 18 2011 (Maxima) a(n):=sum(sum(binomial(n-2*m+1, m-i)*binomial(n-2*m+i, n-2*m), i, 0, m), m, 0, (n)/2); /* Vladimir Kruchinin, Dec 17 2011 */ (Haskell)
a000213 n = a000213_list !! n
a000213_list = 1 : 1 : 1 : zipWith (+) a000213_list
(tail $ zipWith (+) a000213_list (tail a000213_list))
(Magma) I:=[1, 1, 1]; [n le 3 select I[n] else Self(n-1) + Self(n-2) + Self(n-3): n in [1..45]]; // G. C. Greubel, Jun 09 2019 (Sage) ((1-x^2)/(1-x-x^2-x^3)).series(x, 45).coefficients(x, sparse=False) # G. C. Greubel, Jun 09 2019 (GAP) a:=[1, 1, 1];; for n in [4..45] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Jun 09 2019 (Python)
alst = [1, 1, 1]
[alst.append(alst[n-1] + alst[n-2] + alst[n-3]) for n in range(3, 37)]
a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).
+0
294
0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381, 174762, 349525, 699050, 1398101, 2796202, 5592405, 11184810, 22369621, 44739242, 89478485, 178956970, 357913941, 715827882, 1431655765, 2863311530, 5726623061, 11453246122
COMMENTS
Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg, who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017 Number of steps to change from a binary string of n 0's to n 1's using a Gray code. - Jon Stadler (jstadler(AT)coastal.edu)
Popular puzzles such as Spin-Out and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.
Conjecture: {a(n)} also gives all j for which A048702(j) = A000217(j); i.e., if we take the a(n)-th triangular number (a(n)^2 + a(n))/2 and multiply it by 3, we get a(n)-th even-length binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g., a(4) = 10, which is 1010 in binary; the tenth triangular number is 55, and 55*3 = 165 = 10100101 in binary. - Antti Karttunen, circa 1999. (This has been now proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016 Number of ways to tie a tie of n or fewer half turns, excluding mirror images. Also number of walks of length n or less on a triangular lattice with the following restrictions; given l, r and c as the lattice axes. 1. All steps are taken in the positive axis direction. 2. No two consecutive steps are taken on the same axis. 3. All walks begin with l. 4. All walks end with rlc or lrc. - Bill Blewett, Dec 21 2000 a(n) is the minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - Sen-peng Eu, Jun 15 2002 Equivalently, numbers m whose binary representation is effectively, for some number k, both the lazy Fibonacci and the Zeckendorf representation of k (in which case k = A022290(m)). - Peter Munn, Oct 06 2022 a(n+1) gives row sums of Riordan array (1/(1-x), x(1+2x)). - Paul Barry, Jul 18 2005 Total number of initial 01's in all binary words of length n+1. Example: a(3) = 5 because the binary words of length 4 that start with 01 are (01)00, (01)(01), (01)10 and (01)11 and the total number of initial 01's is 5 (shown between parentheses). a(n) = Sum_{k >= 0} k* A119440(n+1, k). - Emeric Deutsch, May 19 2006 In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts. - Hans Isdahl, Jan 07 2008 For n > 1, let B_n = the complete binary tree with vertex set V where |V| = 2^n - 1. If VC is a minimum-size vertex cover of B_n, Sen-Peng Eu points out that a(n) = |VC|. It also follows that if IS = V\VC, a(n+1) = |IS|. - K.V.Iyer, Apr 13 2009 This is the sequence A(0, 1; 1, 2; 1) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010 1) Denote by {n, k} the number of permutations of 1, ..., n with the up-down index k (for definition, see comment in A203827). Then max_k{n, k} = {n, a(n)} = A000111(n). 2) a(n) is the minimal number > a(n-1) with the Hamming distance d_H(a(n-1), a(n)) = n. Thus this sequence is the Hamming analog of triangular numbers 0, 1, 3, 6, 10, ... (End)
Represented in binary form each term after the second one contains every previous term as a substring.
The terms a(2) = 2 and a(3) = 5 are the only primes. Proof: For even n we get a(n) = 2*(2^(2*n) - 1)/3, which shows that a(n) is even, too, and obviously a(n) > 2 for all even n > 2. For odd n we have a(n) = (2^(n+1) - 1)/3 = (2^((n+1)/2) - 1) * (2^((n+1)/2) + 1)/3. Evidently, at least one of these factors is divisible by 3, both are greater than 6, provided n > 3. Hence it follows that a(n) is composite for all odd n > 3.
Represented as a binary number, a(n+1) has exactly n prime substrings. Proof: Evidently, a(1) = 1_2 has zero and a(2) = 10_2 has 1 prime substring. Let n > 1. Written in binary, a(n+1) is 101010101...01 (if n + 1 is odd) and is 101010101...10 (if n + 1 is even) with n + 1 digits. Only the 2- and 3-digits substrings 10_2 (=2) and 101_2 (=5) are prime substrings. All the other substrings are nonprime since every substring is a previous term and all terms unequal to 2 and 5 are nonprime. For even n + 1, the number of prime substrings equal to 2 = 10_2 is (n+1)/2, and the number of prime substrings equal to 5 = 101_2 is (n-1)/2, makes a sum of n. For odd n + 1 we get n/2 for both, the number of 2's and 5's prime substrings, in any case, the sum is n.
(End)
Also the number of different 3-colorings for the vertices of all triangulated planar polygons on a base with n+2 vertices if the colors of the two base vertices are fixed. - Patrick Labarque, Feb 09 2013 a(n) is the number of length n binary words containing at least one 1 and ending in an even number (possibly zero) of 0's. a(3) = 5 because we have: 001, 011, 100, 101, 111. - Geoffrey Critzer, Dec 15 2013 a(n) is the number of permutations of length n+1 having exactly one descent such that the first element of the permutation is an even number. - Ran Pan, Apr 18 2015 a(n) is the sequence of the last row of the Hadamard matrix H(2^n) obtained via Sylvester's construction: H(2) = [1,1;1,-1], H(2^n) = H(2^(n-1))*H(2), where * is the Kronecker product. - William P. Orrick, Jun 28 2015 Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 131", based on the 5-celled von Neumann neighborhood. See A279053 for references and links. - Robert Price, Dec 05 2016 Conjecture: a(n+1) is the number of compositions of n with two kinds of parts, n and n', where the order of the 1 and 1' does not matter. For n=2, a(3) = 5 compositions, enumerated as follows: 2; 2'; 1,1; 1',1 = 1',1; 1',1'. - Gregory L. Simay, Sep 02 2017 Conjecture proved by recognizing the appropriate g.f. is x/(1 - x)(1 - x)(1 - 2*x^2 - 2x^3 - ...) = x/(1 - 2*x - x^2 + 2x^3). - Gregory L. Simay, Sep 10 2017 a(2*n) = n times the string [10] in binary representation, a(2*n+1) = n times the string [10] followed with [1] in binary representation. Example: a(7) = 85 = (1010101) in binary, a(8) = 170 = (10101010) in binary. - Ctibor O. Zizka, Nov 06 2018 Except for 0, these are the positive integers whose binary expansion has cuts-resistance 1. For the operation of shortening all runs by 1, cuts-resistance is the number of applications required to reach an empty word. Cuts-resistance 2 is A329862. - Gus Wiseman, Nov 27 2019 Let s(k) be the length of the Collatz orbit of k, e.g. s(1) = 1, s(2) = 2, s(3) = 5. Then s(a(n)) = n+3 for n >= 3. Proof by induction: s(a(3)) = s(5) = 6 = 3+3. For odd n >= 5 we have s(a(n)) = s(4*a(n-2)+1) = s(12*a(n-2)+4)+1 = s(3*a(n-2)+1)+3 = s(a(n-2))+2 = (n-2)+3+2 = n+3, and for even n >= 4 this gives s(a(n)) = s(2*a(n-1)) = s(a(n-1))+1 = (n-1)+3+1 = n+3.
Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)
With offset 1 the sequence equals the numbers of 1's from n = 1 to 3, 3 to 7, 7 to 15, ...; of A035263; as shown below: ..1 3 7 15...
..1 0 1 1 1 0 1 0 1 0 1 1 1 0 1...
..1.....2...........5......................10...; a(n) = Sum_(k=1..2n-1) A035263(k) .....1...........2.......................5...; as to zeros.
..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:
..0, 1, 2, 0, 1, 2, ... whereas even numbered disks move in the pattern:
..0, 2, 1, 0, 2, 1, ... (End)
Except for 0, numbers that are repunits in Gray-code representation ( A014550). - Amiram Eldar, May 21 2021 Also the number of nonempty subsets of {1..n} with integer median, where the median of a multiset is the middle part in the odd-length case, and the average of the two middle parts in the even-length case. For example, the a(1) = 1 through a(4) = 10 subsets are:
{1} {1} {1} {1}
{2} {2} {2}
{3} {3}
{1,3} {4}
{1,2,3} {1,3}
{2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
The complement is counted by A005578. For mean instead of median we have A051293, counting empty sets A327475. (End)
REFERENCES
Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.
FORMULA
a(n) = ceiling(2*(2^n-1)/3).
Alternating sum transform (PSumSIGN) of {2^n - 1} ( A000225). a(n) = a(n-1) + 2*a(n-2) + 1.
a(n) = 2*2^n/3 - 1/2 - (-1)^n/6.
a(n) = n + 2*Sum_{k = 1..n-2} a(k).
G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3). - Paul Barry, Feb 11 2003 a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). - Paul Barry, Feb 11 2003 a(n) = Sum_{k = 0..floor((n-1)/2)} 2^(n-2*k-1). - Paul Barry, Nov 11 2003 a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2*k); a(n+1) = Sum_{k = 0..n} Sum_{j = 0..k} (-1)^(j+k)*2^j. - Paul Barry, Nov 12 2003 (-1)^(n+1)*a(n) = Sum_{i = 0..n} Sum_{k = 1..i} k!*k* Stirling2(i, k)*(-1)^(k-1) = (1/3)*(-2)^(n+1)-(1/6)(3*(-1)^(n+1)-1). - Mario Catalani (mario.catalani(AT)unito.it), Dec 22 2003
a(n+1) = (n!/3)*Sum_{i - (-1)^i + j = n, i = 0..n, j = 0..n} 1/(i - (-1)^i)!/j!. - Benoit Cloitre, May 24 2004 a(n) = Sum_{k = 0..n} 2^(n-k-1)*(1-(-1)^k), row sums of A130125. - Paul Barry, Jul 28 2004 a(n) = Sum_{k = 0..n} binomial(k, n-k+1)2^(n-k); a(n) = Sum_{k = 0..floor(n/2)} binomial(n-k, k+1)2^k. - Paul Barry, Oct 07 2004 a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3) - 1 = A005578(n+1) - 1. - Paul Barry, Oct 08 2005 Convolution of "Number of fixed points in all 231-avoiding involutions in S_n." ( A059570) with "1-n" ( A024000), treating the result as if offset was 0. - Graeme McRae, Jul 12 2006 Starting (1, 2, 5, 10, 21, 42, ...), these are the row sums of triangle A135228. - Gary W. Adamson, Nov 23 2007 Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [ A005578(n), A001045(n), a(n-1)]. - Gary W. Adamson, Dec 25 2007 If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*stirling2(k,j)*x^(m-k) then a(n-3) = (-1)^(n-1)*f(n,3,-2), (n >= 3). - Milan Janjic, Apr 26 2009 a(n) = round((2^(n+2)-3)/6) = floor((2^(n+1)-1)/3) = round((2^(n+1)-2)/3); a(n) = a(n-2) + 2^(n-1), n > 1. - Mircea Merca, Dec 27 2010 a(n) = binary XOR of 2^k-1 for k=0..n. - Paul D. Hanna, Nov 05 2011 E.g.f.: 2/3*exp(2*x) - 1/2*exp(x) - 1/6*exp(-x) = 2/3*U(0); U(k) = 1 - 3/(4*(2^k) - 4*(2^k)/(1+3*(-1)^k - 24*x*(2^k)/(8*x*(2^k)*(-1)^k - (k+1)/U(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011 a(n) = 2*(2^n - 1)/3, for even n; a(n) = (2^(n+1) - 1)/3 = (1/3)*(2^((n+1)/2) - 1)*(2^((n+1)/2) + 1), for odd n. - Hieronymus Fischer, Nov 22 2012 a(n) + a(n+1) = 2^(n+1) - 1. - Arie Bos, Apr 03 2013 G.f.: Q(0)/(3*(1-x)), where Q(k) = 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 + 1/(2*4^k - 8*x*16^k/(4*x*4^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 21 2013 a(n) = (2^(n+1) - 2 + (n mod 2))/3. - Paul Toms, Mar 18 2015 a(0) = 0, a(n) = 2*(a(n-1)) + (n mod 2). - Paul Toms, Mar 18 2015 Binary: a(n) = (a(n-1) shift left 1) + (a(n-1)) NOR (...11110). - Paul Toms, Mar 18 2015 a(n) = -(2^n)*a(-n) for even n; a(n) = -(2^(n+1))*a(-n) + 1 for odd n.
0 = +a(n)*(+2 +4*a(n) -4*a(n+1)) + a(n+1)*(-1 +a(n+1)) for all n in Z. (End)
a(4*k+d) = 2^(d+1)*a(4*k-1) + a(d), a(n+4) = a(n) + 2^n*10, a(0..3) = [0,1,2,5]. So the last digit is always 0,1,2,5 repeated. - Yuchun Ji, May 22 2023
EXAMPLE
a(4)=10 since 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111 are the 10 binary strings switching 0000 to 1111.
a(3) = 1 because "lrc" is the only way to tie a tie with 3 half turns, namely, pass the business end of the tie behind the standing part to the left, bring across the front to the right, then behind to the center. The final motion of tucking the loose end down the front behind the "lr" piece is not considered a "step".
a(4) = 2 because "lrlc" is the only way to tie a tie with 4 half turns. Note that since the number of moves is even, the first step is to go to the left in front of the tie, not behind it. This knot is the standard "four in hand", the most commonly known men's tie knot. By contrast, the second most well known tie knot, the Windsor, is represented by "lcrlcrlc".
a(n) = (2^0 - 1) XOR (2^1 - 1) XOR (2^2 - 1) XOR (2^3 - 1) XOR ... XOR (2^n - 1). - Paul D. Hanna, Nov 05 2011 G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...
a(9) = 341 = 2^8 + 2^6 + 2^4 + 2^2 + 2^0 = 4^4 + 4^3 + 4^2 + 4^1 + 4^0 = A002450(5). a(10) = 682 = 2*a(9) = 2* A002450(5). - Gregory L. Simay, Sep 27 2017
MAPLE
A000975 := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2* A000975(n-1) else 2* A000975(n-1)+1 fi; fi; end;
f:=n-> if n mod 2 = 0 then (2^n-1)/3 else (2^n-2)/3; fi; [seq(f(n), n=0..40)]; # N. J. A. Sloane, Mar 21 2017
MATHEMATICA
Array[Ceiling[2(2^# - 1)/3] &, 41, 0]
RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == a[n - 1] + 2a[n - 2] + 1}, a, {n, 40}] (* or *)
LinearRecurrence[{2, 1, -2}, {0, 1, 2}, 40] (* Harvey P. Dale, Aug 10 2013 *) f[n_] := Block[{exp = n - 2}, Sum[2^i, {i, exp, 0, -2}]]; Array[f, 33] (* Robert G. Wilson v, Oct 30 2015 *) f[s_List] := Block[{a = s[[-1]]}, Append[s, If[OddQ@ Length@ s, 2a + 1, 2a]]]; Nest[f, {0}, 32] (* Robert G. Wilson v, Jul 20 2017 *)
PROG
(PARI) {a(n) = if( n<0, 0, 2 * 2^n \ 3)}; /* Michael Somos, Sep 04 2006 */ (PARI) a(n)=if(n<=0, 0, bitxor(a(n-1), 2^n-1)) \\ Paul D. Hanna, Nov 05 2011 (PARI) concat(0, Vec(x/(1-2*x-x^2+2*x^3) + O(x^100))) \\ Altug Alkan, Oct 30 2015 (PARI) {a(n) = (4*2^n - 3 - (-1)^n) / 6}; /* Michael Somos, Jul 23 2017 */ (Haskell)
a000975 n = a000975_list !! n
a000975_list = 0 : 1 : map (+ 1)
(zipWith (+) (tail a000975_list) (map (* 2) a000975_list))
(Magma) [(2^(n+1) - 2 + (n mod 2))/3: n in [0..40]]; // Vincenzo Librandi, Mar 18 2015 (GAP) List([0..35], n->(2^(n+1)-2+(n mod 2))/3); # Muniru A Asiru, Nov 01 2018 (Python)
def a(n): return (2**(n+1) - 2 + (n%2))//3
CROSSREFS
Cf. A000295, A005578, A015441, A043291, A053404, A059260, A077854, A119440, A127824, A130125, A135228, A155051, A179970, A264784.
Number of alternating permutations of order n.
(Formerly M1235 N0472)
+0
122
1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, 707584, 5405530, 44736512, 398721962, 3807514624, 38783024290, 419730685952, 4809759350882, 58177770225664, 740742376475050, 9902996106248192, 138697748786275802, 2030847773013704704, 31029068327114173810
COMMENTS
For n>1, a(n) is the number of permutations of order n with the length of longest run equal 2.
Number of inversion sequences of length n where all consecutive subsequences i,j,k satisfy i >= j < k or i < j >= k. a(4) = 10: 0010, 0011, 0020, 0021, 0022, 0101, 0102, 0103, 0112, 0113. - Alois P. Heinz, Oct 16 2019
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
C. Davis, Problem 4755, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. Chandler Davis, Problem 4755: A Permutation Problem, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. [Denoted by P_n in solution.] [Annotated scanned copy]
FORMULA
a(n) = coefficient of x^(n-1)/(n-1)! in power series expansion of (tan(x) + sec(x))^2 = (tan(x)+1/cos(x))^2.
a(n) = coefficient of x^n/n! in power series expansion of 2*(tan(x) + sec(x)) - 2 - x. - Michael Somos, Feb 05 2011 a(n) = 4*|Li_{-n}(i)| - [n=1] = Sum_{m=0..n/2} (-1)^m*2^(1-k)*Sum_{j=0..k} binomial(k,j)*(-1)^j*(k-2*j)^(n+1)/k - [n=1], where k = k(m) = n+1-2*m and [n=1] equals 1 if n=1 and zero else; Li denotes the polylogarithm (and i^2 = -1). - M. F. Hasler, May 20 2012 Let E(x) = 2/(1-sin(x))-1 (essentially the e.g.f.), then
E(x) = -1 + 2*(-1/x + 1/(1-x)/x - x^3/((1-x)*((1-x)*G(0) + x^2))) where G(k) = (2*k+2)*(2*k+3)-x^2+(2*k+2)*(2*k+3)*x^2/G(k+1); (continued fraction, Euler's 1st kind, 1-step).
E(x) = -1 + 2*(-1/x + 1/(1-x)/x - x^3/((1-x)*((1-x)*G(0) + x^2))) where G(k) = 8*k + 6 - x^2/(1 + (2*k+2)*(2*k+3)/G(k+1)); (continued fraction, Euler's 2nd kind, 2-step).
E(x) = (tan(x) + sec(x))^2 = -1 + 2/(1-x*G(0)) where G(k) = 1 - x^2/(2*(2*k+1)*(4*k+3) - 2*x^2*(2*k+1)*(4*k+3)/(x^2 - 4*(k+1)*(4*k+5)/G(k+1))); (continued fraction, 3rd kind, 3-step).
(End)
G.f.: conjecture: 2*T(0)/(1-x) -1, where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-x*(k+1))*(1-x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 19 2013
EXAMPLE
1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 32*x^5 + 122*x^6 + 544*x^7 + 2770*x^8 + ...
The a(0) = 1 through a(4) = 10 permutations:
() (1) (1,2) (1,3,2) (1,3,2,4)
(2,1) (2,1,3) (1,4,2,3)
(2,3,1) (2,1,4,3)
(3,1,2) (2,3,1,4)
(2,4,1,3)
(3,1,4,2)
(3,2,4,1)
(3,4,1,2)
(4,1,3,2)
(4,2,3,1)
(End)
MAPLE
# With Eulerian polynomials:
A := (n, x) -> `if`(n<2, 1/2/(1+I)^(1-n), add(add((-1)^j*binomial(n+1, j)*(m+1-j)^n, j=0..m)*x^m, m=0..n-1)):
A001250 := n -> 2*(I-1)^(1-n)*exp(I*(n-1)*Pi/2)*A(n, I);
# second Maple program:
b:= proc(u, o) option remember;
`if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
end:
a:= n-> `if`(n<2, 1, 2)*b(n, 0):
MATHEMATICA
Table[Length[Select[Permutations[Range[n]], And@@(!(OrderedQ[#]||OrderedQ[Reverse[#]])&/@Partition[#, 3, 1])&]], {n, 8}] (* Gus Wiseman, Jun 21 2021 *) a[0]:=1; a[1]:=1; a[n_]:=a[n]=1/(n (n-1)) Sum[a[n-1-k] a[k] k, {k, 1, n-1}]; Join[{a[0], a[1]}, Map[2 #! a[#]&, Range[2, 24]]] (* Oliver Seipel, May 27 2024 *)
PROG
(PARI) {a(n) = local(v=[1], t); if( n<0, 0, for( k=2, n+3, t=0; v = vector( k, i, if( i>1, t += v[k+1 - i]))); v[3])} /* Michael Somos, Feb 03 2004 */ (PARI) {a(n) = if( n<0, 0, n! * polcoeff( (tan(x + x * O(x^n)) + 1 / cos(x + x * O(x^n)))^2, n))} /* Michael Somos, Feb 05 2011 */ (PARI) A001250(n)=sum(m=0, n\2, my(k); (-1)^m*sum(j=0, k=n+1-2*m, binomial(k, j)*(-1)^j*(k-2*j)^(n+1))/k>>k)*2-(n==1) \\ M. F. Hasler, May 19 2012 (Sage) # Algorithm of L. Seidel (1877)
R = [1]; A = {-1:0, 0:2}; k = 0; e = 1
for i in (0..n) :
Am = 0; A[k + e] = 0; e = -e
for j in (0..i) : Am += A[k]; A[k] = Am; k += e
if i > 1 : R.append(A[-i//2] if i%2 == 0 else A[i//2])
return R
(PARI)
x='x+O('x^66);
egf=2*(tan(x)+1/cos(x))-2-x;
Vec(serlaplace(egf))
(Haskell)
a001250 n = if n == 1 then 1 else 2 * a000111 n
(Python)
from itertools import accumulate, islice
def A001250_gen(): # generator of terms yield from (1, 1)
blist = (0, 2)
while True:
yield (blist := tuple(accumulate(reversed(blist), initial=0)))[-1]
CROSSREFS
The version for permutations of prime indices is A345164. The version for patterns is A345194. A049774 counts permutations avoiding adjacent (1,2,3).
A344614 counts compositions avoiding adjacent (1,2,3) and (3,2,1).
A344615 counts compositions avoiding the weak adjacent pattern (1,2,3).
A344654 counts partitions without a wiggly permutation, ranked by A344653.
A345170 counts partitions with a wiggly permutation, ranked by A345172.
Cf. A000041, A003242, A032020, A056986, A261962, A325534, A325535, A335452, A344652, A344740, A345165.
Number of n-stacks with strictly receding walls, or the number of Type A partitions of n in the sense of Auluck (1951).
(Formerly M0644 N0238)
+0
60
1, 1, 1, 1, 2, 3, 5, 7, 10, 14, 19, 26, 35, 47, 62, 82, 107, 139, 179, 230, 293, 372, 470, 591, 740, 924, 1148, 1422, 1756, 2161, 2651, 3244, 3957, 4815, 5844, 7075, 8545, 10299, 12383, 14859, 17794, 21267, 25368, 30207, 35902, 42600, 50462, 59678, 70465, 83079, 97800, 114967, 134956, 158205, 185209, 216546, 252859
COMMENTS
Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1 (smooth means that successive parts differ by at most one), see example. Dropping the requirement for unimodality gives A186085. - Joerg Arndt, Dec 09 2012 Number of weakly unimodal compositions of n where the maximal part m appears at least m times, see example. - Joerg Arndt, Jun 11 2013 Also weakly unimodal compositions of n with first part 1, maximal up-step 1, and no consecutive up-steps; see example. The smooth weakly unimodal compositions are recovered by shifting all rows above the bottom row to the left by one position with respect to the next lower row. - Joerg Arndt, Mar 30 2014 It would seem from Stanley that he regards a(0)=0 for this sequence and A001523. - Michael Somos, Feb 22 2015 Also the number of odd-length compositions of n with alternating parts strictly decreasing. These are finite odd-length sequences q of positive integers summing to n such that q(i) > q(i+2) for all possible i. The even-length version is A064428. For example, the a(1) = 1 through a(9) = 14 compositions are: (1) (2) (3) (4) (5) (6) (7) (8) (9)
(211) (221) (231) (241) (251) (261)
(311) (312) (322) (332) (342)
(321) (331) (341) (351)
(411) (412) (413) (423)
(421) (422) (432)
(511) (431) (441)
(512) (513)
(521) (522)
(611) (531)
(612)
(621)
(711)
(32211)
(End)
In the Ferrers diagram of a partition x of n, count the dots in each diagonal parallel to the main diagonal (starting at the top-right, say). The result diag(x) is a smooth weakly unimodal composition of n into positive parts such that the first and last part are 1. For example, diag(5541) = 11233221. The function diag is many-to-one; the size of its codomain as a set is a(n). If diag(x) = diag(y), each hook of x can be slid by the same amount past the main diagonal to get y. For example, diag(5541) = diag(44331). - George Beck, Sep 26 2021 Conjecture: Also the number of integer partitions y of n with a fixed point y(i) = i. These partitions are ranked by A352827. The conjecture is stated at A238395, but Resta tells me he may not have had a proof. The a(1) = 1 through a(8) = 10 partitions are: (1) (11) (111) (22) (32) (42) (52) (62)
(1111) (221) (222) (322) (422)
(11111) (321) (421) (521)
(2211) (2221) (2222)
(111111) (3211) (3221)
(22111) (4211)
(1111111) (22211)
(32111)
(221111)
(11111111)
Note that these are not the same partitions (compare A352827 to A352874), only the same count (apparently). (End)
The above conjecture is true. See Section 4 of the Blecher-Knopfmacher paper in the Links section. - Jeremy Lovejoy, Sep 26 2022
REFERENCES
G. E. Andrews, The reasonable and unreasonable effectiveness of number theory in statistical mechanics, pp. 21-34 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
G. E. Andrews, Three-quadrant Ferrers graphs, Indian J. Math., 42 (No. 1, 2000), 1-7.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see section 2.5 on page 76.
LINKS
E. M. Wright, Stacks, III, Quart. J. Math. Oxford, 23 (1972), 153-158.
FORMULA
G.f.: 1 + ( Sum_{k>=1} -(-1)^k * x^(k*(k+1)/2) ) / ( Product_{k>=1} 1-x^k ).
G.f.: 1 + ( Sum_{n>=1} q^(n^2) / ( Product_{k=1..n-1} 1-q^k )^2 * (1-q^n) ) ). - Joerg Arndt, Dec 09 2012 a(n) ~ exp(Pi*sqrt(2*n/3)) / (8*sqrt(3)*n) [Auluck, 1951]. - Vaclav Kotesovec, Sep 26 2016
EXAMPLE
For a(6)=5 we have the following stacks:
.x... ..x.. ...x. .xx.
xxxxx xxxxx xxxxx xxxx xxxxxx
.
There are a(9) = 14 smooth weakly unimodal compositions of 9:
01: [ 1 1 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 1 2 1 ]
03: [ 1 1 1 1 1 2 1 1 ]
04: [ 1 1 1 1 2 1 1 1 ]
05: [ 1 1 1 1 2 2 1 ]
06: [ 1 1 1 2 1 1 1 1 ]
07: [ 1 1 1 2 2 1 1 ]
08: [ 1 1 2 1 1 1 1 1 ]
09: [ 1 1 2 2 1 1 1 ]
10: [ 1 1 2 2 2 1 ]
11: [ 1 2 1 1 1 1 1 1 ]
12: [ 1 2 2 1 1 1 1 ]
13: [ 1 2 2 2 1 1 ]
14: [ 1 2 3 2 1 ]
(End)
There are a(9) = 14 weakly unimodal compositions of 9 where the maximal part m appears at least m times:
01: [ 1 1 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 2 2 ]
03: [ 1 1 1 1 2 2 1 ]
04: [ 1 1 1 2 2 1 1 ]
05: [ 1 1 1 2 2 2 ]
06: [ 1 1 2 2 1 1 1 ]
07: [ 1 1 2 2 2 1 ]
08: [ 1 2 2 1 1 1 1 ]
09: [ 1 2 2 2 1 1 ]
10: [ 1 2 2 2 2 ]
11: [ 2 2 1 1 1 1 1 ]
12: [ 2 2 2 1 1 1 ]
13: [ 2 2 2 2 1 ]
14: [ 3 3 3 ]
(End)
There are a(9) = 14 compositions of 9 with first part 1, maximal up-step 1, and no consecutive up-steps:
01: [ 1 1 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 1 1 2 ]
03: [ 1 1 1 1 1 1 2 1 ]
04: [ 1 1 1 1 1 2 1 1 ]
05: [ 1 1 1 1 1 2 2 ]
06: [ 1 1 1 1 2 1 1 1 ]
07: [ 1 1 1 1 2 2 1 ]
08: [ 1 1 1 2 1 1 1 1 ]
09: [ 1 1 1 2 2 1 1 ]
10: [ 1 1 1 2 2 2 ]
11: [ 1 1 2 1 1 1 1 1 ]
12: [ 1 1 2 2 1 1 1 ]
13: [ 1 1 2 2 2 1 ]
14: [ 1 1 2 2 3 ]
(End)
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 5*x^6 + 7*x^7 + 10*x^8 + 14*x^9 + ...
MAPLE
b:= proc(n, i, t) option remember; `if`(n<=0, `if`(i=1, 1, 0),
`if`(n<0 or i<1, 0, b(n-i, i, t)+b(n-(i-1), i-1, false)+
`if`(t, b(n-(i+1), i+1, t), 0)))
end:
a:= n-> b(n-1, 1, true):
# second Maple program:
local r, a;
a := 0 ;
if n = 0 then
return 1 ;
end if;
for r from 1 do
if r*(r+1) > 2*n then
return a;
else
a := a-(-1)^r*combinat[numbpart](n-r*(r+1)/2) ;
end if;
end do:
MATHEMATICA
max = 50; f[x_] := 1 + Sum[-(-1)^k*x^(k*(k+1)/2), {k, 1, max}] / Product[(1-x^k), {k, 1, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Dec 27 2011, after g.f. *) b[n_, i_, t_] := b[n, i, t] = If[n <= 0, If[i == 1, 1, 0], If[n<0 || i<1, 0, b[n-i, i, t] + b[n - (i-1), i-1, False] + If[t, b[n - (i+1), i+1, t], 0]]]; a[n_] := b[n-1, 1, True]; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Dec 01 2015, after Alois P. Heinz *) Flatten[{1, Table[Sum[(-1)^(j-1)*PartitionsP[n-j*((j+1)/2)], {j, 1, Floor[(Sqrt[8*n + 1] - 1)/2]}], {n, 1, 60}]}] (* Vaclav Kotesovec, Sep 26 2016 *) ici[q_]:=And@@Table[q[[i]]>q[[i+2]], {i, Length[q]-2}];
Table[If[n==0, 1, Length[Select[Join@@Permutations/@Select[IntegerPartitions[n], OddQ@*Length], ici]]], {n, 0, 15}] (* Gus Wiseman, Mar 30 2021 *)
PROG
(PARI) {a(n) = if( n<1, n==0, polcoeff( sum(k=1, (sqrt(1+8*n) - 1)\2, -(-1)^k * x^((k + k^2)/2)) / eta(x + x * O(x^n)), n))}; /* Michael Somos, Jul 22 2003 */ (PARI) N=66; q='q+O('q^N);
Vec( 1 + sum(n=1, N, q^(n^2)/(prod(k=1, n-1, 1-q^k)^2*(1-q^n)) ) ) \\ Joerg Arndt, Dec 09 2012 (Sage)
if n < 4: return 1
return (number_of_partitions(n) - [p.crank() for p in Partitions(n)].count(0))/2
CROSSREFS
Conjectured to be column k = 1 of A352833. These partitions (positive crank) are ranked by A352874. A064391 counts partitions by crank.
A257989 gives the crank of the partition with Heinz number n.
a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1) + a(n-2) + a(n-4).
(Formerly M1059)
+0
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
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.
For n = 0, 1, 2, a(n) = n; thereafter, a(n) = 2*a(n-1) - a(n-2) + a(n-3).
(Formerly M0709)
+0
32
0, 1, 2, 3, 5, 9, 16, 28, 49, 86, 151, 265, 465, 816, 1432, 2513, 4410, 7739, 13581, 23833, 41824, 73396, 128801, 226030, 396655, 696081, 1221537, 2143648, 3761840, 6601569, 11584946, 20330163, 35676949, 62608681, 109870576, 192809420, 338356945, 593775046
COMMENTS
Number of compositions of n into parts congruent to {1,2} mod 4. - Vladeta Jovovic, Mar 10 2005 a(n)/a(n-1) tends to A109134; an eigenvalue of the matrix M and a root to the characteristic polynomial. - Gary W. Adamson, May 25 2007 Starting with offset 1 = INVERT transform of (1, 1, 0, 0, 1, 1, 0, 0, ...). - Gary W. Adamson, May 04 2009 a(n-2) is the top left entry of the n-th power of the 3 X 3 matrix [0, 1, 0; 0, 1, 1; 1, 0, 1] or of the 3 X 3 matrix [0, 0, 1; 1, 1, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014 Counts closed walks of length (n+2) at a vertex of a unidirectional triangle containing a loop on remaining two vertices. - David Neil McGrath, Sep 15 2014 Also the number of binary words of length n that begin with 1 and avoid the subword 101. a(5) = 9: 10000, 10001, 10010, 10011, 11000, 11001, 11100, 11110, 11111. - Alois P. Heinz, Jul 21 2016 Also the number of binary words of length n-1 such that every two consecutive 0s are immediately followed by at least two consecutive 1s. a(4) = 5: 010, 011, 101, 110, 111. - Jerrold Grossman, May 03 2024
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020. Christian Ennis, William Holland, Omer Mujawar, Aadit Narayanan, Frank Neubrander, Marie Neubrander, and Christina Simino, Words in Random Binary Sequences I, arXiv:2107.01029 [math.GM], 2021.
FORMULA
G.f.: x/(1-2*x+x^2-x^3).
a(n) = Sum_{k=0..[(2n-1)/3]} binomial(n-1-[k/2], k), where [x]=floor(x). (End)
a(n) = Sum_{k=0..n} binomial(n-k, 2*k+1).
23*a_n = 3*P_{2n+2} + 7*P_{2n+1} - 2*P_{2n}, where P_n are the Perrin numbers, A001608. - Don Knuth, Dec 09 2008 G.f. (1-z)*(1+z^2)/(1-2*z+z^2-z^3) for the augmented version 1, 1, 2, 3, 5, 9, 16, 28, 49, 86, 151, ... was given in Simon Plouffe's thesis of 1992. M^n*[1,0,0] = [a(n-2), a(n-1), a]; where M = the 3 X 3 matrix [0,1,0; 0,0,1; 1,-1,2]. Example M^5*[1,0,0] = [3,5,9]. - Gary W. Adamson, May 25 2007 G.f.: 1/( 1 - Sum_{k>=0} x*(x-x^2+x^3)^k ) - 1. - Joerg Arndt, Sep 30 2012 a(n) = Sum_{k=0..n} binomial( n-floor((k+1)/2), n-floor((3k-1)/2) ). - John Molokach, Jul 21 2013 a(n) = Sum_{k=1..floor((2n+2)/3)} (binomial(n - floor((4*n+15-6*k+(-1)^k)/12), n - floor((4*n+15-6*k+(-1)^k)/12) - floor((2*n-1)/3) + k - 1). - John Molokach, Jul 24 2013 a(n) = round( A001608(2n+1)*r) where r is the real root of 23*x^3 - 23*x^2 + 8*x - 1 = 0, r = 0.4114955... - Richard Turk, Oct 24 2019 a(n) ~ (19 - r + 11*r^2) / (23 * r^(n-1)), where r = 0.569840290998... is the root of the equation r*(2 - r + r^2) = 1. - Vaclav Kotesovec, Apr 14 2024 a(n) = n*3F2(1/3-n/3,2/3-n/3,1-n/3;-n,3/2;27/4). - R. J. Mathar, Jun 27 2024
EXAMPLE
G.f. = x + 2*x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 16*x^6 + 28*x^7 + 49*x^8 + ...
a(n) is the number of subsets of {1..n} containing n such that if x and x + 2 are both in the subset, then so is x + 1. For example, the a(1) = 1 through a(5) = 9 subsets are:
{1} {2} {3} {4} {5}
{1,2} {2,3} {1,4} {1,5}
{1,2,3} {3,4} {2,5}
{2,3,4} {4,5}
{1,2,3,4} {1,2,5}
{1,4,5}
{3,4,5}
{2,3,4,5}
{1,2,3,4,5}
(End)
MAPLE
option remember ;
if n <=2 then
n;
else
2*procname(n-1)-procname(n-2)+procname(n-3) ;
end if;
end proc:
MATHEMATICA
Table[Sum[Binomial[n - Floor[(k + 1)/2], n - Floor[(3 k - 1)/2]], {k, 0, n}], {n, 0, 100}] (* John Molokach, Jul 21 2013 *) Table[Sum[Binomial[n - Floor[(4 n + 15 - 6 k + (-1)^k)/12], n - Floor[(4 n + 15 - 6 k + (-1)^k)/12] - Floor[(2 n - 1)/3] + k - 1], {k, 1, Floor[(2 n + 2)/3]}], {n, 0, 100}] (* John Molokach, Jul 25 2013 *) a[ n_] := If[ n < 0, SeriesCoefficient[ x^2 / (1 - x + 2 x^2 - x^3), {x, 0, -n}], SeriesCoefficient[ x / (1 - 2 x + x^2 - x^3), {x, 0, n}]]; (* Michael Somos, Dec 13 2013 *) RecurrenceTable[{a[0]==0, a[1]==1, a[2]==2, a[n]==2a[n-1]-a[n-2]+a[n-3]}, a, {n, 40}] (* Harvey P. Dale, May 13 2018 *) Table[Length[Select[Subsets[Range[n]], MemberQ[#, n]&&!MatchQ[#, {___, x_, y_, ___}/; x+2==y]&]], {n, 0, 10}] (* Gus Wiseman, Nov 25 2019 *)
PROG
(PARI) {a(n) = sum(k=0, (2*n-1)\3, binomial(n-1-k\2, k))}
(Haskell)
a005314 n = a005314_list !! n
a005314_list = 0 : 1 : 2 : zipWith (+) a005314_list
(tail $ zipWith (-) (map (2 *) $ tail a005314_list) a005314_list)
(PARI) {a(n) = if( n<0, polcoeff( x^2 / (1 - x + 2*x^2 - x^3) + x * O(x^-n), -n), polcoeff( x / (1 - 2*x + x^2 - x^3) + x * O(x^n), n))}; /* Michael Somos, Sep 18 2012 */ (Magma) [0] cat [n le 3 select n else 2*Self(n-1) - Self(n-2) + Self(n-3):n in [1..35]]; // Marius A. Burtea, Oct 24 2019 (Magma) R<x>:=PowerSeriesRing(Integers(), 36); [0] cat Coefficients(R!( x/(1-2*x+x^2-x^3))); // Marius A. Burtea, Oct 24 2019 (SageMath)
def A005314(n): return sum( binomial(n-k, 2*k+1) for k in range(floor((n+2)/3)) )
CROSSREFS
Equals row sums of triangle A099557. Equals row sums of triangle A224838. Cf. A011973 (starting with offset 1 = Falling diagonal sums of triangle with rows displayed as centered text). First differences of A005251, shifted twice to the left.
Expansion of e.g.f. (2 - e^x)^(-2).
(Formerly M1866)
+0
82
1, 2, 8, 44, 308, 2612, 25988, 296564, 3816548, 54667412, 862440068, 14857100084, 277474957988, 5584100659412, 120462266974148, 2772968936479604, 67843210855558628, 1757952715142990612, 48093560991292628228, 1385244691781856307124
COMMENTS
Exponential self-convolution of numbers of preferential arrangements.
Number of compatible bipartitional relations on a set of cardinality n. - Ralf Stephan, Apr 27 2003 With an extra 1 at the beginning, coefficients of the formal (divergent) series expansion at infinity of Sum_{k>=0} 1/binomial(x,k) = 1+1/x+2/x^2+8/x^3+... Also Sum_{k>=0} k!/x^k Product_{i=1..k-1} 1/(1-i/x) yields a generating function in 1/x. - Roland Bacher, Nov 21 2000 a(n) is the total number of open sets summed over all chain topologies that can be placed on an n-set. A chain topology is a topology whose open sets can be totally ordered by inclusion. - Geoffrey Critzer, Apr 06 2017 Also the number of length n + 1 sequences covering an initial interval of positive integers with no adjacent equal parts (anti-runs). For example, the a(0) = 1 through a(2) = 8 anti-runs are:
(1) (1,2) (1,2,1)
(2,1) (1,2,3)
(1,3,2)
(2,1,2)
(2,1,3)
(2,3,1)
(3,1,2)
(3,2,1)
Also the number of ordered set partitions of {1,...,n + 1} with no two successive vertices in the same block. For example, the a(0) = 1 through a(2) = 8 ordered set partitions are:
{{1}} {{1},{2}} {{1,3},{2}}
{{2},{1}} {{2},{1,3}}
{{1},{2},{3}}
{{1},{3},{2}}
{{2},{1},{3}}
{{2},{3},{1}}
{{3},{1},{2}}
{{3},{2},{1}}
(End)
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 294.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
E.g.f.: 1/(2-exp(x))^2.
a(n) = D^n(1/(1-x)^2) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A000670 and A052841. - Peter Bala, Nov 25 2011 E.g.f.: 1/(2-exp(x))^2 = 1/(G(0) + 4), G(k) = 1-4/((2^k)-x*(4^k)/((2^k)*x-(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 15 2011 O.g.f.: Sum_{n>=0} (2*n)!/n! * x^n / Product_{k=1..n} (1 + (n+k)*x). - Paul D. Hanna, Jan 03 2013 G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - (k+1)/(1-k*x)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 15 2013 G.f.: 1/G(0) where G(k) = 1 - x*(k+2)/( 1 - 2*x*(k+1)/G(k+1) ); (continued fraction ). - Sergei N. Gladkovskii, Mar 23 2013 a(n) = Sum_{k=0..n} Stirling2(n,k)*(k + 1)!. - Ilya Gutkovskiy, Jul 25 2018 a(0) = 1; a(n) = Sum_{k=1..n} (k/n + 1) * binomial(n,k) * a(n-k).
a(0) = 1; a(n) = 2*a(n-1) - 2*Sum_{k=1..n-1} (-1)^k * binomial(n-1,k) * a(n-k). (End)
MAPLE
b:= proc(n, m) option remember;
`if`(n=0, (m+1)!, m*b(n-1, m)+b(n-1, m+1))
end:
a:= n-> b(n, 0):
MATHEMATICA
f[n_] := Sum[(i + j)^n/2^(2 + i + j), {i, 0, Infinity}, {j, 0, Infinity}]; Array[f, 20, 0] (* Vladimir Reshetnikov, Dec 31 2008 *) a[n_] := (-1)^n (PolyLog[-n-1, 2] - PolyLog[-n, 2])/4; Array[f, 20, 0] (* Vladimir Reshetnikov, Jan 23 2011 *) Range[0, 19]! CoefficientList[Series[(2 - Exp@ x)^-2, {x, 0, 19}], x] (* Robert G. Wilson v, Jan 23 2011 *) nn = 19; Range[0, nn]! CoefficientList[Series[1 + D[u^2 (Exp[z] - 1)/(1 - u (Exp[z] - 1)), u] /. u -> 1, {z, 0, nn}], z] (* Geoffrey Critzer, Apr 06 2017 *) allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n], FreeQ[Differences[#], 0]&]], {n, 0, 6}] (* Gus Wiseman, Jun 10 2020 *) With[{nn=20}, CoefficientList[Series[1/(2-E^x)^2, {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Oct 02 2021 *)
PROG
(PARI) a(n)=if(n<0, 0, n!*polcoeff(subst(1/(1-y)^2, y, exp(x+x*O(x^n))-1), n))
(PARI) a(n)=polcoeff(sum(m=0, n, (2*m)!/m!*x^m/prod(k=1, m, 1+(m+k)*x+x*O(x^n))), n)
(Maxima) t(n):=sum(stirling2(n, k)*k!, k, 0, n);
makelist(sum(binomial(n, k)*t(k)*t(n-k), k, 0, n), n, 0, 20);
CROSSREFS
Anti-run compositions are counted by A003242. A triangle counting maximal anti-runs of compositions is A106356. Anti-runs of standard compositions are counted by A333381. Adjacent unequal pairs in standard compositions are counted by A333382.
a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.
(Formerly M1005)
+0
65
1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, 273, 441, 714, 1156, 1870, 3025, 4895, 7921, 12816, 20736, 33552, 54289, 87841, 142129, 229970, 372100, 602070, 974169, 1576239, 2550409, 4126648, 6677056, 10803704, 17480761, 28284465, 45765225, 74049690, 119814916
COMMENTS
Number of compositions of n into 1's, 3's and 4's. - Len Smiley, May 08 2001 The sum of any two alternating terms (terms separated by one term) produces a number from the Fibonacci sequence. (e.g. 4+9=13, 9+25=34, 6+15=21, etc.) Taking square roots starting from the first term and every other term after, we get the Fibonacci sequence. - Sreyas Srinivasan (sreyas_srinivasan(AT)hotmail.com), May 02 2002
(1 + x + 2*x^2 + x^3)/(1 - x - x^3 - x^4) = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 15*x^5 + 25*x^6 + 40*x^7 + ... is the g.f. for the number of binary strings of length where neither 101 nor 111 occur. [Lozansky and Rousseau] Or, equivalently, where neither 000 nor 010 occur.
Equivalently, a(n+2) is the number of length-n binary strings with no two set bits with distance 2; see fxtbook link. - Joerg Arndt, Jul 10 2011 a(n) is the number of words written with the letters "a" and "b", with the following restriction: any "a" must be followed by at least two letters, the second of which is a "b". - Bruno Petazzoni (bpetazzoni(AT)ac-creteil.fr), Oct 31 2005. [This is also equivalent to the previous two conditions.]
Let a(0) = 1, then a(n) = partial products of Product_{n>2} (F(n)/F(n-1))^2 = 1*1*2*2*(3/2)*(3/2)*(5/3)*(5/3)*(8/5)*(8/5)*.... E.g., a(7) = 15 = 1*1*1*2*2*(3/2)*(3/2)*(5/3). - Gary W. Adamson, Dec 13 2009 Number of permutations satisfying -k <= p(i) - i <= r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1}. - Vladimir Baltic, Mar 07 2012 The 2-dimensional version, which counts sets of pairs no two of which are separated by graph-distance 2, is A273461. - Gus Wiseman, Nov 27 2019 a(n+1) is the number of multus bitstrings of length n with no runs of 4 ones. - Steven Finch, Mar 25 2020
REFERENCES
E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see pp. 157 and 172.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
FORMULA
G.f.: 1 / ((1 + x^2) * (1 - x - x^2)); a(2*n) = F(n+1)^2, a(2*n - 1) = F(n+1)*F(n). a(n) = a(-4-n) * (-1)^n. - Michael Somos, Mar 10 2004 The g.f. -(1+z+2*z^2+z^3)/((z^2+z-1)*(1+z^2)) for the truncated version 1, 2, 4, 6, 9, 15, 25, 40, ... was given in the Simon Plouffe thesis of 1992. [edited by R. J. Mathar, May 13 2008] a(n) = round((-(1/5)*sqrt(5) - 1/5)*(-2*1/(-sqrt(5)+1))^n/(-sqrt(5)+1) + ((1/5)*sqrt(5) - 1/5)*(-2*1/( sqrt(5)+1))^n/(sqrt(5)+1)).
G.f.: 1/(1-x-x^2)/(1+x^2). (End)
a(n) = (-i)^n*Sum{k=0..n} U(n-2k, i/2) where i^2=-1. - Paul Barry, Nov 15 2003 a(n) = Sum_{k=0..floor(n/2)} (-1)^k*F(n-2k+1). - Paul Barry, Oct 12 2007 F(floor(n/2) + 2)^(n mod 2)*F(floor(n/2) + 1)^(2 - (n mod 2)) where F(n) is the n-th Fibonacci number. - David Nacin, Feb 29 2012 a(n+1)*a(n+3) = a(n)*a(n+2) + a(n+1)*a(n+2) for all n in Z. - Michael Somos, Jan 19 2014 a(n) = Sum_{j=0..floor(n/3)} Sum_{k=0..j} binomial(n-3j,k)*binomial(j,k)*2^k. - Tony Foster III, Sep 18 2017 E.g.f.: (2*cos(x) + sin(x) + exp(x/2)*(3*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Mar 12 2024
EXAMPLE
G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 6*x^5 + 9*x^6 + 15*x^7 + 25*x^8 + 40*x^9 + ...
The a(2) = 1 through a(7) = 15 subsets with no two elements differing by 2:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{1,2} {3} {3} {3}
{1,2} {4} {4}
{2,3} {1,2} {5}
{1,4} {1,2}
{2,3} {1,4}
{3,4} {1,5}
{2,3}
{2,5}
{3,4}
{4,5}
{1,2,5}
{1,4,5}
(End)
MATHEMATICA
LinearRecurrence[{1, 0, 1, 1}, {1, 1, 1, 2}, 50] (* Harvey P. Dale, Jul 13 2011 *) Table[Fibonacci[Floor[n/2] + 2]^Mod[n, 2]*Fibonacci[Floor[n/2] + 1]^(2 - Mod[n, 2]), {n, 0, 40}] (* David Nacin, Feb 29 2012 *) a[ n_] := Fibonacci[ Quotient[ n+2, 2]] Fibonacci[ Quotient[ n+3, 2]] (* Michael Somos, Jan 19 2014 *) Table[Length[Select[Subsets[Range[n]], !MatchQ[#, {___, x_, ___, y_, ___}/; x+2==y]&]], {n, 10}] (* Gus Wiseman, Nov 27 2019 *)
PROG
(PARI) {a(n) = fibonacci( (n+2)\2 ) * fibonacci( (n+3)\2 )} /* Michael Somos, Mar 10 2004 */ (PARI) Vec(1/(1-x-x^3-x^4)+O(x^66))
(Magma) [ n eq 1 select 1 else n eq 2 select 1 else n eq 3 select 1 else n eq 4 select 2 else Self(n-1)+Self(n-3)+ Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 20 2011 (Python)
def a(n, adict={0:1, 1:1, 2:1, 3:2}):
if n in adict:
return adict[n]
adict[n]=a(n-1)+a(n-3)+a(n-4)
(Haskell)
a006498 n = a006498_list !! n
a006498_list = 1 : 1 : 1 : 2 : zipWith (+) (drop 3 a006498_list)
(zipWith (+) (tail a006498_list) a006498_list)
CROSSREFS
Diagonal sums of number triangle A059259. Numbers whose binary expansion has no subsequence (1,0,1) are A048716.
Dual pairs of integrals arising from reflection coefficients.
(Formerly M3284)
+0
10
0, 1, 1, 4, 6, 16, 28, 64, 120, 256, 496, 1024, 2016, 4096, 8128, 16384, 32640, 65536, 130816, 262144, 523776, 1048576, 2096128, 4194304, 8386560, 16777216, 33550336, 67108864, 134209536, 268435456, 536854528, 1073741824, 2147450880, 4294967296, 8589869056
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
G.f.: x*(1-x)/((1-2*x)*(1-2*x^2)).
a(n) = 2*a(n-1)+2*a(n-2)-4*a(n-3).
a(n) = 2^n/2-2^(n/2)*(1+(-1)^n)/4. (End)
G.f.: (1+x*Q(0))*x/(1-x), where Q(k)= 1 - 1/(2^k - 2*x*2^(2*k)/(2*x*2^k - 1/(1 + 1/(2*2^k - 8*x*2^(2*k)/(4*x*2^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 22 2013
EXAMPLE
Also the number of integer compositions of n with at least one odd part. For example, the a(1) = 1 through a(5) = 16 compositions are:
(1) (1,1) (3) (1,3) (5)
(1,2) (3,1) (1,4)
(2,1) (1,1,2) (2,3)
(1,1,1) (1,2,1) (3,2)
(2,1,1) (4,1)
(1,1,1,1) (1,1,3)
(1,2,2)
(1,3,1)
(2,1,2)
(2,2,1)
(3,1,1)
(1,1,1,2)
(1,1,2,1)
(1,2,1,1)
(2,1,1,1)
(1,1,1,1,1)
(End)
MAPLE
f := n-> if n mod 2 = 0 then 2^(n-1)-2^((n-2)/2) else 2^(n-1); fi;
MATHEMATICA
LinearRecurrence[{2, 2, -4}, {0, 1, 1}, 30] (* Harvey P. Dale, Nov 30 2015 *) Table[2^(n-1)-If[EvenQ[n], 2^(n/2-1), 0], {n, 0, 15}] (* Gus Wiseman, Feb 26 2022 *)
PROG
(Magma) [Floor(2^n/2-2^(n/2)*(1+(-1)^n)/4): n in [0..40]]; // Vincenzo Librandi, Aug 20 2011 (PARI) Vec(x*(1-x)/((1-2*x)*(1-2*x^2)) + O(x^50)) \\ Michel Marcus, Jan 28 2016
CROSSREFS
Even bisection is A006516 = 2^(n-1)*(2^n - 1). A000045(n-1) counts compositions without odd parts, non-singleton A077896.
A003242 counts Carlitz compositions.
A052952 (or A074331) counts non-singleton compositions without even parts.
Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.
+0
157
1, 1, 1, 3, 4, 7, 12, 19, 29, 48, 75, 118, 186, 293, 460, 725, 1139, 1789, 2814, 4422, 6949, 10924, 17168, 26979, 42404, 66644, 104737, 164610, 258707, 406588, 639009, 1004287, 1578363, 2480606, 3898599, 6127152, 9629623, 15134213, 23785388, 37381849, 58750468
COMMENTS
Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.
FORMULA
a(n) = A025048(n) + A025049(n) - 1 = sum_k[ A059881(n, k)] = sum_k[S(n, k) + T(n, k)] - 1 where if n>k>0 S(n, k) = sum_j[T(n - k, j)] over j>k and T(n, k) = sum_j[S(n - k, j)] over k>j (note reversal) and if n>0 S(n, n) = T(n, n) = 1; S(n, k) = A059882(n, k), T(n, k) = A059883(n, k). - Henry Bottomley, Feb 05 2001 a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - Vaclav Kotesovec, Sep 12 2014
EXAMPLE
There are a(7)=19 such compositions of 7:
[ 1] + [ 1 2 1 2 1 ]
[ 2] + [ 1 2 1 3 ]
[ 3] + [ 1 3 1 2 ]
[ 4] + [ 1 4 2 ]
[ 5] + [ 1 5 1 ]
[ 6] + [ 1 6 ]
[ 7] - [ 2 1 3 1 ]
[ 8] - [ 2 1 4 ]
[ 9] + [ 2 3 2 ]
[10] + [ 2 4 1 ]
[11] + [ 2 5 ]
[12] - [ 3 1 2 1 ]
[13] - [ 3 1 3 ]
[14] + [ 3 4 ]
[15] - [ 4 1 2 ]
[16] - [ 4 3 ]
[17] - [ 5 2 ]
[18] - [ 6 1 ]
[19] 0 [ 7 ]
For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'), and for A025049(7)-1=8 the first two parts are decreasing (marked by '-'). (End)
MAPLE
b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
end:
a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
MATHEMATICA
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], wigQ]], {n, 0, 15}] (* Gus Wiseman, Jun 17 2021 *)
PROG
(PARI)
D(n, f)={my(M=matrix(n, n, j, k, k>=j), s=M[, n]); for(b=1, n, f=!f; M=matrix(n, n, j, k, if(k<j, if(f, if(k>1, M[j-k, k-1]), M[j-k, n]-M[j-k, k] ))); for(k=2, n, M[, k]+=M[, k-1]); s+=M[, n]); s~}
seq(n) = concat([1], D(n, 0) + D(n, 1) - vector(n, j, 1)) \\ Andrew Howroyd, Jan 31 2024
CROSSREFS
The version allowing pairs (x,x) is A344604. A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.
Search completed in 0.300 seconds
| 
