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-3 of 3 results.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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)

Examples

			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

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

Crossrefs

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.

Programs

  • 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(n-1) + Self(n-4) :n in [1..50]]; // Marius A. Burtea, Sep 13 2019
  • 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(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
  • 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,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 *)
  • 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 */
  • SageMath
    @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

Formula

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

Extensions

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

A158777 Irregular array T(n,k), read by rows: row n is the polynomial expansion in t of p(x,t) = exp(t*x)/(1 - x/t - t^4 * x^4) with weighting factors t^n*n!.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 2, 0, 1, 6, 0, 6, 0, 3, 0, 1, 24, 0, 24, 0, 12, 0, 4, 0, 25, 120, 0, 120, 0, 60, 0, 20, 0, 245, 0, 121, 720, 0, 720, 0, 360, 0, 120, 0, 2190, 0, 1446, 0, 361, 5040, 0, 5040, 0, 2520, 0, 840, 0, 20370, 0, 15162, 0, 5047, 0, 841, 40320, 0, 40320, 0, 20160, 0, 6720, 0
Offset: 0

Views

Author

Roger L. Bagula, Mar 26 2009

Keywords

Comments

Row sums are A334157: {1, 2, 5, 16, 89, 686, 5917, 54860, 588401, 7370074, ...}.
Outer diagonal is A330045: {1, 1, 1, 1, 25, 121, 361, 841, 42001, 365905, ...}.
From Petros Hadjicostas, Apr 15 2020: (Start)
To prove the general formula below for T(n,2*m), let v = x/t in the equation Sum_{n,k >= 0} (T(n,k)/n!) * (x/t)^n * t^k = p(x,t). We get Sum_{n,k >= 0} (T(n,k)/n!) * v^n * t^k = exp(t^2*v)/(1 - v - t^8*v^4).
Using the Taylor expansions of exp(t^2*v) and 1/(1 - v - t^8*v^4) around v = 0 (from array A180184), we get that Sum_{n,k >= 0} (T(n,k)/n!) * v^n * t^k = (Sum_{n >= 0} (t^2*v)^n/n!) * (Sum_{n >= 0} Sum_{h=0..floor(n/4)} binomial(n - 3*h, h)*t^(8*h)*v^n).
Using the Cauchy product of the above two series, for each n >= 0, we get Sum_{k >= 0} (T(n,k)/n!)*t^k = Sum_{l=0..n} Sum_{h=0..floor(l/4)} (binomial(l - 3*h, h)/(n-l)!)*t^(8*h+2*n-2*l). This implies that T(n,k) = 0 for odd k >= 1.
Letting k = 2*m = 8*h + 2*n - 2*l and s = n - l, we get Sum_{m >= 0} (T(n, 2*m)/n!)*t^(2*m) = Sum_{m >= 0} Sum_{s=0..m with 4|(m-s)} (binomial(n - s - 3*(m - s)/4, (m - s)/4)/s!)*t^(2*m) (and also that T(n,2*j) = 0 for j > m). Equating coefficients, we get the formula for T(n,2*m) shown below. (End)

Examples

			Array T(n,k) (with n >= 0 and 0 <= k <= 2*n) begins as follows:
     1;
     1, 0,    1;
     2, 0,    2, 0,    1;
     6, 0,    6, 0,    3, 0,   1;
    24, 0,   24, 0,   12, 0,   4, 0,    25;
   120, 0,  120, 0,   60, 0,  20, 0,   245, 0,   121;
   720, 0,  720, 0,  360, 0, 120, 0,  2190, 0,  1446, 0,  361;
  5040, 0, 5040, 0, 2520, 0, 840, 0, 20370, 0, 15162, 0, 5047, 0, 841;
  ...

Crossrefs

Cf. A000142, A001710, A001715, A180184, A330045, A334157.

Programs

  • Maple
    # Triangle T(n, k) without the zeros (even k):
W := proc(n, m) local v, s, h; v := 0;
for s from 0 to m do
if 0 = (m - s) mod 4 then
h := (m - s)/4;
v := v + binomial(n - s - 3*h, h)/s!;
end if; end do; n!*v; end proc;
for n1 from 0 to 20 do
seq(W(n1,m1), m1=0..n1); end do; # Petros Hadjicostas, Apr 15 2020
  • Mathematica
    (* Generates the sequence in the data section *)
Table[Expand[t^n*n!*SeriesCoefficient[Series[Exp[t*x]/(1 - x/t - t^4*x^4), {x, 0, 20}], n]], {n, 0, 10}];
a = Table[CoefficientList[Expand[t^n*n!*SeriesCoefficient[Series[Exp[t*x]/(1 - x/t - t^4*x^4), {x, 0, 20}], n]], t], {n, 0, 10}];
Flatten[%]
(* Generates row sums *)
Table[Apply[Plus, CoefficientList[Expand[t^n*n!*SeriesCoefficient[Series[Exp[t*x]/( 1 - x/t - t^4*x^4), {x, 0, 20}], n]], t]], {n, 0, 10}];

Formula

T(n,k) = [t^k] (t^n * n! * ([x^n] p(x,t))), where p(x,t) = exp(t*x)/(1 - x/t - t^4*x^4).
From Petros Hadjicostas, Apr 15 2020: (Start)
Sum_{n,k >= 0} (T(n,k)/n!) * (x/t)^n * t^k = p(x,t).
T(n,0) = n! = A000142(n) for n >= 0; T(n,2) = n! for n >= 1; T(n,4) = n!/2 = A001710(n) for n >= 2; T(n,6) = n!/6 = A001715(n) for n >= 3.
T(n,2*m) = n! * Sum_{s = 0..m with 4|(m-s)} binomial(n - s - 3*(m-s)/4, (m-s)/4)/s! for n >= 0 and 0 <= m <= n.
T(n,2*n) = A330045(n) for n >= 0. (End)

Extensions

Various sections edited by Petros Hadjicostas, Apr 13 2020

A352041 a(0) = 1; a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k,k) * a(k).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 96, 136, 196, 285, 417, 614, 909, 1349, 2002, 2968, 4394, 6493, 9572, 14074, 20639, 30189, 44049, 64123, 93151, 135080, 195599, 282915, 408884, 590658, 853080, 1232168, 1780190, 2573059, 3721103
Offset: 0

Views

Author

Ilya Gutkovskiy, Mar 01 2022

Keywords

Crossrefs

Cf. A092684, A180184, A352039.

Programs

  • Mathematica
    a[0] = 1; a[n_] := a[n] = Sum[Binomial[n - 3 k, k] a[k], {k, 0, Floor[n/4]}]; Table[a[n], {n, 0, 44}]
nmax = 44; A[] = 1; Do[A[x] = A[x^4/(1 - x)]/(1 - x) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

Formula

G.f. A(x) satisfies: A(x) = A(x^4/(1 - x)) / (1 - x).
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.