|
| |
|
|
A000930
|
|
Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).
(Formerly M0571 N0207)
|
|
144
|
|
|
|
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 14-th century Indian mathematician.
Number of compositions of n into parts 1 and 3. [Joerg Arndt, Jun 25 2011]
A Lam{\'e} 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(binomial(n-(m-1)*i, i), i=0..n/m). 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 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
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. [From 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, 399, 248,... 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
|
|
|
REFERENCES
|
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 78,80.
Russell Chamberlain, Sam Ginsburg, Manda Riehl and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, http://www.uwec.edu/surepam/SUREPAM%202011/Manda.pdf
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, http://www.cs.rit.edu/~pga/k-zeck.pdf, 2012. - From N. J. A. Sloane, Jun 10 2012
M. Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.
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).
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - From N. J. A. Sloane, Sep 16 2012
D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.
B. Keszegh, N Lemons and D. Palvolgyi, Online and quasi-online colorings of wedges and intervals, Arxiv preprint arXiv:1207.4415, 2012. - From N. J. A. Sloane, Dec 23 2012
H. Langman, Play Mathematics. Hafner, NY, 1962, p. 13.
Antonio M. Oller-Marc\'en, "The Dying Rabbit Problem Revisited", INTEGERS, 9 (2009), 129-138 [From Parthasarathy Nambi, May 09 2009]
F. Ruskey and J. Woodcock, Counting Fixed-Height Tatami Tilings, Electronic Journal of Combinatorics, Paper R126 (2009) 20 pages. [From Frank Ruskey, Sep 26 2010]
David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag. [Added by N. J. A. Sloane, Jul 09 2009]
Z. Skupien, Sparse Hamiltonian 2-decompositions ..., Discr. Math., 309 (2009), 6382-6390. - from N. J. A. Sloane, Feb 12 2010
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
|
T. D. Noe, Table of n, a(n) for n=0..500
J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms
J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms
M. Randic, D. Morales, O. Araujo, Higher-order Lucas numbers, Divulgaciones Matematicas 6:2 (2008), pp. 275-283.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373
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, 2011
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
T. Sillke, The binary form of Conway's Sequence
E. Wilson, The Scales of Mt. Meru
Index to sequences with linear recurrences with constant coefficients, signature (1,0,1).
|
|
|
FORMULA
|
G.f.: 1/(1-x-x^3).
a(n) = sum(binomial(n-2*i, i), i=0..n/3).
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= 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, C(k, floor((n-k)/2))(1+(-1)^(n-k))/2}; - Paul Barry, Jan 12 2006
a(n) = sum{k=0..n, C((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
|
|
|
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 (zerinvarylajos(AT)yahoo.com), Oct 10 2006
seq(add(binomial(n-2*k, k), k=0..floor(n/3)), n=0..37); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 03 2007
A000930:=-1/(-1+z+z**3); [Simon Plouffe in his 1992 dissertation.]
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 (zerinvarylajos(AT)yahoo.com), 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
|
|
|
CROSSREFS
|
For Lam{\'e} sequences of orders 1 through 9 see A000045, this one, A017898-A017904.
Cf. A000073, A000213, A048715, A069241, A170954.
See also A000079, A003269, A003520, A005708, A005709, A005710.
Essentially the same as A068921 and A078012.
Cf. A145580.
Cf. A001609.
Cf. A179070, A214551.
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. Name expanded by N. J. A. Sloane, Sep 07 2012
|
|
|
STATUS
|
approved
|
| |
|
|
