

A003269


a(n) = a(n1) + a(n4) with a(0) = 0, a(1) = a(2) = a(3) = 1.
(Formerly M0526)


82



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n1) + a(nm), with a(n) = 1 for n = 0...m1. The generating function is 1/(1xx^m). Also a(n) = Sum_{i=0..n/m} binomial(n(m1)*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(nm+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(n1) + a(nm). Then the number of compositions of n having m as a least summand is a(m, nm)  a(m+1, nm1).  Gregory L. Simay, Jul 14 2016
For n>=3, a(n3) = 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 pcolored compositions of n. For n>=4, 2*a(n3) equals the number of 2colored 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 nth 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)


REFERENCES

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).


LINKS

T. D. Noe, Table of n, a(n) for n = 0..501
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119135.
D. Birmajer, J. B. Gil, M. D. Weiner, n the Enumeration of Restricted Words over a Finite Alphabet , J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilfequivalence on Theta_kembeddings, University of Wisconsin, April 2012.
Adi Dani, Compositions of natural numbers over arithmetic progressions
E. Di Cera and Y. Kong, Theory of multivalent binding in one and twodimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107124.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in kZeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012.
I. M. Gessel, 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, C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277289, sequence u(n,3,1).
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371380.
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.
R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and NonTatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 17.
A. O. Munagi, Eulertype identities for integer compositions via zigzag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
Augustine O. Munagi, Integer Compositions and HigherOrder 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.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.
E. Wilson, The Scales of Mt. Meru
Index entries for twoway infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).


FORMULA

G.f.: x/(1xx^4).
G.f.: 1 + 1/(1Sum_{k>=0} x^(4*k+1)).
a(n) = a(n3) + a(n4) + a(n5) + a(n6) 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^418*x^28*x1 (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)^(nk))/2 + cos(Pi*n/2))/2;
a(n+1) = Sum_{k=0..n} C(k,floor((nk)/3))(2*cos(2*Pi*(nk)/3)+1)/3. (End)
a(n) = Sum_{j=0..(n1)/3} binomial(n13*j,j).  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/4n/4,1/2n/4,3/4n/4,1n/4], [1/3n/3,2/3n/3,1n/3], 4^4/3^3) for n>=10.  Peter Luschny, Sep 18 2014


EXAMPLE

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) = 74 = 3. The compositions are (84), (48) and (444).  Gregory L. Simay, Jul 14 2016


MAPLE

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 3)}, unlabeled]: seq(count(SeqSetU, size=j), j=4..51);
seq(add(binomial(n3*k, k), k=0..floor(n/3)), n=0..47); # Zerinvary Lajos, Apr 03 2007
A003269:=z/(1zz**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=j1) then 1 else 0 fi); a:= n> (M^(n))[1, 2]; seq(a(n), n=0..48); # Alois P. Heinz, Jul 27 2008


MATHEMATICA

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, 40} ]
CoefficientList[Series[x/(1  x  x^4), {x, 0, 50}], x] (* Zerinvary Lajos, Mar 29 2007 *)
Table[Sum[Binomial[n  3i  1, i], {i, 0, 35}], {n, 0, 35}]
LinearRecurrence[{1, 0, 0, 1}, {0, 1, 1, 1}, 49] (* Robert G. Wilson v, Jul 12 2014 *)


PROG

(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 */
(Haskell)
a003269 n = a003269_list !! n
a003269_list = 0 : 1 : 1 : 1 : zipWith (+) a003269_list
(drop 3 a003269_list)
 Reinhard Zumkeller, Feb 27 2011
(MAGMA) I:=[0, 1, 1, 1]; [n le 4 select I[n] else Self(n1) + Self(n4) :n in [1..50]]; // Marius A. Burtea, Sep 13 2019


CROSSREFS

Cf. A000045, A000079, A000930, A003520, A005708, A005709, A005710, A005711, A017898, A048718, A072827, A072850A072856, A079955A080014.
See A017898 for an essentially identical sequence.
Sequence in context: A099559 A247084 A017898 * A087221 A295072 A206739
Adjacent sequences: A003266 A003267 A003268 * A003270 A003271 A003272


KEYWORD

nonn,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
Initial 0 prepended by N. J. A. Sloane, Apr 09 2008


STATUS

approved



