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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000930 Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).
(Formerly M0571 N0207)
200
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Named after a 14th-century Indian mathematician.

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(9) = 6.

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

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:

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.

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

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]

D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.

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

Harvey P. Dale and T. D. Noe, Table of n, a(n) for n = 0..5000 [The first 500 terms were computed by T. D. Noe]

J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms, 3rd Computer Music Conference, 1996.

J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms

I. Amburg, K. Dasaratha, L. Flapan, T. Garrity, C. Lee, C. Mihailak, N. Neumann-Chun, S. Peluse, M. Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences, arXiv:1509.05239v1 [math.CO] 17 Sep 2015. See Conjecture 5.8.

Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, University of Wisconsin, April 2012.

E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.

Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012. - N. J. A. Sloane, Jun 10 2012

M. Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373

T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., 41 (1968), 13-21.

V. C. Harris, C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,2,1).

W. R. Heinson, Simulation studies on shape and growth kinetics for fractal aggregates in aerosol and colloidal systems, PhD Dissertation, Kansas State Univ., Manhattan, Kansas, 2015; see page 49.

J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 14

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 376

M. Janjic, Recurrence Relations and Determinants, arXiv preprint arXiv:1112.2466 [math.CO], 2011.

M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - N. J. A. Sloane, Sep 16 2012

B. Keszegh, N Lemons and D. Palvolgyi, Online and quasi-online colorings of wedges and intervals, arXiv preprint arXiv:1207.4415 [math.CO], 2012-2015. - N. J. A. Sloane, Dec 23 2012

K. Kirthi, Narayana Sequences for Cryptographic Applications, arXiv preprint arXiv:1509.05745, 2015

Steven Linton, James Propp, Tom Roby, Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.

T. Mansour and M. Shattuck, Polynomials whose coefficients are generalized Tribonacci numbers, Applied Mathematics and Computation, Volume 219, Issue 15, 1 April 2013, Pages 8366-8374.

T. Mansour, M. Shattuck, A monotonicity property for generalized Fibonacci sequences, arXiv preprint arXiv:1410.6943 [math.CO], 2014.

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], 2013, Table 17.

J. Noonan and D. Zeilberger, The Goulden-Jackson Cluster Method: Extensions, Applications and Implementations, arXiv:math/9806036 [math.CO], Jun 8 1998.

Antonio M. Oller-Marcén, The Dying Rabbit Problem Revisited, INTEGERS, 9 (2009), 129-138

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. Randic, D. Morales, O. Araujo, Higher-order Lucas numbers, Divulgaciones Matematicas 6:2 (2008), pp. 275-283.

F. Ruskey and J. Woodcock, Counting Fixed-Height Tatami Tilings, Electronic Journal of Combinatorics, Paper R126 (2009), 20 pages.

T. Sillke, The binary form of Conway's Sequence

Z. Skupien, Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles, Discr. Math., 309 (2009), 6382-6390. - N. J. A. Sloane, Feb 12 2010

E. Wilson, The Scales of Mt. Meru

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

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). - Johannes W. Meijer, Jul 21 2013

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

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-> (Matrix([[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 *)

PROG

(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

(Maxima) makelist(sum(binomial(n-2*k, k), k, 0, n/3), n, 0, 18); \\ Emanuele Munarini, May 24 2011

(PARI) x='x+O('x^66); Vec(1/(1-(x+x^3))) \\ Joerg Arndt, May 24 2011

(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

CROSSREFS

For Lamé sequences of orders 1 through 9 see A000045, this one, and A017898-A017904.

Cf. A000073, A000213, A048715, A069241, A170954, A092526.

See also A000079, A003269, A003520, A005708, A005709, A005710.

Essentially the same as A068921 and A078012.

See also A145580, A001609, A179070, A214551.

Sequence in context: A068921 * A078012 A135851 A199804 A101913 A121653

Adjacent sequences:  A000927 A000928 A000929 * A000931 A000932 A000933

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 30 08:47 EDT 2016. Contains 273513 sequences.