cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 23 results. Next

A218439 a(n) = A001609(n)^2, where g.f. of A001609 is x*(1+3*x^2)/(1-x-x^3).

Original entry on oeis.org

1, 1, 16, 25, 36, 100, 225, 441, 961, 2116, 4489, 9604, 20736, 44521, 95481, 205209, 440896, 946729, 2033476, 4368100, 9381969, 20151121, 43283241, 92968164, 199685161, 428904100, 921243904, 1978737289, 4250127249, 9128847025, 19607840784, 42115658841
Offset: 1

Views

Author

Paul D. Hanna, Oct 28 2012

Keywords

Comments

A001609 equals the logarithmic derivative of Narayana's cows sequence A000930.

Examples

			O.g.f.: A(x) = x + x^2 + 16*x^3 + 25*x^4 + 36*x^5 + 100*x^6 + 225*x^7 +...
L.g.f.: L(x) = x + x^2/2 + 16*x^3/3 + 25*x^4/4 + 36*x^5/5 + 100*x^6/6 + 225*x^7/7 +...
where exponentiation yields the g.f. of A218438:
exp(L(x)) = 1 + x + x^2 + 6*x^3 + 12*x^4 + 19*x^5 + 48*x^6 + 110*x^7 +...

Links

Crossrefs

Cf. A000930, A001609, A002478, A112455, A218438.

Programs

  • Mathematica
    Rest[CoefficientList[Series[x*(1 + 14*x^2 + 5*x^3 - 9*x^4 - 9*x^5)/((1 + x^2 - x^3)*(1 - x - 2*x^2 - x^3)), {x, 0, 50}], x]] (* G. C. Greubel, Apr 28 2017 *)
  • PARI
    {a(n)=polcoeff(x*(1+14*x^2+5*x^3-9*x^4-9*x^5)/((1+x^2-x^3)*(1-x-2*x^2-x^3+x*O(x^n))),n)}
for(n=1,40,print1(a(n),", "))

Formula

O.g.f.: x*(1 + 14*x^2 + 5*x^3 - 9*x^4 - 9*x^5)/((1 + x^2 - x^3)*(1 - x - 2*x^2 - x^3)).
Logarithmic derivative of A218438.
a(n) = -2*(-1)^n*A112455(n) +3*A002478(n) -2*A002478(n-1)-2*A002478(n-2), n>1. - R. J. Mathar, Oct 28 2012

A228647 a(n) = A001609(n^2) for n>=1, where g.f. of A001609 is x*(1+3*x^2)/(1-x-x^3).

Original entry on oeis.org

1, 5, 31, 453, 14131, 946781, 136250983, 42115660581, 27961563559891, 39874307297033165, 122134599693975367423, 803522677430288749340325, 11354589189995520431547851761, 344634362031276605039944979868611, 22467750416780812361715214948922598721, 3146114090698891414621617889648190060326821
Offset: 1

Views

Author

Paul D. Hanna, Aug 28 2013

Keywords

Comments

A001609 forms the logarithmic derivative of Narayana's cows sequence A000930.

Examples

			L.g.f.: L(x) = x + 5*x^2/2 + 31*x^3/3 + 453*x^4/4 + 14131*x^5/5 +...
where
exp(L(x)) = 1 + x + 3*x^2 + 13*x^3 + 128*x^4 + 2974*x^5 + 161048*x^6 + 19632276*x^7 +...+ A228648(n)*x^n +...

Crossrefs

Cf. A218439, A228648, A001609, A000930, A231620.

Programs

  • PARI
    {A001609(n)=n*polcoeff(-log(1-x-x^3 +x*O(x^n)), n)}
{a(n)=A001609(n^2)}
for(n=1,20,print1(a(n),", "))

Formula

Equals the logarithmic derivative of A228648.

A228648 G.f.: exp( Sum_{n>=1} A001609(n^2)*x^n/n ), where the l.g.f. of A001609 is -log(1-x-x^3).

Original entry on oeis.org

1, 1, 3, 13, 128, 2974, 161048, 19632276, 5284440413, 3112165670205, 3990553641147871, 11107142249379896577, 66971338268043285905138, 873496931276771661395863398, 24617613776054408956962658439353, 1497874647146694311608664496205734267, 196633628592570082430451891781759097556806
Offset: 0

Views

Author

Paul D. Hanna, Aug 28 2013

Keywords

Comments

A001609 forms the logarithmic derivative of Narayana's cows sequence A000930.

Examples

			G.f.: A(x) = 1 + x + 3*x^2 + 13*x^3 + 128*x^4 + 2974*x^5 + 161048*x^6 +...
where
log(A(x)) = x + 5*x^2/2 + 31*x^3/3 + 453*x^4/4 + 14131*x^5/5 + 946781*x^6/6 + 136250983*x^7/7 +...+ A001609(n^2)*x^n/n +...

Crossrefs

Cf. A228647, A001609, A000930.

Programs

  • PARI
    {A001609(n)=n*polcoeff(-log(1-x-x^3 +x*O(x^n)), n)}
{a(n)=polcoeff(exp(sum(m=1,n+1,A001609(m^2)*x^m/m)+x*O(x^n)),n)}
for(n=0,20,print1(a(n),", "))

Formula

Logarithmic derivative yields A228647.

A000204 Lucas numbers (beginning with 1): L(n) = L(n-1) + L(n-2) with L(1) = 1, L(2) = 3.

Original entry on oeis.org

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

See A000032 for the version beginning 2, 1, 3, 4, 7, ...
Also called Schoute's accessory series (see Jean, 1984). - N. J. A. Sloane, Jun 08 2011
L(n) is the number of matchings in a cycle on n vertices: L(4)=7 because the matchings in a square with edges a, b, c, d (labeled consecutively) are the empty set, a, b, c, d, ac and bd. - Emeric Deutsch, Jun 18 2001
This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1..m - 1, a(m) = m + 1. The generating function is (x + m*x^m)/(1 - x - x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n - 1 - (m - 1)*i, i - 1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m = 2: A000204, m = 3: A001609, m = 4: A014097, m = 5: A058368, m = 6: A058367, m = 7: A058366, m = 8: A058365, m = 9: A058364.
L(n) is the number of points of period n in the golden mean shift. The number of orbits of length n in the golden mean shift is given by the n-th term of the sequence A006206. - Thomas Ward, Mar 13 2001
Row sums of A029635 are 1, 1, 3, 4, 7, ... - Paul Barry, Jan 30 2005
a(n) counts circular n-bit strings with no repeated 1's. E.g., for a(5): 00000 00001 00010 00100 00101 01000 01001 01010 10000 10010 10100. Note #{0...} = fib(n+1), #{1...} = fib(n-1), #{000..., 001..., 100...} = a(n-1), #{010..., 101...} = a(n-2). - Len Smiley, Oct 14 2001
Row sums of the triangle in A182579. - Reinhard Zumkeller, May 07 2012
If p is prime then L(p) == 1 (mod p). L(2^k) == -1 (mod 2^(k+1)) for k = 0,1,2,... - Thomas Ordowski, Sep 25 2013
Satisfies Benford's law [Brown-Duncan, 1970; Berger-Hill, 2017]. - N. J. A. Sloane, Feb 08 2017

Examples

			G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 11*x^5 + 18*x^6 + 29*x^7 + 47*x^8 + ...

References

  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 69.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 46.
  • Leonhard Euler, Introductio in analysin infinitorum (1748), sections 216 and 229.
  • G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 148.
  • Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
  • V. E. Hoggatt, Jr., Fibonacci and Lucas Numbers. Houghton, Boston, MA, 1969.
  • R. V. Jean, Mathematical Approach to Pattern and Form in Plant Growth, Wiley, 1984. See p. 5. - N. J. A. Sloane, Jun 08 2011
  • Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001.
  • 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).
  • S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

Links

Crossrefs

Cf. A000032, A000045, A061084, A027960, A001609, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A006206, A101033, A101032, A100492, A099731, A094216, A094638, A000108, A090946 (complement).

Programs

  • Haskell
    a000204 n = a000204_list !! n
a000204_list = 1 : 3 : zipWith (+) a000204_list (tail a000204_list)
-- Reinhard Zumkeller, Dec 18 2011
  • Magma
    [Lucas(n): n in [1..30]]; // G. C. Greubel, Dec 17 2017
  • Maple
    A000204 := proc(n) option remember; if n <=2 then 2*n-1; else procname(n-1)+procname(n-2); fi; end;
with(combinat): A000204 := n->fibonacci(n+1)+fibonacci(n-1);
# alternative Maple program:
L:= n-> (<<1|1>, <1|0>>^n. <<2, -1>>)[1, 1]:
seq(L(n), n=1..50);  # Alois P. Heinz, Jul 25 2008
# Alternative:
a := n -> `if`(n=1, 1, `if`(n=2, 3, hypergeom([(1-n)/2, -n/2], [1-n], -4))):
seq(simplify(a(n)), n=1..39); # Peter Luschny, Sep 03 2019
  • Mathematica
    c = (1 + Sqrt[5])/2; Table[Expand[c^n + (1 - c)^n], {n, 30}] (* Artur Jasinski, Oct 05 2008 *)
Table[LucasL[n, 1], {n, 36}] (* Zerinvary Lajos, Jul 09 2009 *)
LinearRecurrence[{1, 1},{1, 3}, 50] (* Sture Sjöstedt, Nov 28 2011 *)
lukeNum[n_] := If[n < 1, 0, LucasL[n]]; (* Michael Somos, May 18 2015 *)
lukeNum[n_] := SeriesCoefficient[x D[Log[1 / (1 - x - x^2)], x], {x, 0, n}]; (* Michael Somos, May 18 2015 *)
  • PARI
    A000204(n)=fibonacci(n+1)+fibonacci(n-1) \\ Michael B. Porter, Nov 05 2009
  • Python
    from functools import cache
@cache
def a(n): return [1, 3][n-1] if n < 3 else a(n-1) + a(n-2)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Nov 13 2022
  • Python
    [(i:=-1)+(j:=2)] + [(j:=i+j)+(i:=j-i) for  in range(100)] # _Jwalin Bhatt, Apr 02 2025
  • Sage
    def A000204():
    x, y = 1, 2
    while true:
       yield x
       x, y = x + y, x
a = A000204(); print([next(a) for i in range(39)])  # Peter Luschny, Dec 17 2015
  • Scala
    def lucas(n: BigInt): BigInt = {
  val zero = BigInt(0)
  def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {
    case `zero` => a
    case _ => fibTail(n - 1, b, a + b)
  }
  fibTail(n, 2, 1)
}
(1 to 50).map(lucas()) // _Alonso del Arte, Oct 20 2019

Formula

Expansion of x(1 + 2x)/(1 - x - x^2). - Simon Plouffe, dissertation 1992; multiplied by x. - R. J. Mathar, Nov 14 2007
a(n) = A000045(2n)/A000045(n). - Benoit Cloitre, Jan 05 2003
For n > 1, L(n) = F(n + 2) - F(n - 2), where F(n) is the n-th Fibonacci number (A000045). - Gerald McGarvey, Jul 10 2004
a(n+1) = 4*A054886(n+3) - A022388(n) - 2*A022120(n+1) (a conjecture; note that the above sequences have different offsets). - Creighton Dement, Nov 27 2004
a(n) = Sum_{k=0..floor((n+1)/2)} (n+1)*binomial(n - k + 1, k)/(n - k + 1). - Paul Barry, Jan 30 2005
L(n) = A000045(n+3) - 2*A000045(n). - Creighton Dement, Oct 07 2005
L(n) = A000045(n+1) + A000045(n-1). - John Blythe Dobson, Sep 29 2007
a(n) = 2*Fibonacci(n-1) + Fibonacci(n), n >= 1. - Zerinvary Lajos, Oct 05 2007
L(n) is the term (1, 1) in the 1 X 2 matrix [2, -1].[1, 1; 1, 0]^n. - Alois P. Heinz, Jul 25 2008
a(n) = phi^n + (1 - phi)^n = phi^n + (-phi)^(-n) = ((1 + sqrt(5))^n + (1 - sqrt(5))^n)/(2^n) where phi is the golden ratio (A001622). - Artur Jasinski, Oct 05 2008
a(n) = A014217(n+1) - A014217(n-1). See A153263. - Paul Curtz, Dec 22 2008
a(n) = ((1 + sqrt(5))^n - (1 - sqrt(5))^n)/(2^n*sqrt(5)) + ((1 + sqrt(5))^(n - 1) - (1 - sqrt(5))^(n - 1))/(2^(n - 2)*sqrt(5)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009, Jan 14 2009
From Hieronymus Fischer, Oct 20 2010 (Start)
Continued fraction for n odd: [L(n); L(n), L(n), ...] = L(n) + fract(Fib(n) * phi).
Continued fraction for n even: [L(n); -L(n), L(n), -L(n), L(n), ...] = L(n) - 1 + fract(Fib(n)*phi). Also: [L(n) - 2; 1, L(n) - 2, 1, L(n) - 2, ...] = L(n) - 2 + fract(Fib(n)*phi). (End)
INVERT transform of (1, 2, -1, -2, 1, 2, ...). - Gary W. Adamson, Mar 07 2012
L(2n - 1) = floor(phi^(2n - 1)); L(2n) = ceiling(phi^(2n)). - Thomas Ordowski, Jun 15 2012
a(n) = hypergeom([(1 - n)/2, -n/2], [1 - n], -4) for n >= 3. - Peter Luschny, Sep 03 2019
E.g.f.: 2*(exp(x/2)*cosh(sqrt(5)*x/2) - 1). - Stefano Spezia, Jul 26 2022

Extensions

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
Plouffe Maple line edited by N. J. A. Sloane, May 13 2008

A000930 Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Named after a 14th-century Indian mathematician. [The sequence first appeared in the book "Ganita Kaumudi" (1356) by the Indian mathematician Narayana Pandita (c. 1340 - c. 1400). - Amiram Eldar, Apr 15 2021]
Number of compositions of n into parts 1 and 3. - Joerg Arndt, Jun 25 2011
A Lamé sequence of higher order.
Could have begun 1,0,0,1,1,1,2,3,4,6,9,... (A078012) but that would spoil many nice properties.
Number of tilings of a 3 X n rectangle with straight trominoes.
Number of ways to arrange n-1 tatami mats in a 2 X (n-1) room such that no 4 meet at a point. For example, there are 6 ways to cover a 2 X 5 room, described by 11111, 2111, 1211, 1121, 1112, 212.
Equivalently, number of compositions (ordered partitions) of n-1 into parts 1 and 2 with no two 2's adjacent. E.g., there are 6 such ways to partition 5, namely 11111, 2111, 1211, 1121, 1112, 212, so a(6) = 6. [Minor edit by Keyang Li, Oct 10 2020]
This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..floor(n/m)} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
a(n+2) is the number of n-bit 0-1 sequences that avoid both 00 and 010. - David Callan, Mar 25 2004 [This can easily be proved by the Cluster Method - see for example the Noonan-Zeilberger article. - N. J. A. Sloane, Aug 29 2013]
a(n-4) is the number of n-bit sequences that start and end with 0 but avoid both 00 and 010. For n >= 6, such a sequence necessarily starts 011 and ends 110; deleting these 6 bits is a bijection to the preceding item. - David Callan, Mar 25 2004
Also number of compositions of n+1 into parts congruent to 1 mod m. Here m=3, A003269 for m=4, etc. - Vladeta Jovovic, Feb 09 2005
Row sums of Riordan array (1/(1-x^3), x/(1-x^3)). - Paul Barry, Feb 25 2005
Row sums of Riordan array (1,x(1+x^2)). - Paul Barry, Jan 12 2006
Starting with offset 1 = row sums of triangle A145580. - Gary W. Adamson, Oct 13 2008
Number of digits in A061582. - Dmitry Kamenetsky, Jan 17 2009
From Jon Perry, Nov 15 2010: (Start)
The family a(n) = a(n-1) + a(n-m) with a(n)=1 for n=0..m-1 can be generated by considering the sums (A102547):
1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10
1 3 6 10 15 21 28
1 4 10 20
1
------------------------------
1 1 1 2 3 4 6 9 13 19 28 41 60
with (in this case 3) leading zeros added to each row.
(End)
Number of pairs of rabbits existing at period n generated by 1 pair. All pairs become fertile after 3 periods and generate thereafter a new pair at all following periods. - Carmine Suriano, Mar 20 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=3, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >= 3, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
For n>=2, row sums of Pascal's triangle (A007318) with triplicated diagonals. - Vladimir Shevelev, Apr 12 2012
Pisano period lengths of the sequence read mod m, m >= 1: 1, 7, 8, 14, 31, 56, 57, 28, 24, 217, 60, 56, 168, ... (A271953) If m=3, for example, the remainder sequence becomes 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, ... with a period of length 8. - R. J. Mathar, Oct 18 2012
Diagonal sums of triangle A011973. - John Molokach, Jul 06 2013
"In how many ways can a kangaroo jump through all points of the integer interval [1,n+1] starting at 1 and ending at n+1, while making hops that are restricted to {-1,1,2}? (The OGF is the rational function 1/(1 - z - z^3) corresponding to A000930.)" [Flajolet and Sedgewick, p. 373] - N. J. A. Sloane, Aug 29 2013
a(n) is the number of length n binary words in which the length of every maximal run of consecutive 0's is a multiple of 3. a(5) = 4 because we have: 00011, 10001, 11000, 11111. - Geoffrey Critzer, Jan 07 2014
a(n) is the top left entry of the n-th power of the 3X3 matrix [1, 0, 1; 1, 0, 0; 0, 1, 0] or of the 3 X 3 matrix [1, 1, 0; 0, 0, 1; 1, 0, 0]. - R. J. Mathar, Feb 03 2014
a(n-3) is the top left entry of the n-th power of any of the 3 X 3 matrices [0, 1, 0; 0, 1, 1; 1, 0, 0], [0, 0, 1; 1, 1, 0; 0, 1, 0], [0, 1, 0; 0, 0, 1; 1, 0, 1] or [0, 0, 1; 1, 0, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014
Counts closed walks of length (n+3) on a unidirectional triangle, containing a loop at one of remaining vertices. - David Neil McGrath, Sep 15 2014
a(n+2) equals the number of binary words of length n, having at least two zeros between every two successive ones. - Milan Janjic, Feb 07 2015
a(n+1)/a(n) tends to x = 1.465571... (decimal expansion given in A092526) in the limit n -> infinity. This is the real solution of x^3 - x^2 -1 = 0. See also the formula by Benoit Cloitre, Nov 30 2002. - Wolfdieter Lang, Apr 24 2015
a(n+2) equals the number of subsets of {1,2,..,n} in which any two elements differ by at least 3. - Robert FERREOL, Feb 17 2016
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*. Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2,x}, g(3) = {3,2x,x+1,x^2}, etc. Let T(r) be the tree obtained by substituting r for x. If a positive integer N such that r = N^(1/3) is not an integer, then the number of (not necessarily distinct) integers in g(n) is A000930(n), for n >= 1. (See A274142.) - Clark Kimberling, Jun 13 2016
a(n-3) is the number of compositions of n excluding 1 and 2, n >= 3. - Gregory L. Simay, Jul 12 2016
Antidiagonal sums of array A277627. - Paul Curtz, May 16 2019
a(n+1) is the number of multus bitstrings of length n with no runs of 3 ones. - Steven Finch, Mar 25 2020
Suppose we have a(n) samples, exactly one of which is positive. Assume the cost for testing a mix of k samples is 3 if one of the samples is positive (but you will not know which sample was positive if you test more than 1) and 1 if none of the samples is positive. Then the cheapest strategy for finding the positive sample is to have a(n-3) undergo the first test and then continue with testing either a(n-4) if none were positive or with a(n-6) otherwise. The total cost of the tests will be n. - Ruediger Jehn, Dec 24 2020

Examples

			The number of compositions of 11 without any 1's and 2's is a(11-3) = a(8) = 13. The compositions are (11), (8,3), (3,8), (7,4), (4,7), (6,5), (5,6), (5,3,3), (3,5,3), (3,3,5), (4,4,3), (4,3,4), (3,4,4). - _Gregory L. Simay_, Jul 12 2016
The compositions from the above example may be mapped to the a(8) compositions of 8 into 1's and 3's using this (more generally applicable) method: replace all numbers greater than 3 with a 3 followed by 1's to make the same total, then remove the initial 3 from the composition. Maintaining the example's order, they become (1,1,1,1,1,1,1,1), (1,1,1,1,1,3), (3,1,1,1,1,1), (1,1,1,1,3,1), (1,3,1,1,1,1), (1,1,1,3,1,1), (1,1,3,1,1,1), (1,1,3,3), (3,1,1,3), (3,3,1,1), (1,3,1,3), (1,3,3,1), (3,1,3,1). - _Peter Munn_, May 31 2017

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, id. 8,80.
  • R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [See p. 12, line 3]
  • H. Langman, Play Mathematics. Hafner, NY, 1962, p. 13.
  • David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag. - N. J. A. Sloane, Jul 09 2009
  • 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

Crossrefs

For Lamé sequences of orders 1 through 9 see A000045, this sequence, and A017898 - A017904.
Cf. A000073, A000213, A048715, A069241, A092526, A170954.
See also A000079, A003269, A003520, A005708, A005709, A005710.
Essentially the same as A068921 and A078012.
See also A001609, A145580, A179070, A214551 (same rule except divide by GCD).
A271901 and A271953 give the period of this sequence mod n.
Cf. A007318, A060576, A102547, A277627, A289207.
A120562 has the same recurrence for odd n.

Programs

  • GAP
    a:=[1,1,1];; for n in [4..50] do a[n]:=a[n-1]+a[n-3]; od; a; # Muniru A Asiru, Aug 13 2018
  • Haskell
    a000930 n = a000930_list !! n
a000930_list = 1 : 1 : 1 : zipWith (+) a000930_list (drop 2 a000930_list)
-- Reinhard Zumkeller, Sep 25 2011
  • Magma
    [1,1] cat [ n le 3 select n else Self(n-1)+Self(n-3): n in [1..50] ]; // Vincenzo Librandi, Apr 25 2015
  • Maple
    f := proc(r) local t1,i; t1 := []; for i from 1 to r do t1 := [op(t1),0]; od: for i from 1 to r+1 do t1 := [op(t1),1]; od: for i from 2*r+2 to 50 do t1 := [op(t1),t1[i-1]+t1[i-1-r]]; od: t1; end; # set r = order
with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 2)}, unlabeled]: seq(count(SeqSetU, size=j), j=3..40); # Zerinvary Lajos, Oct 10 2006
A000930 := proc(n)
    add(binomial(n-2*k,k),k=0..floor(n/3)) ;
end proc: # Zerinvary Lajos, Apr 03 2007
a:= n-> (<<1|1|0>, <0|0|1>, <1|0|0>>^n)[1,1]:
seq(a(n), n=0..50); # Alois P. Heinz, Jun 20 2008
  • Mathematica
    a[0] = 1; a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 3]; Table[ a[n], {n, 0, 40} ]
CoefficientList[Series[1/(1 - x - x^3), {x, 0, 45}], x] (* Zerinvary Lajos, Mar 22 2007 *)
LinearRecurrence[{1, 0, 1}, {1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
a[n_] := HypergeometricPFQ[{(1 - n)/3, (2 - n)/3, -n/3}, {(1 - n)/ 2, -n/2}, -27/4]; Table[a[n], {n, 0, 43}] (* Jean-François Alcover, Feb 26 2013 *)
Table[-RootSum[1 + #^2 - #^3 &, 3 #^(n + 2) - 11 #^(n + 3) + 2 #^(n + 4) &]/31, {n, 20}] (* Eric W. Weisstein, Feb 14 2025 *)
  • Maxima
    makelist(sum(binomial(n-2*k,k),k,0,n/3),n,0,18); /* Emanuele Munarini, May 24 2011 */
  • PARI
    a(n)=polcoeff(exp(sum(m=1,n,((1+sqrt(1+4*x))^m + (1-sqrt(1+4*x))^m)*(x/2)^m/m)+x*O(x^n)),n) \\ Paul D. Hanna, Oct 08 2009
  • PARI
    x='x+O('x^66); Vec(1/(1-(x+x^3))) \\ Joerg Arndt, May 24 2011
  • PARI
    a(n)=([0,1,0;0,0,1;1,0,1]^n*[1;1;1])[1,1] \\ Charles R Greathouse IV, Feb 26 2017
  • Python
    from itertools import islice
def A000930_gen(): # generator of terms
    blist = [1]*3
    while True:
        yield blist[0]
        blist = blist[1:]+[blist[0]+blist[2]]
A000930_list = list(islice(A000930_gen(),30)) # Chai Wah Wu, Feb 04 2022
  • SageMath
    @CachedFunction
def a(n): # A000930
    if (n<3): return 1
    else: return a(n-1) + a(n-3)
[a(n) for n in (0..80)] # G. C. Greubel, Jul 29 2022

Formula

G.f.: 1/(1-x-x^3). - Simon Plouffe in his 1992 dissertation
a(n) = Sum_{i=0..floor(n/3)} binomial(n-2*i, i).
a(n) = a(n-2) + a(n-3) + a(n-4) for n>3.
a(n) = floor(d*c^n + 1/2) where c is the real root of x^3-x^2-1 and d is the real root of 31*x^3-31*x^2+9*x-1 (c = 1.465571... = A092526 and d = 0.611491991950812...). - Benoit Cloitre, Nov 30 2002
a(n) = Sum_{k=0..n} binomial(floor((n+2k-2)/3), k). - Paul Barry, Jul 06 2004
a(n) = Sum_{k=0..n} binomial(k, floor((n-k)/2))(1+(-1)^(n-k))/2. - Paul Barry, Jan 12 2006
a(n) = Sum_{k=0..n} binomial((n+2k)/3,(n-k)/3)*(2*cos(2*Pi*(n-k)/3)+1)/3. - Paul Barry, Dec 15 2006
a(n) = term (1,1) in matrix [1,1,0; 0,0,1; 1,0,0]^n. - Alois P. Heinz, Jun 20 2008
G.f.: exp( Sum_{n>=1} ((1+sqrt(1+4*x))^n + (1-sqrt(1+4*x))^n)*(x/2)^n/n ).
Logarithmic derivative equals A001609. - Paul D. Hanna, Oct 08 2009
a(n) = a(n-1) + a(n-2) - a(n-5) for n>4. - Paul Weisenhorn, Oct 28 2011
For n >= 2, a(2*n-1) = a(2*n-2)+a(2*n-4); a(2*n) = a(2*n-1)+a(2*n-3). - Vladimir Shevelev, Apr 12 2012
INVERT transform of (1,0,0,1,0,0,1,0,0,1,...) = (1, 1, 1, 2, 3, 4, 6, ...); but INVERT transform of (1,0,1,0,0,0,...) = (1, 1, 2, 3, 4, 6, ...). - Gary W. Adamson, Jul 05 2012
G.f.: 1/(G(0)-x) where G(k) = 1 - x^2/(1 - x^2/(x^2 - 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 16 2012
G.f.: 1 + x/(G(0)-x) where G(k) = 1 - x^2*(2*k^2 + 3*k +2) + x^2*(k+1)^2*(1 - x^2*(k^2 + 3*k +2))/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 27 2012
a(2*n) = A002478(n), a(2*n+1) = A141015(n+1), a(3*n) = A052544(n), a(3*n+1) = A124820(n), a(3*n+2) = A052529(n+1). - Johannes W. Meijer, Jul 21 2013, corrected by Greg Dresden, Jul 06 2020
G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x^2)/( x*(4*k+3 + x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 08 2013
a(n) = v1*w1^n+v3*w2^n+v2*w3^n, where v1,2,3 are the roots of (-1+9*x-31*x^2+31*x^3): [v1=0.6114919920, v2=0.1942540040 - 0.1225496913*I, v3=conjugate(v2)] and w1,2,3 are the roots of (-1-x^2+x^3): [w1=1.4655712319, w2=-0.2327856159 - 0.7925519925*I, w3=conjugate(w2)]. - Gerry Martens, Jun 27 2015
a(n) = (6*A001609(n+3) + A001609(n-7))/31 for n>=7. - Areebah Mahdia, Jun 07 2020
a(n+6)^2 + a(n+1)^2 + a(n)^2 = a(n+5)^2 + a(n+4)^2 + 3*a(n+3)^2 + a(n+2)^2. - Greg Dresden, Jul 07 2021
a(n) = Sum_{i=(n-7)..(n-1)} a(i) / 2. - Jules Beauchamp, May 10 2025

Extensions

Name expanded by N. J. A. Sloane, Sep 07 2012

A001644 a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3.

Original entry on oeis.org

3, 1, 3, 7, 11, 21, 39, 71, 131, 241, 443, 815, 1499, 2757, 5071, 9327, 17155, 31553, 58035, 106743, 196331, 361109, 664183, 1221623, 2246915, 4132721, 7601259, 13980895, 25714875, 47297029, 86992799, 160004703, 294294531, 541292033, 995591267, 1831177831
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

For n >= 3, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain three consecutive ones provided the positions of the zeros and ones are fixed on a circle. This is proved in Charalambides (1991) and Zhang and Hadjicostas (2015). For example, a(3)=7 because only the sequences 110, 101, 011, 001, 010, 100 and 000 avoid three consecutive ones. (For n=1,2 the statement is still true provided we allow the sequence to wrap around itself on a circle.) - Petros Hadjicostas, Dec 16 2016
For n >= 3, also the number of dominating sets on the n-cycle graph C_n. - Eric W. Weisstein, Mar 30 2017
For n >= 3, also the number of minimal dominating sets and maximal irredundant sets on the n-sun graph. - Eric W. Weisstein, Jul 28 and Aug 17 2017
For n >= 3, also the number of minimal edge covers in the n-web graph. - Eric W. Weisstein, Aug 03 2017
For n >= 1, also the number of ways to tile a bracelet of length n with squares, dominoes, and trominoes. - Ruijia Li and Greg Dresden, Sep 14 2019
If n is prime, then a(n)-1 is a multiple of n ; a counterexample for the converse is given by n = 182. - Robert FERREOL, Apr 03 2024

Examples

			G.f. = 3 + x + 3*x^2 + 7*x^3 + 11*x^4 + 21*x^5 + 39*x^6 + 71*x^7 + 131*x^8 + ...

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.
  • G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • 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

Crossrefs

Cf. A000073, A073145, A106293 (Pisano periods), A073728 (partial sums).
Cf. A058265.
Cf. A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.

Programs

  • GAP
    a:=[3,1,3];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # Muniru A Asiru, Dec 18 2018
  • Haskell
    a001644 n = a001644_list !! n
a001644_list = 3 : 1 : 3 : zipWith3 (((+) .) . (+))
               a001644_list (tail a001644_list) (drop 2 a001644_list)
-- Reinhard Zumkeller, Apr 13 2014
  • Magma
    I:=[3,1,3]; [n le 3 select I[n] else Self(n-1)+Self(n-2)+ Self(n-3): n in [1..40]]; // Vincenzo Librandi, Aug 04 2017
  • Maple
    A001644:=-(1+2*z+3*z**2)/(z**3+z**2+z-1); # Simon Plouffe in his 1992 dissertation; gives sequence except for the initial 3
A001644 :=proc(n)
    option remember;
    if n <= 2 then
        1+2*modp(n+1,2)
    else
        procname(n-1)+procname(n-2)+procname(n-3);
    end if;
end proc:
seq(A001644(n),n=0..80) ;
  • Mathematica
    a[x_]:= a[x] = a[x-1] +a[x-2] +a[x-3]; a[0] = 3; a[1] = 1; a[2] = 3; Array[a, 40, 0]
a[n_]:= n*Sum[Sum[Binomial[j, n-3*k+2*j]*Binomial[k, j], {j,n-3*k,k}]/k, {k, n}]; a[0] = 3; Array[a, 40, 0] (* Robert G. Wilson v, Feb 24 2011 *)
LinearRecurrence[{1, 1, 1}, {3, 1, 3}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)
Table[RootSum[-1 - # - #^2 + #^3 &, #^n &], {n, 0, 40}] (* Eric W. Weisstein, Mar 30 2017 *)
RootSum[-1 - # - #^2 + #^3 &, #^Range[0, 40] &] (* Eric W. Weisstein, Aug 17 2017 *)
  • PARI
    {a(n) = if( n<0, polsym(1 - x - x^2 - x^3, -n)[-n+1], polsym(1 + x + x^2 - x^3, n)[n+1])}; /* Michael Somos, Nov 02 2002 */
  • PARI
    my(x='x+O('x^40)); Vec((3-2*x-x^2)/(1-x-x^2-x^3)) \\ Altug Alkan, Apr 19 2018
  • SageMath
    ((3-2*x-x^2)/(1-x-x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Mar 22 2019

Formula

Binet's formula: a(n) = r1^n + r2^n + r3^n, where r1, r2, r3 are the roots of the characteristic polynomial 1 + x + x^2 - x^3, see A058265.
a(n) = A000073(n) + 2*A000073(n-1) + 3*A000073(n-2).
G.f.: (3-2*x-x^2)/(1-x-x^2-x^3). - Miklos Kristof, Jul 29 2002
a(n) = n*Sum_{k=1..n} Sum_{j=n-3*k..k} binomial(j, n-3*k+2*j)*binomial(k,j)/k, n > 0, a(0)=3. - Vladimir Kruchinin, Feb 24 2011
a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3. - Harvey P. Dale, Feb 01 2015
a(n) = A073145(-n). for all n in Z. - Michael Somos, Dec 17 2016
Sum_{k=0..n} k*a(k) = (n*a(n+3) - a(n+2) - (n+1)*a(n+1) + 4)/2. - Yichen Wang, Aug 30 2020
a(n) = Trace(M^n), where M = [0, 0, 1; 1, 0, 1; 0, 1, 1] is the companion matrix to the monic polynomial x^3 - x^2 - x - 1. It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - Peter Bala, Dec 29 2022

Extensions

Edited by Mario Catalani (mario.catalani(AT)unito.it), Jul 17 2002
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A001638 A Fielder sequence: a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4.

Original entry on oeis.org

4, 1, 1, 4, 9, 11, 16, 29, 49, 76, 121, 199, 324, 521, 841, 1364, 2209, 3571, 5776, 9349, 15129, 24476, 39601, 64079, 103684, 167761, 271441, 439204, 710649, 1149851, 1860496, 3010349, 4870849, 7881196, 12752041, 20633239, 33385284, 54018521, 87403801
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

For n > 1, a(n) is the number of ways of choosing a subset of vertices of an n-cycle so that every vertex of the n-cycle is adjacent to one of the chosen vertices. (Note that this is not the same as the number of dominating sets of the n-cycle, which is given by A001644.) - Joel B. Lewis, Sep 12 2010
For n >= 3, a(n) is also the number of total dominating sets in the n-cycle graph. - Eric W. Weisstein, Apr 10 2018
For n > 0, a(n) is the number of ways to tile a strip of length n with squares, trominos, and quadrominos where the inital tile (of length 1, 3, or 4) can take on 1, 3, or 4 colors respectively. - Greg Dresden and Yuan Shen, Aug 10 2024

References

  • 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

Crossrefs

Cf. A000032, A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.

Programs

  • Magma
    I:=[4,1,1,4]; [n le 4 select I[n] else Self(n-1) + Self(n-3) + Self(n-4): n in [1..30]]; // G. C. Greubel, Jan 09 2018
  • Maple
    A001638:=-(z+1)*(4*z**2-z+1)/(z**2+z-1)/(z**2+1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence except for the initial 4
  • Mathematica
    LinearRecurrence[{1, 0, 1, 1}, {4, 1, 1, 4}, 50] (* T. D. Noe, Aug 09 2012 *)
Table[LucasL[n] + 2 Cos[n Pi/2], {n, 0, 20}] (* Eric W. Weisstein, Apr 10 2018 *)
CoefficientList[Series[(-4 + 3 x + x^3)/(-1 + x + x^3 + x^4), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 10 2018 *)
  • PARI
    a(n)=if(n<0,0,fibonacci(n+1)+fibonacci(n-1)+simplify(I^n+(-I)^n))
  • PARI
    a(n)=if(n<0,0,polsym((1+x-x^2)*(1+x^2),n)[n+1])

Formula

G.f.: (1-x)*(4+x+x^2)/((1+x^2)*(1-x-x^2)).
a(n) = L(n) + i^n + (-i)^n, a(2n) = L(n)^2, a(2n+1) = L(2n+1) where L() is Lucas sequence A000032.
a(n) = a(n-1) + a(n-3) + a(n-4). - Eric W. Weisstein, Apr 10 2018
a(n) = Trace(M^n), where M = [0, 0, 0, 1; 1, 0, 0, 1; 0, 1, 0, 0; 0, 0, 1, 1] is the companion matrix to the monic polynomial x^4 - x^3 - x - 1. . It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - Peter Bala, Jan 08 2023

Extensions

Edited by Michael Somos, Feb 17 2002 and Nov 02 2002

A014097 a(n) = a(n-1)+a(n-4).

Original entry on oeis.org

1, 1, 1, 5, 6, 7, 8, 13, 19, 26, 34, 47, 66, 92, 126, 173, 239, 331, 457, 630, 869, 1200, 1657, 2287, 3156, 4356, 6013, 8300, 11456, 15812, 21825, 30125, 41581, 57393, 79218, 109343, 150924, 208317, 287535
Offset: 1

Views

Author

David Broadhurst

Keywords

Comments

Number of ways to cover (without overlapping) a ring lattice (necklace) of n sites with molecules that are 4 sites wide.
This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1...m-1, a(m) = m+1. The generating function is (x+m*x^m)/(1-x-x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n-1-(m-1)*i, i-1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m=2: A000204, m=3: A001609, m=4: A014097, m=5: A058368, m=6: A058367, m=7: A058366, m=8: A058365, m=9: A058364.

Links

Crossrefs

Cf. A020999, A000204, A001609, A000079, A003269, A003520, A005708, A005709, A005710.

Programs

  • Mathematica
    LinearRecurrence[{1,0,0,1},{1,1,1,5},40] (* Harvey P. Dale, Mar 06 2016 *)
  • Maxima
    a(n):=sum(binomial(n-3*j,n-4*j)*n/(n-3*j),j,0,(n-1)/3); /* Vladimir Kruchinin, Mar 25 2016 */
  • PARI
    a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,1]^(n-1)*[1;1;1;5])[1,1] \\ Charles R Greathouse IV, Sep 09 2016

Formula

G.f.: -x*(1+4*x^3)/(-1+x+x^4). a(n)= 4*A003269(n)-3*A003269(n-1). - R. J. Mathar, Nov 16 2007
a(n) = Sum_{j=0..(n-1)/3}(binomial(n-3*j,n-4*j)*n/(n-3*j)). - Vladimir Kruchinin, Mar 25 2016
From Greg Dresden, Aug 23 2019: (Start)
a(n) = r1^n + r2^n + r3^n + r4^n, where {r1,r2,r3,r4} are the four roots of x^4-x^3-1=0, see A086106, A230151.
a(n) = round(r^n) for n>21 and r the positive real root of x^4-x^3-1.
(End)

Extensions

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

A058368 Number of ways to cover (without overlapping) a ring lattice (necklace) of n sites with molecules that are 5 sites wide.

Original entry on oeis.org

1, 1, 1, 1, 6, 7, 8, 9, 10, 16, 23, 31, 40, 50, 66, 89, 120, 160, 210, 276, 365, 485, 645, 855, 1131, 1496, 1981, 2626, 3481, 4612, 6108, 8089, 10715, 14196, 18808, 24916, 33005, 43720, 57916, 76724, 101640, 134645, 178365, 236281, 313005, 414645
Offset: 1

Views

Author

Yong Kong (ykong(AT)curagen.com), Dec 17 2000

Keywords

Comments

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1...m-1, a(m) = m+1. The generating function is (x+m*x^m)/(1-x-x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n-1-(m-1)*i, i-1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m=2: A000204, m=3: A001609, m=4: A014097, m=5: A058368, m=6: A058367, m=7: A058366, m=8: A058365, m=9: A058364.

Examples

			a(5) = 6 because there is one way to put zero molecule to the necklace and 5 ways to put one molecule.

Links

Crossrefs

Cf. A000204, A001609, A014097, A000079, A003269, A003520, A005708, A005709, A005710.

Programs

  • Mathematica
    LinearRecurrence[{1,0,0,0,1},{1,1,1,1,6},50] (* Harvey P. Dale, Aug 14 2020 *)

Formula

a(n) = 1 + n*Sum_{i=1..n/5} binomial(n-4*i-1, i-1)/i.
a(n) = a(n-1) + a(n-5) for n >= 6.
G.f.: (x+5*x^5)/(1-x-x^5).

A058364 Number of ways to cover (without overlapping) a ring lattice (necklace) of n sites with molecules that are 9 sites wide.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 28, 39, 51, 64, 78, 93, 109, 126, 144, 172, 211, 262, 326, 404, 497, 606, 732, 876, 1048, 1259, 1521, 1847, 2251, 2748, 3354, 4086, 4962, 6010, 7269, 8790, 10637, 12888, 15636, 18990, 23076, 28038
Offset: 1

Views

Author

Yong Kong (ykong(AT)curagen.com), Dec 17 2000

Keywords

Comments

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1...m-1, a(m) = m+1. The generating function is (x+m*x^m)/(1-x-x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n-1-(m-1)*i, i-1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m=2: A000204, m=3: A001609, m=4: A014097, m=5: A058368, m=6: A058367, m=7: A058366, m=8: A058365, m=9: A058364.

Examples

			a(9) = 10 because there is one way to put zero molecule to the necklace and 9 ways to put one molecule.

References

  • E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
  • Y. Kong, General recurrence theory of ligand binding on a three-dimensional lattice, J. Chem. Phys. Vol. 111 (1999), pp. 4790-4799.

Crossrefs

Cf. A000079, A003269, A003520, A005708, A005709, A005710.

Formula

a(n) = 1 + n*sum(binomial(n-1-8*i, i-1)/i, i=1..n/9). a(n) = a(n-1) + a(n-9), a(n) = 1 for n = 1..8, a(9) = 10. generating function = (x+9*x^9)/(1-x-x^9).
Showing 1-10 of 23 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.