

A000930


Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n1) + a(n3).
(Formerly M0571 N0207)


210



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 14thcentury 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 n1 tatami mats in a 2 X (n1) 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 n1 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(n1) + a(nm), with a(n) = 1 for n = 0...m1. The generating function is 1/(1xx^m). Also a(n) = Sum_{i=0..floor(n/m)} binomial(n(m1)*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 nbit 01 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 NoonanZeilberger article.  N. J. A. Sloane, Aug 29 2013]
a(n4) = number of nbit 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/(1x^3), x/(1x^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(n1) + a(nm) with a(n)=1 for n=0..m1 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 pcolored compositions of n. For n>=3, 2*a(n3) equals the number of 2colored 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 nth 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(n3) is the top left entry of the nth 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 nth 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(n3) is the number of compositions of n excluding 1 and 2, n >= 3.  Gregory L. Simay, Jul 12 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. 215. [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, SpringerVerlag.  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).
Krzysztof Strasburger, The order of three lowestenergy states of the sixelectron harmonium at small force constan, The Journal of Chemical Physics 144, 234304 (2016); doi: http://dx.doi.org/10.1063/1.4953677


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. NeumannChun, S. Peluse, M. Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIPStern Sequences, arXiv:1509.05239v1 [math.CO] Sep 17 2015. See Conjecture 5.8.
Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilfequivalence on Theta_kembeddings, University of Wisconsin, April 2012.
E. Di Cera and Y. Kong, Theory of multivalent binding in one and twodimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107124.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in kZeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012.  N. J. A. Sloane, Jun 10 2012
M. Feinberg, New slants, Fib. Quart. 2 (1964), 223227.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373
T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., 41 (1968), 1321.
V. C. Harris, C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277289, 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), 371380.
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.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 91.
B. Keszegh, N Lemons and D. Palvolgyi, Online and quasionline colorings of wedges and intervals, arXiv preprint arXiv:1207.4415 [math.CO], 20122015.
K. Kirthi, Narayana Sequences for Cryptographic Applications, arXiv preprint arXiv:1509.05745 [math.NT], 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.
K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.
T. Mansour and M. Shattuck, Polynomials whose coefficients are generalized Tribonacci numbers, Applied Mathematics and Computation, Volume 219, Issue 15, Apr 01 2013, Pages 83668374.
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 GouldenJackson Cluster Method: Extensions, Applications and Implementations, arXiv:math/9806036 [math.CO], Jun 08 1998.
Antonio M. OllerMarcén, The Dying Rabbit Problem Revisited, INTEGERS, 9 (2009), 129138
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, Higherorder Lucas numbers, Divulgaciones Matematicas 6:2 (2008), pp. 275283.
F. Ruskey and J. Woodcock, Counting FixedHeight Tatami Tilings, Electronic Journal of Combinatorics, Paper R126 (2009), 20 pages.
T. Sillke, The binary form of Conway's Sequence
Z. Skupien, Sparse Hamiltonian 2decompositions together with exact count of numerous Hamilton cycles, Discr. Math., 309 (2009), 63826390.  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/(1xx^3).  Simon Plouffe in his 1992 dissertation
a(n) = Sum_{i=0..floor(n/3)} binomial(n2*i, i).
a(n) = a(n2) + a(n3) + a(n4) for n>3.
a(n) = floor(d*c^n + 1/2) where c is the real root of x^3x^21 and d is the real root of 31*x^331*x^2+9*x1 (c = 1.465571... = A092526 and d = 0.611491991950812...).  Benoit Cloitre, Nov 30 2002
a(n) = Sum_{k=0..n} binomial(floor((n+2k2)/3), k).  Paul Barry, Jul 06 2004
a(n) = Sum_{k=0..n} binomial(k, floor((nk)/2))(1+(1)^(nk))/2.  Paul Barry, Jan 12 2006
a(n) = Sum_{k=0..n} binomial((n+2k)/3,(nk)/3)*(2*cos(2*Pi*(nk)/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 + (1sqrt(1+4*x))^n)*(x/2)^n/n ).
Logarithmic derivative equals A001609.  Paul D. Hanna, Oct 08 2009
a(n) = a(n1) + a(n2)  a(n5) for n>4.  Paul Weisenhorn, Oct 28 2011
For n>=2, a(2*n1) = a(2*n2)+a(2*n4); a(2*n) = a(2*n1)+a(2*n3).  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*x31*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 (1x^2+x^3): [w1=1.4655712319, w2=0.2327856159  0.7925519925*I, w3=conjugate(w2)].  Gerry Martens, Jun 27 2015


EXAMPLE

The number of compositions of 11 without any 1's and 2's is a(113) = 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


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[i1]+t1[i1r]]; 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(n2*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/(1xx^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[{(1n)/3, (2n)/3, n/3}, {(1n)/ 2, n/2}, 27/4]; Table[a[n], {n, 0, 43}] (* JeanFrançois Alcover, Feb 26 2013 *)


PROG

(PARI) a(n)=polcoeff(exp(sum(m=1, n, ((1+sqrt(1+4*x))^m + (1sqrt(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
(Maxima) makelist(sum(binomial(n2*k, k), k, 0, n/3), n, 0, 18); \\ Emanuele Munarini, 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(n1)+Self(n3): n in [1..50] ]; // Vincenzo Librandi, Apr 25 2015


CROSSREFS

For Lamé sequences of orders 1 through 9 see A000045, this one, and A017898A017904.
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 (same rule except divide by gcd).
A271901 and A271953 give the period of this sequence mod n.
Sequence in context: A068921 * A078012 A135851 A199804 A101913 A121653
Adjacent sequences: A000927 A000928 A000929 * A000931 A000932 A000933


KEYWORD

nonn,easy,nice,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

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


STATUS

approved



