A017817 -id:A017817 - cp's OEIS frontend

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

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, 1088589, 1502555, 2073943

Offset: 0

N. J. A. Sloane

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..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.
For this family of sequences, a(n+1) is the number of compositions of n+1 into parts 1 and m. For n>=m, a(n-m+1)is the number of compositions of n in which each part is greater than m or equivalently, in which parts 1 through m are excluded. - Gregory L. Simay, Jul 14 2016
For this family of sequences, let a(m,n) = a(n-1) + a(n-m). Then the number of compositions of n having m as a least summand is a(m, n-m) - a(m+1, n-m-1). - Gregory L. Simay, Jul 14 2016
For n>=3, a(n-3) = number of compositions of n in which each part is >=4. - Milan Janjic, Jun 28 2010
For n>=1, number of compositions of n into parts == 1 (mod 4). Example: a(8)=5 because there are 5 compositions of 8 into parts 1 or 5: (1,1,1,1,1,1,1,1), (1,1,1,5), (1,1,5,1), (1,5,1,1), (5,1,1,1). - Adi Dani, Jun 16 2011
a(n+1) is the number of compositions of n into parts 1 and 4. - Joerg Arndt, Jun 25 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>=4, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >= 4, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1,2}. - Vladimir Baltic, Mar 07 2012
a(n+4) equals the number of binary words of length n having at least 3 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
From Clark Kimberling, Jun 13 2016: (Start)
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, 2*x, x+1, x^2}, etc.
Let T(r) be the tree obtained by substituting r for x.
If N is a positive integer such that r = N^(1/4) is not an integer, then the number of (not necessarily distinct) integers in g(n) is A003269(n), for n > = 1. See A274142. (End)

			G.f.: x + x^2 + x^3 + x^4 + 2*x^5 + 3*x^6 + 4*x^7 + 5*x^8 + 7*x^9 + 10*x^10 + ...
The number of compositions of 12 having 4 as a least summand is a(4, 12 -4 + 1) - a(5, 12 - 5 + 1) = A003269(9) - A003520(8) = 7-4 = 3. The compositions are (84), (48) and (444). - _Gregory L. Simay_, Jul 14 2016

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 120.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..501
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [The hal link does not always work. - _N. J. A. Sloane_, Feb 19 2025]
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [Local copy with annotations and a correction from _N. J. A. Sloane_, Feb 19 2025]
Peter G. Anderson, More Properties of the Zeckendorf Array, Fib. Quart. 52-5 (2014), 15-21. With 2 more initial zeros.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
Bruce M. Boman, Geometric Capitulum Patterns Based on Fibonacci p-Proportions, Fibonacci Quart. 58 (2020), no. 5, 91-102.
Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, University of Wisconsin, April 2012.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
Hùng Việt Chu, Nurettin Irmak, Steven J. Miller, László Szalay, and Sindy Xin Zhang, Schreier Multisets and the s-step Fibonacci Sequences, arXiv:2304.05409 [math.CO], 2023. See also Integers (2024) Vol. 24A, Art. No. A7, p. 3.
Adi Dani, Compositions of natural numbers over arithmetic progressions
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,3,1).
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 377
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3} gives seq. shifted 4 places left
R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 17.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 [math.CO] (2014), eq. (23).
Flaviano Morone, Ian Leifer, and Hernán A. Makse, Fibration symmetries uncover the building blocks of biological networks, Proceedings of the National Academy of Sciences (2020) Vol. 117, No. 15, 8306-8314.
Augustine O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.8.3.
Djamila Oudrar and Maurice Pouzet, Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes, arXiv:2312.05913 [math.CO], 2023. See p. 18.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
E. Wilson, The Scales of Mt. Meru
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Cf. A000045, A000079, A000930, A003520, A005708, A005709, A005710, A005711, A017898.
Cf. A048718, A072827, A072850, A072851, A072852, A072853, A072854, A072855, A072856.
Cf. A079955 - A080014.
See A017898 for an essentially identical sequence.
Row sums of A180184.

a003269 n = a003269_list !! n
a003269_list = 0 : 1 : 1 : 1 : zipWith (+) a003269_list
                                          (drop 3 a003269_list)
-- Reinhard Zumkeller, Feb 27 2011

I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1) + Self(n-4) :n in [1..50]]; // Marius A. Burtea, Sep 13 2019

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 3)}, unlabeled]: seq(count(SeqSetU, size=j), j=4..51);
seq(add(binomial(n-3*k,k),k=0..floor(n/3)),n=0..47); # Zerinvary Lajos, Apr 03 2007
A003269:=z/(1-z-z**4); # Simon Plouffe in his 1992 dissertation
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 3)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=3..50); # Zerinvary Lajos, Mar 26 2008
M:= Matrix(4, (i,j)-> if j=1 then [1,0,0,1][i] elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,2]; seq(a(n), n=0..48); # Alois P. Heinz, Jul 27 2008

a[0]= 0; a[1]= a[2]= a[3]= 1; a[n_]:= a[n]= a[n-1] + a[n-4]; Table[a[n], {n,0,50}]
CoefficientList[Series[x/(1-x-x^4), {x,0,50}], x] (* Zerinvary Lajos, Mar 29 2007 *)
Table[Sum[Binomial[n-3*i-1,i], {i,0,(n-1)/3}], {n,0,50}]
LinearRecurrence[{1,0,0,1}, {0,1,1,1}, 50] (* Robert G. Wilson v, Jul 12 2014 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,a+d}; NestList[nxt,{0,1,1,1},50][[;;,1]] (* Harvey P. Dale, May 27 2024 *)

{a(n) = polcoeff( if( n<0, (1 + x^3) / (1 + x^3 - x^4), 1 / (1 - x - x^4)) + x * O(x^abs(n)), abs(n))} /* Michael Somos, Jul 12 2003 */

@CachedFunction
def a(n): return ((n+2)//3) if (n<4) else a(n-1) + a(n-4) # a = A003269
[a(n) for n in (0..50)] # G. C. Greubel, Jul 25 2022

G.f.: x/(1-x-x^4).
G.f.: -1 + 1/(1-Sum_{k>=0} x^(4*k+1)).
a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) for n>4.
a(n) = floor(d*c^n + 1/2) where c is the positive real root of -x^4+x^3+1 and d is the positive real root of 283*x^4-18*x^2-8*x-1 (c=1.38027756909761411... and d=0.3966506381592033124...). - Benoit Cloitre, Nov 30 2002
Equivalently, a(n) = floor(c^(n+3)/(c^4+3) + 1/2) with c as defined above (see A086106). - Greg Dresden and Shuer Jiang, Aug 31 2019
a(n) = term (1,2) in the 4 X 4 matrix [1,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
From Paul Barry, Oct 20 2009: (Start)
a(n+1) = Sum_{k=0..n} C((n+3*k)/4,k)*((1+(-1)^(n-k))/2 + cos(Pi*n/2))/2;
a(n+1) = Sum_{k=0..n} C(k,floor((n-k)/3))(2*cos(2*Pi*(n-k)/3)+1)/3. (End)
a(n) = Sum_{j=0..(n-1)/3} binomial(n-1-3*j,j) (cf. A180184). - Vladimir Kruchinin, May 23 2011
A017817(n) = a(-4 - n) * (-1)^n. - Michael Somos, Jul 12 2003
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(2*k+1 + x^3)/( x*(2*k+2 + x^3) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 29 2013
Appears a(n) = hypergeometric([1/4-n/4,1/2-n/4,3/4-n/4,1-n/4], [1/3-n/3,2/3-n/3,1-n/3], -4^4/3^3) for n>=10. - Peter Luschny, Sep 18 2014

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

Initial 0 prepended by N. J. A. Sloane, Apr 09 2008

A079398 a(0)=0, a(1)=1, a(2)=1, a(3)=1, a(n) = a(n-3) + a(n-4) for n > 3.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 7, 8, 9, 12, 15, 17, 21, 27, 32, 38, 48, 59, 70, 86, 107, 129, 156, 193, 236, 285, 349, 429, 521, 634, 778, 950, 1155, 1412, 1728, 2105, 2567, 3140, 3833, 4672, 5707, 6973, 8505, 10379, 12680, 15478, 18884, 23059, 28158, 34362

Offset: 0

Benoit Cloitre, Feb 16 2003

P(0)=P(1)=P(2)=P(3)=1, for m > 3: P(m) = P(m-3) + P(m-4) is the 3rd sequence in the series: Fibonacci sequence, Padovan sequence, ... The Padovan sequence (whose ratio of successive terms approaches the plastic constant) is similar to the Perrin sequence. - Jonathan Vos Post, Jan 23 2005
Binomial transform yields A079398 without the initial (0,1,1,1). - R. J. Mathar, Apr 09 2008
a(n+1) corresponds to the diagonal sums of "triangle": 1; 1; 1; 1,1; 1,1; 1,1; 1,2,1; 1,2,1; 1,2,1; 1,3,3,1; 1,3,3,1; 1,3,3,1; 1,4,6,4,1; ..., rows of Pascal's triangle (A007318) repeated three times. - Philippe Deléham, Dec 13 2008
a(n) is the number of pairs of rabbits living at month n with the following rules: a pair of rabbits born in month n begins to procreate in month n + 3, procreates again in month n + 4, and dies at the end of this month (each pair therefore gives birth to 2 pairs); warning! The first pair is born in month 2. - Robert FERREOL, Oct 24 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart. 44 (2006), no. 4, 335-340.
Eric Weisstein's World of Mathematics, Padovan Sequence.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,1).

Cf. A000931.

CoefficientList[Series[x (1 + x + x^2)/(1 - x^3 - x^4), {x, 0, 60}], x] (* Vincenzo Librandi, Mar 16 2014 *)
LinearRecurrence[{0, 0, 1, 1}, {0, 1, 1, 1}, 60] (* Jean-François Alcover, Dec 05 2017 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,a+b}; NestList[nxt,{0,1,1,1},60][[;;,1]] (* Harvey P. Dale, Apr 27 2023 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,0,0]^n*[0;1;1;1])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

x='x+O('x^50); concat([0], Vec(x*(1+x+x^2)/(1-x^3-x^4))) \\ G. C. Greubel, Apr 30 2017

a(0)=0, a(1)=1, a(2)=1, a(3)=1, a(n) = a(n-3) + a(n-4) for n > 3. - Colin Barker, Sep 18 2013
From Paul Barry, Jul 06 2004: (Start)
a(n) = Sum_{k=0..floor((n-1)/2)} binomial(floor((n-k-1)/3), k) (offset 0).
a(n) = (Sum_{k=0..floor(n/2)} binomial(floor((n-k-1)/3), k))-0^n (offset 0). (End)
For n > 1, a(n) = P(n-2) where P(n) is defined by: P(0)=P(1)=P(2)=P(3)=1, for m > 3: P(m) = P(m-3) + P(m-4). - Jonathan Vos Post, Jan 23 2005
The same sequence may be constructed as follows: Let M = {{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}}; v[1] = {1, 1, 1, 1}; v[n] = M.v[n - 1]. Then a(n) = v[n][[1]]. - Roger L. Bagula, Sep 16 2006
O.g.f.: -x^2*(1+x+x^2)/(-1+x^3+x^4). a(n) = A017817(n-1) + A017817(n-2) + A017817(n-3). - R. J. Mathar, Apr 09 2008

Recurrence corrected by Colin Barker, Sep 18 2013

A306713 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of g.f. 1/(1-x^k-x^(k+1)).

Original entry on oeis.org

1, 1, 1, 1, 0, 2, 1, 0, 1, 3, 1, 0, 0, 1, 5, 1, 0, 0, 1, 1, 8, 1, 0, 0, 0, 1, 2, 13, 1, 0, 0, 0, 1, 0, 2, 21, 1, 0, 0, 0, 0, 1, 1, 3, 34, 1, 0, 0, 0, 0, 1, 0, 2, 4, 55, 1, 0, 0, 0, 0, 0, 1, 0, 1, 5, 89, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 7, 144, 1, 0, 0, 0, 0, 0, 0, 1, 0, 2, 3, 9, 233

Offset: 0

Seiichi Manyama, Mar 05 2019

A(n,k) is the number of compositions of n into parts k and k+1.

			Square array begins:
    1, 1, 1, 1, 1, 1, 1, 1, 1, ...
    1, 0, 0, 0, 0, 0, 0, 0, 0, ...
    2, 1, 0, 0, 0, 0, 0, 0, 0, ...
    3, 1, 1, 0, 0, 0, 0, 0, 0, ...
    5, 1, 1, 1, 0, 0, 0, 0, 0, ...
    8, 2, 0, 1, 1, 0, 0, 0, 0, ...
   13, 2, 1, 0, 1, 1, 0, 0, 0, ...
   21, 3, 2, 0, 0, 1, 1, 0, 0, ...
   34, 4, 1, 1, 0, 0, 1, 1, 0, ...
   55, 5, 1, 2, 0, 0, 0, 1, 1, ...

Seiichi Manyama, Antidiagonals n = 0..139, flattened

Columns 1-10 give A000045(n+1), A182097, A017817, A017827, A017837, A017847, A017857, A017867, A017877, A017887.

Cf. A306646, A306680.

T[n_, k_] := Sum[Binomial[j, n-k*j], {j, 0, Floor[n/k]}]; Table[T[k, n - k + 1], {n, 0, 12}, {k, 0, n}] // Flatten (* Amiram Eldar, Jun 21 2021 *)

A(n,k) = Sum_{j=0..floor(n/k)} binomial(j,n-k*j).

A196138 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,2,1,3,4 for x=0,1,2,3,4.

Original entry on oeis.org

1, 0, 0, 1, 4, 1, 2, 3, 3, 2, 1, 8, 4, 8, 1, 1, 14, 19, 19, 14, 1, 3, 19, 31, 31, 31, 19, 3, 3, 46, 70, 165, 165, 70, 46, 3, 2, 56, 117, 251, 326, 251, 117, 56, 2, 4, 133, 253, 931, 1350, 1350, 931, 253, 133, 4, 6, 184, 538, 1880, 3288, 3716, 3288, 1880, 538, 184, 6, 5, 372

Offset: 1

R. H. Hardin Sep 28 2011

Every 0 is next to 0 0's, every 1 is next to 1 2's, every 2 is next to 2 1's, every 3 is next to 3 3's, every 4 is next to 4 4's
Table starts
.1...0....1.....2......1......1.......3........3.........2..........4
.0...4....3.....8.....14.....19......46.......56.......133........184
.1...3....4....19.....31.....70.....117......253.......538.......1169
.2...8...19....31....165....251.....931.....1880......5556......15236
.1..14...31...165....326...1350....3288....12943.....33772.....113604
.1..19...70...251...1350...3716...20706....63545....255501.....992477
.3..46..117...931...3288..20706...75720...384083...1662512....8212668
.3..56..253..1880..12943..63545..384083..2040678..11848389...73800939
.2.133..538..5556..33772.255501.1662512.11848389..86632050..560572499
.4.184.1169.15236.113604.992477.8212668.73800939.560572499.5257705657

			Some solutions for n=6 k=4
..2..1..0..1....1..2..2..1....1..2..1..0....1..2..1..0....0..2..1..0
..1..0..1..2....0..1..1..1....1..2..0..1....1..0..1..2....1..1..1..2
..0..1..1..2....2..1..1..2....0..1..1..2....2..1..0..1....2..1..0..1
..1..2..0..1....1..0..1..2....2..1..1..2....0..1..2..1....0..1..2..1
..1..0..2..1....1..2..1..1....1..1..0..1....2..1..0..1....2..1..0..1
..2..1..1..0....1..2..1..0....0..2..1..0....1..0..1..2....1..0..1..2

R. H. Hardin, Table of n, a(n) for n = 1..219

Column 1 is A017817(n+3)

A197250 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,0,1,1,1 for x=0,1,2,3,4.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 1, 8, 8, 1, 3, 16, 3, 16, 3, 3, 40, 53, 53, 40, 3, 2, 80, 110, 275, 110, 80, 2, 4, 192, 227, 780, 780, 227, 192, 4, 6, 400, 1035, 5713, 5062, 5713, 1035, 400, 6, 5, 936, 2004, 16773, 31276, 31276, 16773, 2004, 936, 5, 6, 1984, 7529, 98870, 213912, 405065

Offset: 1

R. H. Hardin Oct 12 2011

Every 0 is next to 0 0's, every 1 is next to 1 0's, every 2 is next to 2 1's, every 3 is next to 3 1's, every 4 is next to 4 1's
Table starts
.1....2.....1.......1........3..........3............2.............4
.2....4.....8......16.......40.........80..........192...........400
.1....8.....3......53......110........227.........1035..........2004
.1...16....53.....275......780.......5713........16773.........98870
.3...40...110.....780.....5062......31276.......213912.......1244680
.3...80...227....5713....31276.....405065......3264225......29975706
.2..192..1035...16773...213912....3264225.....48703999.....692974749
.4..400..2004...98870..1244680...29975706....692974749...11304892092
.6..936..7529..393913..8149652..324191969...9613268927..308547360234
.5.1984.20633.1869033.54813300.2687575073.144634486646.5580867056186

			Some solutions containing all values 0 to 4 for n=6 k=4
..0..1..1..2....1..2..2..1....1..0..1..1....0..1..1..0....1..0..1..1
..1..1..0..1....0..1..1..0....1..1..2..0....2..1..4..1....2..1..3..0
..1..3..2..1....2..1..4..1....0..1..3..1....1..0..1..2....0..1..1..2
..0..1..1..0....1..0..1..1....1..4..1..3....1..3..1..0....1..1..0..1
..1..1..4..1....2..1..1..0....1..1..0..1....0..1..1..2....1..4..1..2
..1..0..1..2....0..1..3..1....0..1..1..2....1..1..0..1....0..1..1..0

R. H. Hardin, Table of n, a(n) for n = 1..199

Column 1 is A017817(n+5)

A197889 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,2,1,1,1 for x=0,1,2,3,4.

Original entry on oeis.org

1, 0, 0, 1, 4, 1, 2, 3, 3, 2, 1, 14, 6, 14, 1, 1, 18, 47, 47, 18, 1, 3, 43, 77, 155, 77, 43, 3, 3, 78, 196, 835, 835, 196, 78, 3, 2, 154, 529, 2263, 2730, 2263, 529, 154, 2, 4, 305, 1637, 10827, 17890, 17890, 10827, 1637, 305, 4, 6, 572, 4235, 38938, 92843, 129294, 92843

Offset: 1

R. H. Hardin Oct 19 2011

Every 0 is next to 0 0's, every 1 is next to 1 2's, every 2 is next to 2 1's, every 3 is next to 3 1's, every 4 is next to 4 1's
Table starts
.1...0.....1......2........1.........1...........3...........3...........2
.0...4.....3.....14.......18........43..........78.........154.........305
.1...3.....6.....47.......77.......196.........529........1637........4235
.2..14....47....155......835......2263.......10827.......38938......157178
.1..18....77....835.....2730.....17890.......92843......567991.....3000116
.1..43...196...2263....17890....129294.....1134527.....9389938....74334188
.3..78...529..10827....92843...1134527....13253562...145351090..1728849664
.3.154..1637..38938...567991...9389938...145351090..2512321052.39163260138
.2.305..4235.157178..3000116..74334188..1728849664.39163260138
.4.572.11211.654028.17111462.612587633.19259087568

			Some solutions containing all values 0 to 4 for n=6 k=4
..1..2..2..1....0..2..1..0....0..1..2..0....1..2..0..1....1..2..2..1
..3..1..1..0....1..1..1..2....2..1..1..1....3..1..1..2....0..1..1..0
..1..4..1..2....2..1..4..1....1..4..1..2....1..4..1..2....1..4..1..2
..2..1..4..1....2..1..1..3....0..1..1..2....2..1..4..1....2..1..3..1
..0..1..1..3....1..0..2..1....1..2..3..1....2..1..1..3....2..1..3..1
..1..2..2..1....0..1..2..1....1..2..1..0....1..0..2..1....1..0..1..2

R. H. Hardin, Table of n, a(n) for n = 1..144

Column 1 is A017817(n+3)

A198185 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,2,1,0,0 for x=0,1,2,3,4.

Original entry on oeis.org

1, 0, 0, 1, 4, 1, 2, 3, 3, 2, 1, 8, 9, 8, 1, 1, 16, 25, 25, 16, 1, 3, 21, 77, 59, 77, 21, 3, 3, 56, 148, 331, 331, 148, 56, 3, 2, 70, 395, 883, 2033, 883, 395, 70, 2, 4, 171, 866, 3485, 8298, 8298, 3485, 866, 171, 4, 6, 256, 2346, 12030, 48958, 51688, 48958, 12030, 2346, 256, 6

Offset: 1

R. H. Hardin Oct 21 2011

Every 0 is next to 0 0's, every 1 is next to 1 2's, every 2 is next to 2 1's, every 3 is next to 3 0's, every 4 is next to 4 0's
Table starts
.1...0....1......2.......1.........1..........3............3.............2
.0...4....3......8......16........21.........56...........70...........171
.1...3....9.....25......77.......148........395..........866..........2346
.2...8...25.....59.....331.......883.......3485........12030.........43774
.1..16...77....331....2033......8298......48958.......216307.......1155412
.1..21..148....883....8298.....51688.....395340......2639341......19059216
.3..56..395...3485...48958....395340....4522496.....41084248.....441157382
.3..70..866..12030..216307...2639341...41084248....559601114....8186901838
.2.171.2346..43774.1155412..19059216..441157382...8186901838..174674654015
.4.256.5663.155664.5522239.135044844.4292509761.115542567852.3432842252818

			Some solutions containing all values 0 to 4 for n=6 k=4
..2..1..1..0....2..1..0..1....0..1..1..2....0..3..0..1....0..1..2..1
..1..0..2..1....1..0..3..2....1..2..0..1....3..0..3..2....3..0..3..0
..0..4..0..1....0..4..0..1....1..0..4..0....0..4..0..1....0..4..0..3
..3..0..1..2....3..0..3..1....2..1..0..3....3..0..3..0....1..0..4..0
..0..1..1..2....0..3..0..2....2..1..1..0....0..1..1..2....2..3..0..3
..1..2..0..1....1..2..1..1....1..0..2..1....1..2..0..1....1..0..3..0

R. H. Hardin, Table of n, a(n) for n = 1..179

Column 1 is A017817(n+3)

A339060 Number of compositions (ordered partitions) of n into distinct parts congruent to 3 mod 4.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 4, 1, 0, 6, 4, 1, 0, 6, 6, 1, 0, 12, 6, 1, 0, 18, 8, 1, 24, 24, 8, 1, 24, 30, 10, 1, 48, 42, 10, 1, 72, 48, 12, 1, 120, 60, 12, 121, 144, 72, 14, 121, 216, 84, 14, 241, 264, 96, 16, 361, 360, 114, 16, 601, 432, 126, 18, 841

Offset: 0

Ilya Gutkovskiy, Nov 22 2020

nonn

			a(21) = 6 because we have [11, 7, 3], [11, 3, 7], [7, 11, 3], [7, 3, 11], [3, 11, 7] and [3, 7, 11].

Index entries for sequences related to compositions

Cf. A004767, A017817, A032020, A032021, A035462, A147599, A337547, A337548, A339059.

nmax = 75; CoefficientList[Series[Sum[k! x^(k (2 k + 1))/Product[1 - x^(4 j), {j, 1, k}], {k, 0, nmax}], {x, 0, nmax}], x]

G.f.: Sum_{k>=0} k! * x^(k*(2*k + 1)) / Product_{j=1..k} (1 - x^(4*j)).

A050443 a(0)=4, a(1)=0, a(2)=0, a(3)=3; thereafter a(n) = a(n-3) + a(n-4).

Original entry on oeis.org

4, 0, 0, 3, 4, 0, 3, 7, 4, 3, 10, 11, 7, 13, 21, 18, 20, 34, 39, 38, 54, 73, 77, 92, 127, 150, 169, 219, 277, 319, 388, 496, 596, 707, 884, 1092, 1303, 1591, 1976, 2395, 2894, 3567, 4371, 5289, 6461, 7938, 9660, 11750, 14399, 17598, 21410, 26149, 31997

Offset: 0

Tony Davie (ad(AT)dcs.st-and.ac.uk), Dec 23 1999

Related to Perrin sequence. a(p) is divisible by p for primes p.
Wells states that Mihaly Bencze [Beneze] (1998) proved the divisibility property for this sequence: that a(n) is always divisible by n when n is prime. - Gary W. Adamson, Nov 14 2006
As a(n) = trace(M^n) where M = [0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,0,0], the previous property comes from the fact that trace(M^n) = trace(M) (= 0) mod n for n prime. - Robert FERREOL, Apr 09 2024

			a(11) = 11 because a(7) = 7 and a(8) = 4.

David Wells, "Prime Numbers, the Most Mysterious Figures in Math", John Wiley & Sons, Inc.; 2005, p. 103.

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Sadjia Abbad and Hacène Belbachir, The r-Fibonacci polynomial and its companion sequences linked with some classical sequences, Integers (2025), Vol. 25, Art. No. A38. See p. 17.
Mihaly Bencze, Dan Saracino, and Allen Stenger, Solution of Problem 10655: A Recurrence Generating Multiples of Primes, American Mathematical Monthly 107 (2000) 281-282.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Gregory T. Minton, Linear recurrence sequences satisfying congruence conditions, Proc. Amer. Math. Soc. (2014), Vol. 142, No. 7, 2337-2352. MR3195758.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,1).

Column 3 of A306646.
Cf. A001608, A052338.
Cf. A087935, A087936.

a:=[4,0,0,3];; for n in [5..60] do a[n]:=a[n-3]+a[n-4]; od; Print(a); # Muniru A Asiru, Mar 09 2019

I:=[4,0,0,3]; [n le 4 select I[n] else Self(n-3) +Self(n-4): n in [1..60]]; // G. C. Greubel, Mar 04 2019

LinearRecurrence[{0,0,1,1}, {4,0,0,3}, 60] (* G. C. Greubel, Mar 04 2019 *)

polsym(x^4-x-1,55) \\ Joerg Arndt, Mar 04 2019

((4-x^3)/(1-x^3-x^4)).series(x, 60).coefficients(x, sparse=False) # G. C. Greubel, Mar 04 2019

G.f.: (4-x^3)/(1-x^3-x^4). - Christian G. Bower, Dec 23 1999
a(n) = (x_1)^n + (x_2)^n + (x_3)^n + (x_4)^n where (x_i) 1 <= i <= 4 are the roots of x^4 = x + 1. - Benoit Cloitre, Oct 27 2003
Let M = the 4 X 4 matrix [0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,0,0]; then a(n) = the leftmost term of M^n * [4,0,0,3]. Example: a(13) = 13 since M^13 * [4,0,0,3] = [13,21,18,20]. - Gary W. Adamson, Nov 14 2006
a(0) = 4 and a(n) = n*Sum_{k=1..floor(n/3)} binomial(k,n-3*k)/k for n > 0. - Seiichi Manyama, Mar 04 2019
From Aleksander Bosek, Mar 10 2019: (Start)
a(n+10) = a(n+5) + 2*a(n+3) + a(n).
a(n+11) = a(n+6) + 3*a(n+1) + 2*a(n).
a(n+12) = a(n+10) + 5*a(n+5) + a(n).
a(n+12) = 3*a(n+5) + a(n+3) + a(n).
a(n+13) = 3*a(n+6) + 2*a(n+1) + a(n).
a(n+14) = 2*a(n+8) + 3*a(n+3) + a(n).
a(n+15) = 2*a(n+7) + 4*a(n+5) + a(n).
a(n+15) = 2*a(n+9) + 4*a(n+1) + 3*a(n).
a(n+19) = a(n+17) + 5*a(n+5) + a(n).
a(n+20) = 5*a(n+10) + 6*a(n+5) + a(n).
a(n+22) = a*(n+21) + 5*a(n+5) + a(n).
a(n+25) = 2*a(n+21) + 5*a(n+5) + a(n).
a((s+4)*n+m) = Sum_{l=0..n} binomial(n-l,l)*a(s*n+l+m) for every m,s > 0.
a(m) = Sum_{l=0..n}(-1)^{n-l}*binomial(n-l,l)*a(m+n+3*l) for every m > 0. (End)
a(n) = 4*A017817(n) - A017817(n-3). - R. J. Mathar, Aug 10 2021

More terms from Christian G. Bower, Dec 23 1999

More terms from Benoit Cloitre, Oct 27 2003

cp's OEIS Frontend

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A079398 a(0)=0, a(1)=1, a(2)=1, a(3)=1, a(n) = a(n-3) + a(n-4) for n > 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A306713 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of g.f. 1/(1-x^k-x^(k+1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A196138 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,2,1,3,4 for x=0,1,2,3,4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A197250 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,0,1,1,1 for x=0,1,2,3,4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A197889 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,2,1,1,1 for x=0,1,2,3,4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A198185 T(n,k)=Number of nXk 0..4 arrays with each element x equal to the number of its horizontal and vertical neighbors equal to 0,2,1,0,0 for x=0,1,2,3,4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A339060 Number of compositions (ordered partitions) of n into distinct parts congruent to 3 mod 4.

Views

Author

Keywords

Examples