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 11 results. Next

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

A017898 Expansion of (1-x)/(1-x-x^4).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371, 59864, 82629, 114051, 157422, 217286, 299915, 413966, 571388, 788674
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A Lamé sequence of higher order.
Essentially the same as A003269, which has much more information.
Number of compositions of n into parts >= 4. - Joerg Arndt, Aug 13 2012

Links

Crossrefs

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

Programs

  • 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
a:= n-> (Matrix(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$2, 1][i] else 0 fi)^n)[4,4]: seq(a(n), n=0..42); # Alois P. Heinz, Aug 04 2008
  • Mathematica
    LinearRecurrence[{1, 0, 0, 1}, {1, 0, 0, 0}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
CoefficientList[Series[(1-x)/(1-x-x^4),{x,0,50}],x] (* Harvey P. Dale, Sep 12 2019 *)
  • PARI
    a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,1]^n*[1;0;0;0])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

Formula

a(n) = a(n-1) + a(n-4). - R. J. Mathar, Mar 06 2008
G.f.: 1/(1-sum(k>=4, x^k)). - Joerg Arndt, Aug 13 2012
Apparently a(n) = hypergeometric([1-1/4*n, 5/4-1/4*n, 3/2-1/4*n, 7/4-1/4*n],[4/3-1/3*n, 5/3-1/3*n, 2-1/3*n], -4^4/3^3) for n>=13. - Peter Luschny, Sep 18 2014
a(n) = A003269(n+1)-A003269(n). - R. J. Mathar, Jun 10 2018

A017899 Expansion of 1/(1 -x^5 -x^6 -x^7 - ...).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106, 140, 185, 245, 325, 431, 571, 756, 1001, 1326, 1757, 2328, 3084, 4085, 5411, 7168, 9496, 12580, 16665, 22076, 29244, 38740, 51320, 67985, 90061, 119305, 158045, 209365, 277350
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of compositions of n into parts >=5. - Joerg Arndt, Jun 22 2011
a(n+5) equals the number of binary words such that 0 appears only in runs whose lengths are a multiple of 5. - Milan Janjic, Feb 17 2015
a(n-5) equals the number of circular arrangements of the first n positive integers such that adjacent terms have absolute difference 2 or 3. - Ethan Patrick White, Jun 24 2020

Links

Crossrefs

For Lamé sequences of orders 1 through 9 see A000045, A000930, A017898-A017904.
Apart from initial terms, same as A003520.

Programs

  • 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
a:= n-> (Matrix(5, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$3, 1][i] else 0 fi)^n)[5,5]: seq(a(n), n=0..50); # Alois P. Heinz, Aug 04 2008
  • Mathematica
    CoefficientList[ Series[(1 - x)/(1 - x - x^5), {x, 0, 50}], x] (* Adi Dani, Jun 25 2011 *)
LinearRecurrence[{1,0,0,0,1},{1,0,0,0,0},60] (* Harvey P. Dale, Jun 07 2015 *)
  • PARI
    Vec((1-x)/(1-x-x^5)+O(x^99)) \\ Charles R Greathouse IV, Jun 21 2011

Formula

G.f.: (1-x)/(1-x-x^5) = 1/(1-Sum_{k>=5} x^k).
For positive integers n and k such that k <= n <= 5*k, and 4 divides n-k, define c(n,k) = binomial(k,(n-k)/4), and c(n,k) = 0, otherwise. Then, for n>=1, a(n+5) = Sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011

A017903 Expansion of 1/(1 - x^9 - x^10 - ...).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 19, 24, 30, 37, 45, 54, 64, 76, 91, 110, 134, 164, 201, 246, 300, 364, 440, 531, 641, 775, 939, 1140, 1386, 1686, 2050, 2490, 3021, 3662, 4437, 5376, 6516, 7902, 9588
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A Lamé sequence of higher order.
a(n) = number of compositions of n in which each part is >=9. - Milan Janjic, Jun 28 2010
a(n+9) equals the number of n-length binary words such that 0 appears only in a run which length is a multiple of 9. - Milan Janjic, Feb 17 2015

Links

Crossrefs

For Lamé sequences of orders 1 through 9 see A000045, A000930, A017898-A017904.
Cf. A005711.

Programs

  • 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
a:= n-> (Matrix(9, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$7, 1][i] else 0 fi)^n)[9,9]: seq(a(n), n=0..55); # Alois P. Heinz, Aug 04 2008
  • Mathematica
    CoefficientList[(1-x)/(1-x-x^9) + O[x]^70, x] (* Jean-François Alcover, Jun 08 2015 *)
  • PARI
    Vec((x-1)/(x-1+x^9)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

Formula

G.f.: (x-1)/(x-1+x^9). - Alois P. Heinz, Aug 04 2008
For positive integers n and k such that k <= n <= 9*k, and 8 divides n-k, define c(n,k) = binomial(k,(n-k)/8), and c(n,k) = 0, otherwise. Then, for n>= 1, a(n+9) = sum(c(n,k), k=1..n). - Milan Janjic, Dec 09 2011
a(n) = A005711(n-10) for n > 9. - Alois P. Heinz, May 21 2018

A141539 Square array A(n,k) of numbers of length n binary words with at least k "0" between any two "1" digits (n,k >= 0), read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 3, 5, 16, 1, 2, 3, 4, 8, 32, 1, 2, 3, 4, 6, 13, 64, 1, 2, 3, 4, 5, 9, 21, 128, 1, 2, 3, 4, 5, 7, 13, 34, 256, 1, 2, 3, 4, 5, 6, 10, 19, 55, 512, 1, 2, 3, 4, 5, 6, 8, 14, 28, 89, 1024, 1, 2, 3, 4, 5, 6, 7, 11, 19, 41, 144, 2048, 1, 2, 3, 4, 5, 6, 7, 9, 15, 26, 60, 233, 4096
Offset: 0

Views

Author

Alois P. Heinz, Aug 15 2008

Keywords

Comments

A(n,k+1) = A(n,k) - A143291(n,k).
From Gary W. Adamson, Dec 19 2009: (Start)
Alternative method generated from variants of an infinite lower triangle T(n) = A000012 = (1; 1,1; 1,1,1; ...) such that T(n) has the leftmost column shifted up n times. Then take lim_{k->infinity} T(n)^k, obtaining a left-shifted vector considered as rows of an array (deleting the first 1) as follows:
1, 2, 4, 8, 16, 32, 64, 128, 256, ... = powers of 2
1, 1, 2, 3, 5, 8, 13, 21, 34, ... = Fibonacci numbers
1, 1, 1, 2, 3, 4, 6, 9, 13, ... = A000930
1, 1, 1, 1, 2, 3, 4, 5, 7, ... = A003269
... with the next rows A003520, A005708, A005709, ... such that beginning with the Fibonacci row, the succession of rows are recursive sequences generated from a(n) = a(n-1) + a(n-2); a(n) = a(n-1) + a(n-3), ... a(n) = a(n-1) + a(n-k); k = 2,3,4,... Last, columns going up from the topmost 1 become rows of triangle A141539. (End)

Examples

			A(4,2) = 6, because 6 binary words of length 4 have at least 2 "0" between any two "1" digits: 0000, 0001, 0010, 0100, 1000, 1001.
Square array A(n,k) begins:
    1,  1,  1,  1,  1,  1,  1,  1, ...
    2,  2,  2,  2,  2,  2,  2,  2, ...
    4,  3,  3,  3,  3,  3,  3,  3, ...
    8,  5,  4,  4,  4,  4,  4,  4, ...
   16,  8,  6,  5,  5,  5,  5,  5, ...
   32, 13,  9,  7,  6,  6,  6,  6, ...
   64, 21, 13, 10,  8,  7,  7,  7, ...
  128, 34, 19, 14, 11,  9,  8,  8, ...

Links

Crossrefs

Cf. column k=0: A000079, k=1: A000045(n+2), k=2: A000930(n+2), A068921, A078012(n+5), k=3: A003269(n+4), A017898(n+7), k=4: A003520(n+4), A017899(n+9), k=5: A005708(n+5), A017900(n+11), k=6: A005709(n+6), A017901(n+13), k=7: A005710(n+7), A017902(n+15), k=8: A005711(n+7), A017903(n+17), k=9: A017904(n+19), k=10: A017905(n+21), k=11: A017906(n+23), k=12: A017907(n+25), k=13: A017908(n+27), k=14: A017909(n+29).
Main diagonal gives A000027(n+1).
A(2n,n) gives A000217(n+1)
A(3n,n) gives A008778.
A(3n,2n) gives A034856(n+1).
A(2n,3n) gives A005408.
A(2^n-1,n) gives A376697.
See also A143291.

Programs

  • Maple
    A:= proc(n, k) option remember;
      if k=0 then 2^n
    elif n<=k and n>=0 then n+1
    elif n>0 then A(n-1, k) +A(n-k-1, k)
    else          A(n+1+k, k) -A(n+k, k)
      fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);
  • Mathematica
    a[n_, k_] := a[n, k] = Which[k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, a[n-1, k] + a[n-k-1, k], True, a[n+1+k, k] - a[n+k, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Formula

G.f. of column k: x^(-k)/(1-x-x^(k+1)).
A(n,k) = 2^n if k=0, otherwise A(n,k) = n+1 if n<=k, otherwise A(n,k) = A(n-1,k) + A(n-k-1,k).

A017900 Expansion of 1/(1 - x^6 - x^7 - x^8 - ...).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 34, 43, 55, 71, 92, 119, 153, 196, 251, 322, 414, 533, 686, 882, 1133, 1455, 1869, 2402, 3088, 3970, 5103, 6558, 8427, 10829, 13917, 17887, 22990, 29548, 37975, 48804, 62721, 80608
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A Lamé sequence of higher order.
Number of compositions of n into parts >= 6. - Milan Janjic, Jun 28 2010
a(n+6) equals the number of n-length binary words such that 0 appears only in a run which length is a multiple of 6. - Milan Janjic, Feb 17 2015
Same as sequence A005708 with 1, 0, 0, 0, 0, 0 prepended. - Linas Vepstas, Feb 06 2024

Links

Crossrefs

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

Programs

  • 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
a:= n-> (Matrix(6, (i, j)-> `if`(i=j-1, 1, `if`(j=1, [1, 0$4, 1][i], 0)))^n)[6, 6]: seq(a(n), n=0..80); # Alois P. Heinz, Aug 04 2008
  • Mathematica
    f[n_] := If[n < 1, 1, Sum[ Binomial[ n - 5 k - 5, k], {k, 0, (n - 5)/6}]]; Array[f, 49, 0] (* Adi Dani, Robert G. Wilson v, Jul 04 2011 *)
LinearRecurrence[{1, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0}, 60] (* Jean-François Alcover, Feb 13 2016 *)
  • PARI
    Vec((1-x)/(1-x-x^6)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

Formula

G.f.: 1/(1-Sum_{k>=6} x^k).
G.f.: (1-x)/(1-x-x^6). - Alois P. Heinz, Aug 04 2008
For positive integers n and k such that k <= n <= 6*k, and 5 divides n-k, define c(n,k) = binomial(k,(n-k)/5), and c(n,k) = 0 otherwise. Then, for n >= 1, a(n+6) = Sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011

A017902 Expansion of 1/(1 - x^8 - x^9 - ...).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 18, 23, 29, 36, 44, 53, 64, 78, 96, 119, 148, 184, 228, 281, 345, 423, 519, 638, 786, 970, 1198, 1479, 1824, 2247, 2766, 3404, 4190, 5160, 6358, 7837, 9661, 11908, 14674, 18078
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A Lamé sequence of higher order.
a(n) = number of compositions of n in which each part is >=8. - Milan Janjic, Jun 28 2010
a(n+8) equals the number of n-length binary words such that 0 appears only in a run which length is a multiple of 8. - Milan Janjic, Feb 17 2015

Links

Crossrefs

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

Programs

  • 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
a:= n-> (Matrix(8, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$6, 1][i] else 0 fi)^n)[8,8]: seq(a(n), n=0..53); # Alois P. Heinz, Aug 04 2008
  • Mathematica
    LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0}, 60] (* Jean-François Alcover, Feb 13 2016 *)
  • PARI
    a(n)=([0,1,0,0,0,0,0,0; 0,0,1,0,0,0,0,0; 0,0,0,1,0,0,0,0; 0,0,0,0,1,0,0,0; 0,0,0,0,0,1,0,0; 0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,1; 1,0,0,0,0,0,0,1]^n*[1;0;0;0;0;0;0;0])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

Formula

G.f.: (x-1)/(x-1+x^8). - Alois P. Heinz, Aug 04 2008
For positive integers n and k such that k <= n <= 8*k, and 7 divides n-k, define c(n,k) = binomial(k,(n-k)/7), and c(n,k) = 0, otherwise. Then, for n>=1, a(n+8) = sum(c(n,k), k=1..n). - Milan Janjic, Dec 09 2011
a(n) = A005710(n)-A005710(n-1). - R. J. Mathar, Sep 07 2016

A017901 Expansion of 1/(1 - x^7 - x^8 - ...).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 13, 17, 22, 28, 35, 43, 53, 66, 83, 105, 133, 168, 211, 264, 330, 413, 518, 651, 819, 1030, 1294, 1624, 2037, 2555, 3206, 4025, 5055, 6349, 7973, 10010, 12565, 15771, 19796, 24851, 31200, 39173
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A Lamé sequence of higher order.
a(n) = number of compositions of n in which each part is >= 7. - Milan Janjic, Jun 28 2010
a(n+7) equals the number of n-length binary words such that 0 appears only in a run length that is a multiple of 7. - Milan Janjic, Feb 17 2015
A017847(n) = |a(-n)| for n>=0. - Michael Somos, Oct 28 2018

Examples

			G.f. = 1 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + 2*x^14 + ... - _Michael Somos_, Oct 28 2018

Links

Crossrefs

For Lamé sequences of orders 1 through 9 see A000045, A000930, A017898, A017899, A017900, A017901, A017902, A017903, A017904.
Cf. A005709, A017847.

Programs

  • 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
a := n -> (Matrix(7, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$5, 1][i] else 0 fi)^n)[7,7]: seq(a(n), n=0..50); # Alois P. Heinz, Aug 04 2008
  • Mathematica
    LinearRecurrence[{1,0,0,0,0,0,1}, {1,0,0,0,0,0,0}, 60] (* Jean-François Alcover, Mar 28 2017 *)
  • PARI
    Vec((x-1)/(x-1+x^7)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012
  • PARI
    {a(n) = if( n < 0, polcoeff( 1 / (1 + x^6 - x^7) + x * O(x^-n), -n), polcoeff( (1 - x) / (1 - x - x^7) + x * O(x^n), n))}; /* Michael Somos, Oct 28 2018 */

Formula

G.f.: (x-1)/(x-1+x^7). - Alois P. Heinz, Aug 04 2008
For positive integers n and k such that k <= n <= 7*k, and 6 divides n-k, define c(n,k) = binomial(k,(n-k)/6), and c(n,k) = 0, otherwise. Then, for n>=1, a(n+7) = sum(c(n,k), k=1..n). - Milan Janjic, Dec 09 2011
a(n) = A005709(n) - A005709(n-1). - R. J. Mathar, Sep 07 2016
0 == a(n) + a(n+6) - a(n+7) for all n in Z. - Michael Somos, Oct 28 2018

A143288 Number of binary words of length n containing at least one subword 10^{8}1 and no subwords 10^{i}1 with i<8.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 15, 21, 29, 39, 51, 65, 81, 99, 120, 146, 180, 225, 284, 360, 456, 575, 720, 895, 1106, 1362, 1676, 2065, 2550, 3156, 3912, 4851, 6011, 7437, 9184, 11321, 13936, 17141, 21077, 25919, 31881, 39222, 48254
Offset: 0

Views

Author

Alois P. Heinz, Aug 04 2008

Keywords

Examples

			a(11)=2 because 2 binary words of length 11 have at least one subword 10^{8}1 and no subwords 10^{i}1 with i<8: 01000000001, 10000000010.

Links

Crossrefs

Cf. A005711, A017904, 8th column of A143291.

Programs

  • Maple
    a:= n-> coeff(series(x^10/((x^9+x-1)*(x^10+x-1)), x, n+1), x, n):
seq(a(n), n=0..70);
  • Mathematica
    CoefficientList[Series[x^10 / ((x^9 + x - 1) (x^10 + x - 1)), {x, 0, 60}], x] (* Vincenzo Librandi, Jun 04 2013 *)
LinearRecurrence[{2,-1,0,0,0,0,0,0,1,0,-1,0,0,0,0,0,0,0,-1},{0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9},60] (* Harvey P. Dale, Oct 12 2018 *)
  • PARI
    Vec(1/((x^9+x-1)(x^10+x-1))+O(x^99)) \\ Charles R Greathouse IV, Jun 04 2013

Formula

G.f.: x^10/((x^9+x-1)*(x^10+x-1)).
a(n) = A005711(n+7)-A017904(n+19).
a(n) = 2a(n-1) - a(n-2) + a(n-9) - a(n-11) - a(n-19). - Charles R Greathouse IV, Jun 04 2013

A143289 Number of binary words of length n containing at least one subword 10^{9}1 and no subwords 10^{i}1 with i<9.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 22, 30, 40, 52, 66, 82, 100, 120, 143, 171, 207, 254, 315, 393, 491, 612, 759, 935, 1144, 1392, 1688, 2045, 2480, 3014, 3672, 4483, 5480, 6700, 8185, 9984, 12156, 14774, 17930, 21740, 26349, 31936
Offset: 0

Views

Author

Alois P. Heinz, Aug 04 2008

Keywords

Examples

			a(12)=2 because 2 binary words of length 12 have at least one subword 10^{9}1 and no subwords 10^{i}1 with i<9: 010000000001, 100000000010.

Links

Crossrefs

Cf. A017904, A017905, 9th column of A143291.

Programs

  • Magma
    [n le 11 select 0 else n le 21 select n-11 else 2*Self(n-1)-Self(n-2) +Self(n-10)-Self(n-12)-Self(n-21): n in [1..60]]; // Vincenzo Librandi, Jun 05 2013
  • Maple
    a:= n-> coeff(series(x^11/((x^10+x-1)*(x^11+x-1)), x, n+1), x, n):
seq(a(n), n=0..60);
  • Mathematica
    CoefficientList[Series[x^11 / ((x^10 + x - 1) (x^11 + x - 1)), {x, 0, 60}], x] (* Vincenzo Librandi, Jun 05 2013 *)

Formula

G.f.: x^11/((x^10+x-1)*(x^11+x-1)).
a(n) = A017904(n+19)-A017905(n+21).
a(n) = 2*a(n-1) -a(n-2) +a(n-10) -a(n-12) -a(n-21). - Vincenzo Librandi, Jun 05 2013
Showing 1-10 of 11 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.