|
%I M0526 #261 Dec 22 2023 11:03:50
%S 0,1,1,1,1,2,3,4,5,7,10,14,19,26,36,50,69,95,131,181,250,345,476,657,
%T 907,1252,1728,2385,3292,4544,6272,8657,11949,16493,22765,31422,43371,
%U 59864,82629,114051,157422,217286,299915,413966,571388,788674,1088589,1502555,2073943
%N a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.
%C 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.
%C 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
%C 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
%C For n>=3, a(n-3) = number of compositions of n in which each part is >=4. - _Milan Janjic_, Jun 28 2010
%C 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
%C a(n+1) is the number of compositions of n into parts 1 and 4. - _Joerg Arndt_, Jun 25 2011
%C 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
%C 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
%C 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
%C From _Clark Kimberling_, Jun 13 2016: (Start)
%C 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*.
%C 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.
%C Let T(r) be the tree obtained by substituting r for x.
%C 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)
%D A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 120.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A003269/b003269.txt">Table of n, a(n) for n = 0..501</a>
%H Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, <a href="https://www.emis.de/journals/JIS/VOL22/Shattuck/shattuck13.html">Some New Restricted n-Color Composition Functions</a>, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
%H Mudit Aggarwal and Samrith Ram, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Ram/ram3.html">Generating Functions for Straight Polyomino Tilings of Narrow Rectangles</a>, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
%H Michael A. Allen, <a href="https://arxiv.org/abs/2209.01377">On a Two-Parameter Family of Generalizations of Pascal's Triangle</a>, arXiv:2209.01377 [math.CO], 2022.
%H Peter G. Anderson, <a href="https://www.fq.math.ca/Papers1/52-5/Anderson.pdf">More Properties of the Zeckendorf Array</a>, Fib. Quart. 52-5 (2014), 15-21. With 2 more initial zeros.
%H Vladimir Baltic, <a href="http://dx.doi.org/10.2298/AADM1000008B">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
%H Bruce M. Boman, <a href="https://www.fq.math.ca/Papers1/58-5/boman.pdf">Geometric Capitulum Patterns Based on Fibonacci p-Proportions</a>, Fibonacci Quart. 58 (2020), no. 5, 91-102.
%H Russ Chamberlain, Sam Ginsburg and Chi Zhang, <a href="http://digital.library.wisc.edu/1793/61870">Generating Functions and Wilf-equivalence on Theta_k-embeddings</a>, University of Wisconsin, April 2012.
%H P. Chinn and S. Heubach, <a href="/A005710/a005710.pdf">(1, k)-compositions</a>, Congr. Numer. 164 (2003), 183-194. [Local copy]
%H Hung Viet Chu, Nurettin Irmak, Steven J. Miller, Laszlo Szalay, and Sindy Xin Zhang, <a href="https://arxiv.org/abs/2304.05409">Schreier Multisets and the s-step Fibonacci Sequences</a>, arXiv:2304.05409 [math.CO], 2023.
%H Adi Dani, <a href="/wiki/User:Adi_Dani/Compositions_of_natural_numbers_over_arithmetic_progressions">Compositions of natural numbers over arithmetic progressions</a>
%H E. Di Cera and Y. Kong, <a href="http://dx.doi.org/10.1016/S0301-4622(96)02178-3">Theory of multivalent binding in one and two-dimensional lattices</a>, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
%H Larry Ericksen and Peter G. Anderson, <a href="http://www.cs.rit.edu/~pga/k-zeck.pdf">Patterns in differences between rows in k-Zeckendorf arrays</a>, The Fibonacci Quarterly, Vol. 50, February 2012.
%H I. M. Gessel and Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5.
%H R. K. Guy, <a href="/A004001/a004001_2.pdf">Letter to N. J. A. Sloane with attachment, 1988</a>
%H V. C. Harris and C. C. Styles, <a href="http://www.fq.math.ca/Scanned/2-4/harris.pdf">A generalization of Fibonacci numbers</a>, Fib. Quart. 2 (1964) 277-289, sequence u(n,3,1).
%H J. Hermes, <a href="http://dx.doi.org/10.1007/BF01446684">Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden</a>, Math. Ann., 45 (1894), 371-380.
%H Brian Hopkins and Hua Wang, <a href="https://arxiv.org/abs/2003.05291">Restricted Color n-color Compositions</a>, arXiv:2003.05291 [math.CO], 2020.
%H Jia Huang, <a href="https://arxiv.org/abs/1812.11010">Compositions with restricted parts</a>, arXiv:1812.11010 [math.CO], 2018.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=377">Encyclopedia of Combinatorial Structures 377</a>
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html">Binomial Coefficients and Enumeration of Restricted Words</a>, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
%H Sergey Kirgizov, <a href="https://arxiv.org/abs/2201.00782">Q-bonacci words and numbers</a>, arXiv:2201.00782 [math.CO], 2022.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 17.
%H R. J. Mathar, <a href="https://arxiv.org/abs/1406.7788">Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices</a>, arXiv:1406.7788 [math.CO] (2014), eq. (23).
%H Flaviano Morone, Ian Leifer, and Hernán A. Makse, <a href="https://doi.org/10.1073/pnas.1914628117">Fibration symmetries uncover the building blocks of biological networks</a>, Proceedings of the National Academy of Sciences (2020) Vol. 117, No. 15, 8306-8314.
%H Augustine O. Munagi, <a href="https://www.emis.de/journals/INTEGERS/papers/m60/m60.Abstract.html">Euler-type identities for integer compositions via zig-zag graphs</a>, Integers 12 (2012), Paper No. A60, 10 pp.
%H Augustine O. Munagi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Munagi/munagi10.html">Integer Compositions and Higher-Order Conjugation</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
%H Denis Neiter and Amsha Proag, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Proag/proag3.html">Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.8.3.
%H Djamila Oudrar and Maurice Pouzet, <a href="https://arxiv.org/abs/2312.05913">Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes</a>, arXiv:2312.05913 [math.CO], 2023. See p. 18.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H E. Wilson, <a href="http://www.anaphoria.com/meruone.PDF">The Scales of Mt. Meru</a>
%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,1).
%F G.f.: x/(1-x-x^4).
%F G.f.: -1 + 1/(1-Sum_{k>=0} x^(4*k+1)).
%F a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) for n>4.
%F 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
%F 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
%F 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
%F From _Paul Barry_, Oct 20 2009: (Start)
%F a(n+1) = Sum_{k=0..n} C((n+3*k)/4,k)*((1+(-1)^(n-k))/2 + cos(Pi*n/2))/2;
%F a(n+1) = Sum_{k=0..n} C(k,floor((n-k)/3))(2*cos(2*Pi*(n-k)/3)+1)/3. (End)
%F a(n) = Sum_{j=0..(n-1)/3} binomial(n-1-3*j,j) (cf. A180184). - _Vladimir Kruchinin_, May 23 2011
%F A017817(n) = a(-4 - n) * (-1)^n. - _Michael Somos_, Jul 12 2003
%F 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
%F 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
%e 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 + ...
%e 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
%p with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 3)}, unlabeled]: seq(count(SeqSetU, size=j), j=4..51);
%p seq(add(binomial(n-3*k,k),k=0..floor(n/3)),n=0..47); # _Zerinvary Lajos_, Apr 03 2007
%p A003269:=z/(1-z-z**4); # _Simon Plouffe_ in his 1992 dissertation
%p 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
%p 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
%t 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}]
%t CoefficientList[Series[x/(1-x-x^4), {x,0,50}], x] (* _Zerinvary Lajos_, Mar 29 2007 *)
%t Table[Sum[Binomial[n-3*i-1,i], {i,0,(n-1)/3}], {n,0,50}]
%t LinearRecurrence[{1,0,0,1}, {0,1,1,1}, 50] (* _Robert G. Wilson v_, Jul 12 2014 *)
%o (PARI) {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 */
%o (Haskell)
%o a003269 n = a003269_list !! n
%o a003269_list = 0 : 1 : 1 : 1 : zipWith (+) a003269_list
%o (drop 3 a003269_list)
%o -- _Reinhard Zumkeller_, Feb 27 2011
%o (Magma) 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
%o (SageMath)
%o @CachedFunction
%o def a(n): return ((n+2)//3) if (n<4) else a(n-1) + a(n-4) # a = A003269
%o [a(n) for n in (0..50)] # _G. C. Greubel_, Jul 25 2022
%Y Cf. A000045, A000079, A000930, A003520, A005708, A005709, A005710, A005711, A017898.
%Y Cf. A048718, A072827, A072850, A072851, A072852, A072853, A072854, A072855, A072856.
%Y Cf. A079955 - A080014.
%Y See A017898 for an essentially identical sequence.
%Y Row sums of A180184.
%K nonn,easy
%O 0,6
%A _N. J. A. Sloane_
%E Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
%E Initial 0 prepended by _N. J. A. Sloane_, Apr 09 2008
|
