login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006498 a(n) = a(n-1)+a(n-3)+a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.
(Formerly M1005)
47
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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 A006498 = partial products of Product_{n=2..inf.(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]

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

T. D. Noe, Table of n, a(n) for n=0..500

D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.

Joerg Arndt, Matters Computational (The Fxtbook), section 14.10.1, p.320

Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135

G. E. Bergum and V. E. Hoggatt, Jr., A combinatorial problem involving recursive sequences and tridiagonal matrices, Fib. Quart., 16 (1978), 113-118.

K. Edwards, A Pascal-like triangle related to the tribonacci numbers, Fib. Q., 46/47 (2008/2009), 18-25.

T. Guardia, D. Jiménez, Fiboquadratic Sequences and Extensions of the Cassini Identity Raised From the Study of Rithmomachia, arXiv preprint arXiv:1509.03177, 2015

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301

Index entries for sequences related to Chebyshev polynomials.

Index entries for two-way infinite sequences

Index entries for linear recurrences with constant coefficients, signature (1, 0, 1, 1).

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.

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). - Vladeta Jovovic, May 03 2002

a(n) = (-i)^n*sum{k=0..n, U(n-2k, i/2)} with 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(2*n - 1) = A001654(n), a(2*n) = A007598(n+1). - Michael Somos, Mar 10 2004

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) = round(1/(1/F(n+2) + 2/F(n+3))), where F(n) = A000045, and 0.5 is rounded to 1. - Richard R. Forberg, Aug 04 2014

5*a(n) = (-1)^floor(n/2)*A000034(n+1) + A000032(n+2). - R. J. Mathar, Sep 16 2017

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

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

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

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)

.return adict[n] # David Nacin, Mar 07 2012

(Haskell)

a006498 n = a006498_list !! n

a006498_list = 1 : 1 : 1 : 2 : zipWith (+) (drop 3 a006498_list)

   (zipWith (+) (tail a006498_list) a006498_list)

-- Reinhard Zumkeller, Apr 07 2012

CROSSREFS

Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.

Diagonal sums of number triangle A059259.

Cf. A001654, A007598.

Cf. A209398.

Sequence in context: A157679 A057602 A171646 * A074677 A179997 A101756

Adjacent sequences:  A006495 A006496 A006497 * A006499 A006500 A006501

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Plouffe g.f. edited by R. J. Mathar, May 13 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 06:09 EDT 2017. Contains 292403 sequences.