A000073 -id:A000073 - cp's OEIS frontend

A021913 Period 4: repeat [0, 0, 1, 1].

0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1

Offset: 0

N. J. A. Sloane

Decimal expansion of 1/909.
Lexicographically earliest de Bruijn sequence for n = 2 and k = 2.
Except for first term, binary expansion of the decimal number 1/10 = 0.000110011001100110011... in base 2. - Benoit Cloitre, May 18 2002
Content of #2 binary placeholder when n is converted from decimal to binary. a(n) = n*(n-1)/2 mod 2. Example: a(7) = 1 since 7 in binary is 1 -1- 1 and (7*6/2) mod 2 = 1. - Anne M. Donovan (anned3005(AT)aol.com), Sep 15 2003
Expansion in any base b of 1/((b-1)*(b^2+1)) = 1/(b^3-b^2+b-1). E.g., 1/5 in base 2, 1/20 in base 3, 1/51 in base 4, etc. - Franklin T. Adams-Watters, Nov 07 2006
Except for first term, parity of the triangular numbers A000217. - Omar E. Pol, Jan 17 2012
Except for first term, more generally: 1) Parity of the k-polygonal numbers, if k is odd (Cf. A139600, A139601). 2) Parity of the generalized k-gonal numbers, for even k >= 6. - Omar E. Pol, Feb 05 2012
Except for first term, parity of Recamán's sequence A005132. - Omar E. Pol, Apr 13 2012
Inverse binomial transform of A000749(n+1). - Wesley Ivan Hurt, Dec 30 2015
Least significant bit of tribonacci numbers (A000073). - Andres Cicuttin, Apr 04 2016

			G.f. = x^2 + x^3 + x^6 + x^7 + x^10 + x^11 + x^14 + x^15 + x^18 + x^19 + ...;
1/909 = 0.001100110011001 ...

Guenther Schrack, Table of n, a(n) for n = 0..1000
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (1,-1,1).

Cf. A000073, A000217, A000749, A005132, A007877, A056594, A062158, A133872, A139600, A139601.

&cat [[0, 0, 1, 1]^^30]; // Vincenzo Librandi, Dec 31 2015

A021913:=n->floor((n mod 4)/2); seq(A021913(n), n=0..100); # Wesley Ivan Hurt, Feb 28 2014

Table[Floor[Mod[n,4]/2], {n,0,100}] (* Wesley Ivan Hurt, Feb 28 2014 *)
a[ n_] := Mod[ Quotient[ n, 2], 2]; (* Michael Somos, Feb 28 2014 *)
LinearRecurrence[{1,-1,1},{0,0,1}, 100] (* Ray Chandler, Aug 25 2015 *)
CoefficientList[Series[x^2(1+x)/(1-x^4), {x, 0, 100}], x] (* Vincenzo Librandi, Dec 31 2015 *)
(1-(-1)^Binomial[Range[0, 100], 2])/2 (* G. C. Greubel, Apr 03 2019 *)

{a(n) = n \ 2 % 2}; /* Michael Somos, Feb 28 2014 */

x='x+O('x^99); concat([0, 0], Vec(x^2/(1-x+x^2-x^3))) \\ Altug Alkan, Apr 04 2016

From Paul Barry, Aug 30 2004: (Start)
G.f.: x^2*(1 + x)/(1 - x^4).
a(n) = 1/2 - cos(Pi*n/2)/2 - sin(Pi*n/2)/2.
a(n) = a(n-1) - a(n-2) + a(n-3) for n > 2. (End)
a(n+2) = Sum_{k=0..n} b(k), with b(k) = A056594(k) (partial sums of S(n,x) Chebyshev polynomials at x=0).
a(n) = -a(n-2) + 1, for n >= 2 with a(0) = a(1) = 0.
G.f.: x^2/((1 - x)*(1 + x^2)) = x^2/(1 - x + x^2 - x^3).
From Jaume Oliver Lafont, Dec 05 2008: (Start)
a(n) = 1/2 - sin((2n+1)*Pi/4)/sqrt(2).
a(n) = 1/2 - cos((2n-1)*Pi/4)/sqrt(2). (End)
a(n) = floor((n mod 4)/2). - Reinhard Zumkeller, Apr 15 2011
Euler transform of length 4 sequence [1, -1, 0, 1]. - Michael Somos, Feb 28 2014
a(1-n) = a(n) for all n in Z. - Michael Somos, Feb 28 2014
From Wesley Ivan Hurt, Jul 22 2016: (Start)
a(n) = a(n-4) for n > 3.
a(n) = A133872(n+2).
a(n) + a(n+1) = A007877(n). (End)
E.g.f.: (exp(x) - sin(x) - cos(x))/2. - Ilya Gutkovskiy, Jul 11 2016
a(n) = (1 - (-1)^(n*(n-1)/2))/2. - Guenther Schrack, Feb 28 2019

Chebyshev comment from Wolfdieter Lang, Sep 10 2004

A079262 Octanacci numbers: a(0)=a(1)=...=a(6)=0, a(7)=1; for n >= 8, a(n) = Sum_{i=1..8} a(n-i).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, 32192, 64256, 128257, 256005, 510994, 1019960, 2035872, 4063664, 8111200, 16190208, 32316160, 64504063, 128752121, 256993248, 512966536, 1023897200, 2043730736

Offset: 0

Michael Joseph Halm, Feb 04 2003

a(n+7) is the number of compositions of n into parts <= 8. - Joerg Arndt, Sep 24 2020

			a(16) = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255.

T. D. Noe, Table of n, a(n) for n=0..207
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Taras Goy and Mark Shattuck, Some Toeplitz-Hessenberg Determinant Identities for the Tetranacci Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.6.8.
Tian-Xiao He, Impulse Response Sequences and Construction of Number Sequence Identities, J. Int. Seq. 16 (2013) #13.8.2.
F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quart. 49 (2011), no. 3, 231-243.
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
Fred J. Rispoli, Fibonacci Polytopes and Their Applications, Fib. Q., 43,3 (2005), 227-233.
Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1).

Cf. A066178, A001592, A001591, A001630, A000073, A000045.
Row 8 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
Cf. A253706, A253705. Primes and indices of primes in this sequence.

for j from 0 to 6 do a[j]:=0 od: a[7]:=1: for n from 8 to 45 do a[n]:=sum(a[n-i],i=1..8) od:seq(a[n],n=0..45); # Emeric Deutsch, Apr 16 2005

LinearRecurrence[{1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, 50] (* Vladimir Joseph Stephan Orlovsky, May 25 2011 *)
With[{nn=8},LinearRecurrence[Table[1,{nn}],Join[Table[0,{nn-1}],{1}],50]] (* Harvey P. Dale, Aug 17 2013 *)

G.f.: x^7/(1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7 - x^8). - Emeric Deutsch, Apr 16 2005
a(1)..a(9) = 1, 1, 2, 4, 8, 16, 32, 64, 128. a(10) and following are given by 63*2^(n-8)+(1/2+sqrt(5/4))^(n-6)/sqrt(5)-(1/2-sqrt(5/4))^(n-6)/sqrt(5). Offset 10. a(10)=255. - Al Hakanson (hawkuu(AT)gmail.com), Feb 14 2009
Another form of the g.f.: f(z) = (z^7 - z^8)/(1 - 2*z + z^9), then a(n) = Sum_{i=0..floor((n-7)/9)} (-1)^i*binomial(n-7-8*i,i)*2^(n-7-9*i) - Sum_{i=0..floor((n-8)/9)} (-1)^i*binomial(n-8-8*i,i)*2^(n-8-9*i) with Sum_{i=m..n} alpha(i) = 0 for m>n. - Richard Choulet, Feb 22 2010
Sum_{k=0..7*n} a(k+b)*A171890(n,k) = a(8*n+b), b>=0.
a(n) = 2*a(n-1) - a(n-9). - Vincenzo Librandi, Dec 20 2010

Corrected by Joao B. Oliveira (oliveira(AT)inf.pucrs.br), Nov 25 2004

A003726 Numbers with no 3 adjacent 1's in binary expansion.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 48, 49, 50, 51, 52, 53, 54, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 80, 81, 82

Offset: 1

N. J. A. Sloane

Positions of zeros in A014082. Could be called "tribbinary numbers" by analogy with A003714. - John Keith, Mar 07 2022

The sequence of Tribbinary numbers can be constructed by writing out the Tribonacci representations of nonnegative integers and then evaluating the result in binary. These numbers are similar to Fibbinary numbers A003714, Fibternary numbers A003726, and Tribternary numbers A356823. The number of Tribbinary numbers less than any power of two is a Tribonacci number. We can generate Tribbinary numbers recursively: Start by adding 0 and 1 to the sequence. Then, if x is a number in the sequence add 2x, 4x+1, and 8x+3 to the sequence. The n-th Tribbinary number is even if the n-th term of the Tribonacci word is a. Respectively, the n-th Tribbinary number is of the form 4x+1 if the n-th term of the Tribonacci word is b, and the n-th Tribbinary number is of the form 8x+3 if the n-th term of the Tribonacci word is c. Every nonnegative integer can be written as the sum of two Tribbinary numbers. Every number has a Tribbinary multiple. - Tanya Khovanova and PRIMES STEP Senior, Aug 30 2022

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
Index entries for 2-automatic sequences.

Cf. A278038 (binary), A063037, A000073, A014082 (number of 111).
Cf. A004781 (complement).
Cf. A007088; A003796 (no 000), A004745 (no 001), A004746 (no 010), A004744 (no 011), A003754 (no 100), A004742 (no 101), A004743 (no 110).

a003726 n = a003726_list !! (n - 1)
a003726_list = filter f [0..] where
   f x = x < 7 || (x `mod` 8) < 7 && f (x `div` 2)
-- Reinhard Zumkeller, Jun 03 2012

Select[Range[0, 82], SequenceCount[IntegerDigits[#, 2], {1, 1, 1}] == 0 &] (* Michael De Vlieger, Dec 23 2019 *)

is(n)=!bitand(bitand(n, n<<1), n<<2) \\ Charles R Greathouse IV, Feb 11 2017

There are A000073(n+3) terms of this sequence with at most n bits. In particular, a(A000073(n+3)+1) = 2^n. - Charles R Greathouse IV, Oct 22 2021

Sum_{n>=2} 1/a(n) = 9.516857810319139410424631558212354346868048230248717360943194590798113163384... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 13 2022

A066178 Number of binary bit strings of length n with no block of 8 or more 0's. Nonzero heptanacci numbers, A122189.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, 495776, 987568, 1967200, 3918592, 7805695, 15548665, 30972384, 61695880, 122895984, 244804400, 487641600

Offset: 0

Len Smiley, Dec 14 2001

Analogous bit string description and o.g.f. (1-x)/(1-2x+x^{k+1}) works for nonzero k-nacci numbers.

Compositions of n into parts <= 7. - Joerg Arndt, Aug 06 2012

T. D. Noe, Table of n, a(n) for n = 0..200
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Zhao Hui Du, Link giving derivation and proof of the formula
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Heptanacci Number
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Cf. A000045 (k=2, Fibonacci numbers), A000073 (k=3, tribonacci) A000078 (k=4, tetranacci) A001591 (k=5, pentanacci) A001592 (k=6, hexanacci), A122189 (k=7, heptanacci).

Row 7 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).

a[0] = a[1] = 1; a[2] = 2; a[3] = 4; a[4] = 8; a[5] = 16; a[6] = 32; a[7] = 64; a[n_] := 2*a[n - 1] - a[n - 8]; Array[a, 31, 0]
CoefficientList[ Series[(1 - x)/(1 - 2 x + x^8), {x, 0, 30}], x]
LinearRecurrence[{1,1,1,1,1,1,1},{1,1,2,4,8,16,32},40] (* Harvey P. Dale, Nov 16 2014 *)

O.g.f.: 1/(1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7).
a(n) = Sum_{i=n-7..n-1} a(i).
a(n) = round((r-1)/((t+1)*r - 2*t) * r^(n-1)), where r is the heptanacci constant, the real root of the equation x^(t+1) - 2*x^t + 1 = 0 which is greater than 1. The formula could also be used for a k-step Fibonacci sequence if r is replaced by the k-bonacci constant, as in A000045, A000073, A000078, A001591, A001592. - Zhao Hui Du, Aug 24 2008
a(n) = 2*a(n-1) - a(n-8). - Vincenzo Librandi, Dec 20 2010

Definition corrected by Vincenzo Librandi, Dec 20 2010

A092921 Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...), for column n >= 0.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 3, 2, 1, 1, 0, 1, 5, 4, 2, 1, 1, 0, 1, 8, 7, 4, 2, 1, 1, 0, 1, 13, 13, 8, 4, 2, 1, 1, 0, 1, 21, 24, 15, 8, 4, 2, 1, 1, 0, 1, 34, 44, 29, 16, 8, 4, 2, 1, 1, 0, 1, 55, 81, 56, 31, 16, 8, 4, 2, 1, 1, 0, 1, 89, 149, 108, 61, 32, 16, 8, 4, 2, 1, 1, 0

Offset: 0

Ralf Stephan, Apr 17 2004

For all k >= 1, the k-generalized Fibonacci number F(k,n) satisfies the recurrence obtained by adding more terms to the recurrence of the Fibonacci numbers.
The number of tilings of an 1 X n rectangle with tiles of size 1 X 1, 1 X 2, ..., 1 X k is F(k,n).
T(k,n) is the number of 0-balanced ordered trees with n edges and height k (height is the number of edges from root to a leaf). - Emeric Deutsch, Jan 19 2007
Brlek et al. (2006) call this table "number of psp-polyominoes with flat bottom". - N. J. A. Sloane, Oct 30 2018

			From _Peter Luschny_, Apr 03 2021: (Start)
Array begins:
                n = 0  1  2  3  4  5   6   7   8    9   10
  -------------------------------------------------------------
  [k=1, mononacci ] 0, 1, 1, 1, 1, 1,  1,  1,  1,   1,   1, ...
  [k=2, Fibonacci ] 0, 1, 1, 2, 3, 5,  8, 13, 21,  34,  55, ...
  [k=3, tribonacci] 0, 1, 1, 2, 4, 7, 13, 24, 44,  81, 149, ...
  [k=4, tetranacci] 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...
  [k=5, pentanacci] 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, ...
  [k=6]             0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, ...
  [k=7]             0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, ...
  [k=8]             0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
  [k=9]             0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, ...
Note that the first parameter in F(k, n) refers to rows, and the second parameter refers to columns. This is always the case. Only the usual naming convention for the indices is not adhered to because it is common to call the row sequences k-bonacci numbers. (End)
.
From _Peter Luschny_, Aug 12 2015: (Start)
As a triangle counting compositions of n with largest part k:
  [n\k]| [0][1] [2] [3] [4][5][6][7][8][9]
   [0] | [0]
   [1] | [0, 1]
   [2] | [0, 1,  1]
   [3] | [0, 1,  1,  1]
   [4] | [0, 1,  2,  1,  1]
   [5] | [0, 1,  3,  2,  1, 1]
   [6] | [0, 1,  5,  4,  2, 1, 1]
   [7] | [0, 1,  8,  7,  4, 2, 1, 1]
   [8] | [0, 1, 13, 13,  8, 4, 2, 1, 1]
   [9] | [0, 1, 21, 24, 15, 8, 4, 2, 1, 1]
For example for n=7 and k=3 we have the 7 compositions [3, 3, 1], [3, 2, 2], [3, 2, 1, 1], [3, 1, 3], [3, 1, 2, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1]. (End)

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Srecko Brlek, Andrea Frosini, Simone Rinaldi, and Laurent Vuillon, Tilings by translation: enumeration by a rational language approach, The Electronic Journal of Combinatorics, vol. 13, (2006). Table 1 is essentially this array. - _N. J. A. Sloane_, Jul 20 2014
Eric S. Egge, Restricted permutations related to Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0109219 [math.CO], 2001.
Eric S. Egge, Restricted 3412-Avoiding Involutions, arXiv:math/0307050 [math.CO], 2003.
Eric S. Egge and Toufik Mansour, Restricted permutations, Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0203226 [math.CO], 2002.
Eric S. Egge and Toufik Mansour, 231-avoiding involutions and Fibonacci numbers, arXiv:math/0209255 [math.CO], 2002.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Abraham Flaxman, Aram W. Harrow, and Gregory B. Sorkin, Strings with Maximally Many Distinct Subsequences and Substrings, Electronic J. Combinatorics 11 (1) (2004), Paper R8.
Ivan Flores, k-Generalized Fibonacci numbers, Fib. Quart., 5 (1967), 258-266.
H. Gabai, Generalized Fibonacci k-sequences, Fib. Quart., 8 (1970), 31-38.
R. Kemp, Balanced ordered trees, Random Structures and Alg., 5 (1994), pp. 99-121.
E. P. Miles jr., Generalized Fibonacci numbers and associated matrices, The Amer. Math. Monthly, 67 (1960) 745-752.
M. D. Miller, On generalized Fibonacci numbers, The Amer. Math. Monthly, 78 (1971) 1108-1109.
Michel Mollard, p-th order generalized Fibonacci cubes and maximal cubes in Fibonacci p-cubes, arXiv:2507.16387 [math.CO], 2025. See p. 3.
Harold R. Parks and Dean C. Wills, Sum of k-bonacci Numbers, arXiv:2208.01224 [math.CO], 2022. See p. 5.
Hsin-Po Wang and Chi-Wei Chin, On Counting Subsequences and Higher-Order Fibonacci Numbers, arXiv:2405.17499 [cs.IT], 2024. See p. 2.

Columns converge to A166444: each column n converges to A166444(n) = 2^(n-2).
Rows 1-8 are (shifted) A057427, A000045, A000073, A000078, A001591, A001592, A066178, A079262.
Essentially a reflected version of A048887.
See A048004 and A126198 for closely related arrays.
Cf. A066099.

F:= proc(k, n) option remember; `if`(n<2, n,
      add(F(k, n-j), j=1..min(k,n)))
    end:
seq(seq(F(k, d+1-k), k=1..d+1), d=0..12);  # Alois P. Heinz, Nov 02 2016
# Based on the above function:
Arow := (k, len) -> seq(F(k, j), j = 0..len):
seq(lprint(Arow(k, 14)), k = 1..10); # Peter Luschny, Apr 03 2021

F[k_, n_] := F[k, n] = If[n<2, n, Sum[F[k, n-j], {j, 1, Min[k, n]}]];
Table[F[k, d+1-k], {d, 0, 12}, {k, 1, d+1}] // Flatten (* Jean-François Alcover, Jan 11 2017, translated from Maple *)

F(k,n)=if(n<2,if(n<1,0,1),sum(i=1,k,F(k,n-i)))

T(m,n)=!!n*(matrix(m,m,i,j,j==i+1||i==m)^(n+m-2))[1,m] \\ M. F. Hasler, Apr 20 2018

F(k,n) = if(n==0,0, polcoeff(lift(Mod('x, Pol(vector(k+1,i, if(i==1,1,-1))))^(n+k-2)), k-1)); \\ Kevin Ryde, Jun 05 2020

# As a triangle of compositions of n with largest part k.
C = lambda n,k: Compositions(n, max_part=k, inner=[k]).cardinality()
for n in (0..9): [C(n,k) for k in (0..n)] # Peter Luschny, Aug 12 2015

F(k,n) = F(k,n-1) + F(k,n-2) + ... + F(k,n-k); F(k,1) = 1 and F(k,n) = 0 for n <= 0.
G.f.: x/(1-Sum_{i=1..k} x^i).
F(k,n) = 2^(n-2) for 1 < n <= k+1. - M. F. Hasler, Apr 20 2018
F(k,n) = Sum_{j=0..floor(n/(k+1))} (-1)^j*((n - j*k) + j + delta(n,0))/(2*(n - j*k) + delta(n,0))*binomial(n - j*k, j)*2^(n-j*(k+1)), where delta denotes the Kronecker delta (see Corollary 3.2 in Parks and Wills). - Stefano Spezia, Aug 06 2022

A077947 Expansion of 1/(1 - x - x^2 - 2*x^3).

Original entry on oeis.org

1, 1, 2, 5, 9, 18, 37, 73, 146, 293, 585, 1170, 2341, 4681, 9362, 18725, 37449, 74898, 149797, 299593, 599186, 1198373, 2396745, 4793490, 9586981, 19173961, 38347922, 76695845, 153391689, 306783378, 613566757, 1227133513, 2454267026, 4908534053, 9817068105

Offset: 0

N. J. A. Sloane, Nov 17 2002

Number of sequences of codewords of total length n from the code C={0,10,110,111}. E.g., a(3)=5 corresponds to the sequences 000, 010, 100, 110 and 111. - Paul Barry, Jan 23 2004
In other words: number of compositions of n into 1 kind of 1's and 2's and two kinds of 3's. - Joerg Arndt, Jun 25 2011
Diagonal sums of number Pascal-(1,2,1) triangle A081577. - Paul Barry, Jan 24 2005
For n>0: a(n) = A173593(2*n+1) - A173593(2*n); a(n+1) = A173593(2*n) - A173593(2*n-1). - Reinhard Zumkeller, Feb 22 2010
Sums of 3 successive terms are powers of 2. - Mark Dols, Aug 20 2010
For n > 2, a(n) is the number of quaternary sequences of length n (i) starting with q(0)=0; (ii) ending with q(n-1)=0 or 3 and (iii) in which all triples (q(i), q(i+1), q(i+2)) contain digits 0 and 3; cf. A294627. - Wojciech Florek, Jul 30 2018

			It is shown in A294627 that there are 42 quaternary sequences (i.e. build from four digits 0, 1, 2, 3) and having both 0 and 3 in every (consecutive) triple. Only a(4) = 9 of them start with 0 and end with 0 or 3: 0030, 0033, 0130, 0230, 0300, 0303, 0310, 0320, 0330. - _Wojciech Florek_, Jul 30 2018

S. Roman, Introduction to Coding and Information Theory, Springer-Verlag, 1996, p. 42

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
G. Cerda-Morales, A note on modified third-order Jacobsthal Numbers, arxiv:1905.00725 [math.CO], 2019.
M. H. Cilasun, An Analytical Approach to Exponent-Restricted Multiple Counting Sequences, arXiv preprint arXiv:1412.3265 [math.NT], 2014.
M. H. Cilasun, Generalized Multiple Counting Jacobsthal Sequences of Fermat Pseudoprimes, Journal of Integer Sequences, Vol. 19, 2016, #16.2.3.
Charles K. Cook and Michael R. Bacon, Some identities for Jacobsthal and Jacobsthal-Lucas numbers satisfying higher order recurrence relations, Annales Mathematicae et Informaticae, 41 (2013) pp. 27-39.
W. Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.
S. Kitaev, J. Remmel and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16; see also arXiv preprint, arXiv:1302.2274 [math.CO], 2013.
Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565, arXiv:1009.2565 [math.CO], 2010.
Evren Eyican Polatlı and Yüksel Soykan, On generalized third-order Jacobsthal numbers, Asian Res. J. of Math. (2021) Vol. 17, No. 2, 1-19, Article No. ARJOM.66022.
Yüksel Soykan, Summing Formulas For Generalized Tribonacci Numbers, arXiv:1910.03490 [math.GM], 2019.
Anthony Zaleski and Doron Zeilberger, On the Intriguing Problem of Counting (n+1,n+2)-Core Partitions into Odd Parts, arXiv:1712.10072 [math.CO], 2017.
Index entries for linear recurrences with constant coefficients, signature (1,1,2).

Apart from signs, same as A077972.
Cf. A139217 and A139218.
Cf. A078010.
Cf. A294627.

[Round(2^(n+2)/7): n in [0..40]]; // Vincenzo Librandi, Jun 25 2011

seq(round(2^(n+2)/7),n=0..25); # Mircea Merca, Dec 28 2010

CoefficientList[Series[1/(1 - x - x^2 - 2*x^3), {x, 0, 100}], x] (* or *) LinearRecurrence[{1, 1, 2}, {1, 1, 2}, 70] (* Vladimir Joseph Stephan Orlovsky, Jun 28 2011 *)

a(n):=sum(sum(binomial(k,j)*binomial(j,n-3*k+2*j)*2^(k-j),j,0,k),k,1,n); /* Vladimir Kruchinin, Sep 07 2010 */

Vec(1/(1-x-x^2-2*x^3) + O(x^100)) \\ Altug Alkan, Oct 31 2015

def A077947(n): return (k:=(m:=1<=7) # Chai Wah Wu, Jan 21 2023

G.f.: 1/((1-2*x)*(1+x+x^2)).
a(n) = a(n-1)+a(n-2)+2*a(n-3). - Paul Curtz, May 23 2008
a(n) = round(2^(n+2)/7). - Mircea Merca, Dec 28 2010
a(n) = 4*2^n/7 + 3*cos(2*Pi*n/3)/7 + sqrt(3)*sin(2*Pi*n/3)/21. - Paul Barry, Jan 23 2004
Convolution of A000079 and A049347. a(n) = Sum_{k=0..n} 2^k*2*sqrt(3)*cos(2*Pi(n-k)/3+Pi/6)/3. - Paul Barry, May 19 2004
a(n) = sum(sum(binomial(k,j)*binomial(j,n-3*k+2*j)*2^(k-j),j,0,k),k,1,n), n>0. - Vladimir Kruchinin, Sep 07 2010
Partial sums of A078010 starting (1, 0, 1, 3, 4, 9, ...). - Gary W. Adamson, May 13 2013
a(n) = (1/14)*(2^(n + 3) + (-1)^n*((-1)^floor(n/3) + 4*(-1)^floor((n + 1)/3) + 2*(-1)^floor((n + 2)/3) + (-1)^floor((n + 4)/3))). - John M. Campbell, Dec 23 2016
a(n) = (1/63)*(9*2^(2 + n) + (-1)^n*(2 + 9*floor(n/6) - 32*floor((n + 5)/6) + 24*floor((n + 7)/6) + 20*floor((n + 8)/6) - 10*floor((n + 9)/6) - 27*floor((n + 10)/6) + 14*floor((n + 11)/6) + 3*floor((n + 13)/6) - 2*floor((n + 14)/6) + floor((n + 15)/6))). - John M. Campbell, Dec 23 2016
7*a(n) = 2^(n+2) + A167373(n+1). - R. J. Mathar, Feb 06 2020
a(n) = T(n+1) + 2*(a(1)*T(n-1) + a(2)*T(n-2) + ... + a(n-2)*T(2) + a(n-1)*T(1)) for T(n) = A000073(n), the tribonacci numbers. - Greg Dresden and Bora Bursalı, Sep 14 2023

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A136175 Tribonacci array, T(n,k).

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 11, 9, 8, 13, 20, 17, 15, 10, 24, 37, 31, 28, 19, 12, 44, 68, 57, 51, 35, 22, 14, 81, 125, 105, 94, 64, 41, 26, 16, 149, 230, 193, 173, 118, 75, 48, 30, 18, 274, 423, 355, 318, 217, 138, 88, 55, 33, 21, 504, 778, 653, 585, 399, 254, 162, 101, 61, 39, 23

Offset: 1

Clark Kimberling, Dec 18 2007

As an interspersion (and dispersion), the array is, as a sequence, a permutation of the positive integers. Column k consists of the numbers m such that the least summand in the tribonacci representation of m is T(1,k). For example, column 1 consists of numbers with least summand 1. This array arises from tribonacci representations in much the same way that the Wythoff array, A035513, arises from Fibonacci (or Zeckendorf) representations.
From Abel Amene, Jul 29 2012: (Start)
(Row 1) = A000073 (offset=4) a(0)=0, a(1)=0, a(2)=1
(Row 2) = A001590 (offset=5) a(0)=0, a(1)=1, a(2)=0
(Row 3) = A000213 (offset=4) a(0)=1, a(1)=1, a(2)=1
(Row 4) = A214899 (offset=5) a(0)=2, a(1)=1, a(2)=2
(Row 5) = A020992 (offset=6) a(0)=0, a(1)=2, a(2)=1
(Row 6) = A100683 (offset=6) a(0)=-1,a(1)=2, a(2)=2
(Row 7) = A135491 (offset=4) a(0)=2, a(1)=4, a(2)=8
(Row 8) = A214727 (offset=6) a(0)=1, a(1)=1, a(2)=2
(Row 9) = A081172 (offset=8) a(0)=1, a(1)=1, a(2)=0
(column 1) = A003265
(column 2) = A353083
(End) [Corrected and extended by John Keith, May 09 2022]

			Northwest corner:
1  2   4   7   13  24   44   81  149 274 504
3  6   11  20  37  68   125  230 423 778
5  9   17  31  57  105  193  355 653
8  15  28  51  94  173  318  585
10 19  35  64  118 217  399
12 22  41  75  138 254
14 26  48  88  162
16 30  55 101
18 33  61
21 39
23

Cf. A035513, A353083, A353084.

# maximum index in A73 such that A73 <= n.
A73floorIdx := proc(n)
    local k ;
    for k from 3 do
        if A000073(k) = n then
            return k ;
        elif A000073(k) > n then
            return k -1 ;
        end if ;
    end do:
end proc:
# tribonacci expansion coeffs of n
A278038 := proc(n)
    local k,L,nres ;
    k := A73floorIdx(n) ;
    L := [1] ;
    nres := n-A000073(k) ;
    while k >= 4 do
        k := k-1 ;
        if nres >= A000073(k) then
            L := [1,op(L)] ;
            nres := nres-A000073(k) ;
        else
            L := [0,op(L)] ;
        end if ;
    end do:
    return L ;
end proc:
A278038inv := proc(L)
    add( A000073(i+2)*op(i,L),i=1..nops(L)) ;
end proc:
A135175 := proc(n,k)
    option remember ;
    local a,known,prev,nprev,kprev,freb ;
    if n =1 then
        A000073(k+2) ;
    elif k>3 then
        procname(n,k-1)+procname(n,k-2)+procname(n,k-3) ;
    else
        if k = 1 then
            for a from 1 do
                known := false ;
                for nprev from 1 to n-1 do
                    for kprev from 1 do
                        if procname(nprev,kprev) > a then
                            break ;
                        elif procname(nprev,kprev) = a then
                            known := true ;
                        end if;
                    end do:
                end do:
                if not known then
                    return a ;
                end if;
            end do:
        else
            prev := procname(n,k-1) ;
            freb := A278038(prev) ;
            return A278038inv([0,op(freb)]) ;
        end if;
    end if;
end proc:
seq(seq(A135175(n,d-n),n=1..d-1),d=2..12) ; # R. J. Mathar, Jun 07 2022

T(1,1)=1, T(1,2)=2, T(1,3)=4, T(1,k)=T(1,k-1)+T(1,k-2)+T(1,k-3) for k>3. Row 1 is the tribonacci basis; write B(k)=T(1,k). Each row satisfies the recurrence T(n,k)=T(n,k-1)+T(n,k-2)+T(n,k-3). T(n,1) is least number not in an earlier row. If T(n,1) has tribonacci representation B(k(1))+B(k(2))+...+B(k(m)), then T(n,2) = B(k(2))+B(k(3))+...+B(k(m+1)) and T(n,3) = B(k(3))+B(k(4))+...+B(k(m+2)). (Continued shifting of indices gives the other terms in row n, also.)

T(3, 4) corrected and more terms by John Keith, May 09 2022

A048887 Array T read by antidiagonals, where T(m,n) = number of compositions of n into parts <= m.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 5, 1, 1, 2, 4, 7, 8, 1, 1, 2, 4, 8, 13, 13, 1, 1, 2, 4, 8, 15, 24, 21, 1, 1, 2, 4, 8, 16, 29, 44, 34, 1, 1, 2, 4, 8, 16, 31, 56, 81, 55, 1, 1, 2, 4, 8, 16, 32, 61, 108, 149, 89, 1, 1, 2, 4, 8, 16, 32, 63, 120, 208, 274, 144, 1

Offset: 1

Clark Kimberling

Taking finite differences of array columns from the top down, we obtain (1; 1,1; 1,2,1; 1,4,2,1; ...) = A048004 rows. - Gary W. Adamson, Aug 20 2010

T(m,n) is the number of binary words of length n-1 with < m consecutive 1's. - Geoffrey Critzer, Sep 02 2012

			T(2,5) counts 11111, 1112, 1121, 1211, 2111, 122, 212, 221, where "1211" abbreviates the composition 1+2+1+1.
These eight compositions correspond respectively to: {0,0,0,0}, {0,0,0,1}, {0,0,1,0}, {0,1,0,0}, {1,0,0,0}, {0,1,0,1}, {1,0,0,1}, {1,0,1,0} per the bijection given by _N. J. A. Sloane_ in A048004. - _Geoffrey Critzer_, Sep 02 2012
The array begins:
  1,  1,  1,  1,  1,  1,  1, ...
  1,  2,  3,  5,  8, 13, ...
  1,  2,  4,  7, 13, ...
  1,  2,  4,  8, ...
  1,  2,  4, ...
  1,  2, ...
  1, ...

J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978, p. 154.

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Hsin-Po Wang and Chi-Wei Chin, On Counting Subsequences and Higher-Order Fibonacci Numbers, arXiv:2405.17499 [cs.IT], 2024. See p. 2.

Rows: A000045 (Fibonacci), A000073 (tribonacci), A000078 (tetranacci), etc.

Essentially a reflected version of A092921. See A048004 and A126198 for closely related arrays.

G := t->(1-z)/(1-2*z+z^(t+1)): T := (m,n)->coeff(series(G(m),z=0,30),z^n): matrix(7,12,T);
# second Maple program:
T:= proc(m, n) option remember; `if`(n=0 or m=1, 1,
      add(T(m, n-j), j=1..min(n, m)))
    end:
seq(seq(T(1+d-n, n), n=1..d), d=1..14); # Alois P. Heinz, May 21 2013

Table[nn=10;a=(1-x^k)/(1-x);b=1/(1-x);c=(1-x^(k-1))/(1-x); CoefficientList[ Series[a b/(1-x^2 b c), {x,0,nn}],x],{k,1,nn}]//Grid  (* Geoffrey Critzer, Sep 02 2012 *)
T[m_, n_] := T[m, n] = If[n == 0 || m == 1, 1, Sum[T[m, n-j], {j, 1, Min[n, m]}]]; Table[Table[T[1+d-n, n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Nov 12 2014, after Alois P. Heinz *)

G.f.: (1-z)/[1-2z+z^(t+1)].

A071675 Array read by antidiagonals of trinomial coefficients.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 3, 3, 1, 0, 0, 2, 6, 4, 1, 0, 0, 1, 7, 10, 5, 1, 0, 0, 0, 6, 16, 15, 6, 1, 0, 0, 0, 3, 19, 30, 21, 7, 1, 0, 0, 0, 1, 16, 45, 50, 28, 8, 1, 0, 0, 0, 0, 10, 51, 90, 77, 36, 9, 1, 0, 0, 0, 0, 4, 45, 126, 161, 112, 45, 10, 1, 0, 0, 0, 0, 1, 30, 141, 266, 266

Offset: 0

Henry Bottomley, May 30 2002

Read as a number triangle, this is the Riordan array (1, x(1+x+x^2)) with T(n,k) = Sum_{i=0..floor((n+k)/2)} C(k,2i+2k-n)*C(2i+2k-n,i). Rows start {1}, {0,1}, {0,1,1}, {0,1,2,1}, {0,0,3,3,1},... Row sums are then the trinomial numbers A000073(n+2). Diagonal sums are A013979. - Paul Barry, Feb 15 2005

Let {a_(k,i)}, k>=1, i=0,...,k, be the k-th antidiagonal of the array. Then s_k(n)=sum{i=0,...,k}a_(k,i)* binomial(n,k) is the n-th element of the k-th column of A213742. For example, s_1(n)=binomial(n,1)=n is the first column of A213742 for n>1, s_2(n)=binomial(n,1)+binomial(n,2)is the second column of A213742 for n>1, etc. In particular (see comment in A213742) in cases k=4,5,6,7,8, s_k(n) is A005718(n+2), A005719(n), A005720(n), A001919(n), A064055(n+3), respectively. - Vladimir Shevelev and Peter J. C. Moses, Jun 22 2012

			Rows start
1, 0,  0,  0,  0,  0, ...;
1, 1,  1,  0,  0,  0,  0, ...;
1, 2,  3,  2,  1,  0,  0, ...;
1, 3,  6,  7,  6,  3,  1, 0, ...;
1, 4, 10, 16, 19, 16, 10, 4, 1, ...; etc.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3

Visible version of A027907. Row sums are 3^n, i.e. A000244. Central diagonal is A002426. Cf. A071676 for a slight variation.

T[n_, k_] := Sum[Binomial[n - k - j, j]*Binomial[k, n - k - j], {j, 0,
Floor[(n - k)/2]}]; Table[T[n, k], {n,0,10}, {k,0,n}] // Flatten (* G. C. Greubel, Feb 28 2017 *)

T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-1, k-2) starting with T(0, 0)=1. See A027907 for more.

As a number triangle, T(n, k) = Sum_{i=0..floor((n-k)/2)} C(n-k-i, i) * C(k, n-k-i). - Paul Barry, Apr 26 2005

A102111 Iccanobirt numbers (1 of 15): a(n) = a(n-1) + a(n-2) + R(a(n-3)), where R is the digit reversal function A004086.

Original entry on oeis.org

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 99, 185, 328, 612, 1521, 2956, 4693, 8900, 20185, 33049, 53332, 144483, 291848, 459666, 1135955, 2443813, 4246722, 12285846, 19716010, 34278280, 118852511, 154192582, 281332336, 550783729, 1117407516, 2301424427

Offset: 0

Jonathan Vos Post and Ray Chandler, Dec 30 2004

Digit reversal variation of tribonacci numbers A000073.

Inspired by Iccanobif numbers: A001129, A014258-A014260.

Cf. A102112-A102125, A102131, A102171.

a:=[0,0,1];[n le 3 select a[n] else Self(n-1) + Self(n-2) + Seqint(Reverse(Intseq(Self(n-3)))):n in [1..36]]; // Marius A. Burtea, Oct 23 2019

read("transforms") ;
A102111 := proc(n)
    option remember;
    if n <= 2 then
        return op(n+1,[0,0,1]) ;
    else
        return procname(n-1)+procname(n-2)+digrev(procname(n-3)) ;
    end if;
end proc:
seq(A102111(n),n=0..20) ; # R. J. Mathar, Nov 17 2012

R[n_]:=FromDigits[Reverse[IntegerDigits[n]]];Clear[a];a[0]=0;a[1]=0;a[2]=1;a [n_]:=a[n]=a[n-1]+a[n-2]+R[a[n-3]];Table[a[n], {n, 0, 40}]
nxt[{a_,b_,c_}]:={b,c,IntegerReverse[a]+b+c}; NestList[nxt,{0,0,1},40][[;;,1]] (* Harvey P. Dale, Jul 18 2023 *)

def R(n):
  n_str = str(n)
  reversedn_str = n_str[::-1]
  reversedn = int(reversedn_str)
  return reversedn
def A(n):
  if n == 0:
    return 0
  elif n == 1:
    return 0
  elif n == 2:
    return 1
  elif n >= 3:
    return A(n-1)+A(n-2)+R(A(n-3))
for i in range(0,20):
  print(A(i)) # Dylan Delgado, Oct 23 2019

A004086(a(n)) = A102119(n).

cp's OEIS Frontend

A021913 Period 4: repeat [0, 0, 1, 1].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A079262 Octanacci numbers: a(0)=a(1)=...=a(6)=0, a(7)=1; for n >= 8, a(n) = Sum_{i=1..8} a(n-i).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A003726 Numbers with no 3 adjacent 1's in binary expansion.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A066178 Number of binary bit strings of length n with no block of 8 or more 0's. Nonzero heptanacci numbers, A122189.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A092921 Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...), for column n >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A077947 Expansion of 1/(1 - x - x^2 - 2*x^3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma