A054879 -id:A054879 - cp's OEIS frontend

A081294 Expansion of (1-2x)/(1-4x).

1, 2, 8, 32, 128, 512, 2048, 8192, 32768, 131072, 524288, 2097152, 8388608, 33554432, 134217728, 536870912, 2147483648, 8589934592, 34359738368, 137438953472, 549755813888, 2199023255552, 8796093022208, 35184372088832

Offset: 0

Paul Barry, Mar 17 2003

Binomial transform of A046717. Second binomial transform of A000302 (with interpolated zeros). Partial sums are A007583.
Counts closed walks of length 2n at a vertex of the cyclic graph on 4 nodes C_4. With interpolated zeros, counts closed walks of length n at a vertex of the cyclic graph on 4 nodes C_4. - Paul Barry, Mar 10 2004
In general, Sum_{k=0..n} Sum_{j=0..n} C(2*(n-k), j)*C(2*k, j)*r^j has expansion (1 - (r+1)*x)/(1 - (r+3)*x - (r-1)*(r+3)*x^2 + (r-1)^3*x^3). - Paul Barry, Jun 04 2005 [corrected by Jason Yuen, Jan 20 2025]
a(n) is the number of binary strings of length 2n with an even number of 0's (and hence an even number of 1's). - Toby Gottfried, Mar 22 2010
Number of compositions of n where there are 2 sorts of part 1, 4 sorts of part 2, 8 sorts of part 3, ..., 2^k sorts of part k. - Joerg Arndt, Aug 04 2014
a(n) is also the number of permutations simultaneously avoiding 231 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl Aug 07 2014
INVERT transform of powers of 2 (A000079). - Alois P. Heinz, Feb 11 2021
a(n) is the number of elements in an n-interval of the binomial poset of even-sized subsets of positive integers, cf. Stanley reference and second formula by Paul Barry.  Each multichain 0 = x_0 <= x_1 <= x_2 = 1 in such an n-interval corresponds to a closed walk described above by Paul Barry.  More generally, each multichain 0 = x_0 <= x_1 <= ... <= x_k = 1 corresponds to a closed walk of length 2n on the k-dimensional hypercube, cf. A054879, A092812, A121822. - Geoffrey Critzer, Apr 21 2023

			G.f. = 1 + 2*x + 8*x^2 + 32*x^3 + 128*x^4 + 512*x^5 + 2048*x^6 + 8192*x^7 + ...

Richard P. Stanley, Enumerative Combinatorics, Vol 1, second edition, Example 3.18.3-f, page 323.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
M. Paukner, L. Pepin, M. Riehl, and J. Wieser, Pattern Avoidance in Task-Precedence Posets, arXiv:1511.00080 [math.CO], 2015-2016.
Index to divisibility sequences.
Index entries for linear recurrences with constant coefficients, signature (4).

Row sums of triangle A136158.

Cf. A000079, A081295, A009117, A016742, A054879, A092812, A121822. Essentially the same as A004171.

[(4^n+0^n)/2: n in [0..30]]; // Vincenzo Librandi, Jul 26 2011

R:=PowerSeriesRing(Rationals(), 25); Coefficients(R!( (1-2*x)/(1-4*x))); // Marius A. Burtea, Jan 20 2020

a:= n-> 2^max(0, (2*n-1)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 20 2017

CoefficientList[Series[(1-2x)/(1-4x),{x,0,40}],x] (* or *)
Join[{1}, NestList[4 # &, 2, 40]] (* Harvey P. Dale, Apr 22 2011 *)

a(n)=1<Charles R Greathouse IV, Jul 25 2011

x='x+O('x^100); Vec((1-2*x)/(1-4*x)) \\ Altug Alkan, Dec 21 2015

G.f.: (1-2*x)/(1-4*x).
a(n) = 4*a(n-1) n > 1, with a(0)=1, a(1)=2.
a(n) = (4^n+0^n)/2 (i.e., 1 followed by 4^n/2, n > 0).
E.g.f.: exp(2*x)*cosh(2*x) = (exp(4*x)+exp(0))/2. - Paul Barry, May 10 2003
a(n) = Sum_{k=0..n} C(2*n, 2*k). - Paul Barry, May 20 2003
a(n) = A001045(2*n+1) - A001045(2*n-1) + 0^n/2. - Paul Barry, Mar 10 2004
a(n) = 2^n*A011782(n); a(n) = gcd(A011782(2n), A011782(2n+1)). - Paul Barry, Jan 12 2005
a(n) = Sum_{k=0..n} Sum_{j=0..n} C(2*(n-k), j)*C(2*k, j). - Paul Barry, Jun 04 2005
a(n) = Sum_{k=0..n} A038763(n,k). - Philippe Deléham, Sep 22 2006
a(n) = Integral_{x=0..4} p(n,x)^2/(Pi*sqrt(x(4-x))) dx, where p(n,x) is the sequence of orthogonal polynomials defined by C(2*n,n): p(n,x) = (2*x-4)*p(n-1,x) - 4*p(n-2,x), with p(0,x)=1, p(1,x)=-2+x. - Paul Barry, Mar 01 2007
a(n) = ((2+sqrt(4))^n + (2-sqrt(4))^n)/2. - Al Hakanson (hawkuu(AT)gmail.com), Nov 22 2008
a(n) = A000079(n) * A011782(n). - Philippe Deléham, Dec 01 2008
a(n) = A004171(n-1) = A028403(n) - A000079(n) for n >= 1. - Jaroslav Krizek, Jul 27 2009
a(n) = Sum_{k=0..n} A201730(n,k)*3^k. - Philippe Deléham, Dec 06 2011
a(n) = Sum_{k=0..n} A134309(n,k)*2^k = Sum_{k=0..n} A055372(n,k). - Philippe Deléham, Feb 04 2012
G.f.: Q(0), where Q(k) = 1 - 2*x/(1 - 2/(2 - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 29 2013
E.g.f.: 1/2 + exp(4*x)/2 = (Q(0)+1)/2, where Q(k) = 1 + 4*x/(2*k+1 - 2*x*(2*k+1)/(2*x + (k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 29 2013
a(n) = ceiling( 2^(2n-1) ). - Wesley Ivan Hurt, Jun 30 2013
G.f.: 1 + 2*x/(1 + x)*( 1 + 5*x/(1 + 4*x)*( 1 + 8*x/(1 + 7*x)*( 1 + 11*x/(1 + 10*x)*( 1 + ... )))). - Peter Bala, May 27 2017
Sum_{n>=0} 1/a(n) = 5/3. - Amiram Eldar, Aug 18 2022
Sum_{n>=0} a(n)*x^n/A000680(n) = E(x)^2 where E(x) = Sum_{n>=0} x^n/A000680(n). - Geoffrey Critzer, Apr 21 2023

A066443 Number of distinct paths of length 2n+1 along edges of a unit cube between two fixed adjacent vertices.

Original entry on oeis.org

1, 7, 61, 547, 4921, 44287, 398581, 3587227, 32285041, 290565367, 2615088301, 23535794707, 211822152361, 1906399371247, 17157594341221, 154418349070987, 1389765141638881, 12507886274749927, 112570976472749341

Offset: 0

John W. Layman, Aug 12 2002

All members of sequence are also hex, or central hexagonal, numbers (A003215). (If n is a hex number, 9n - 2 is always a hex number; see recurrence.) - Matthew Vandermast, Mar 30 2003
The sequence 1,1,7,61,547,... with g.f. (1-9x+6x^2)/((1-x)(1-9x)) and a(n) = A054879(n)/3 + 2*0^n/3 gives the denominators in the probability that a random walk on the cube returns to its starting corner on the 2n-th step. - Paul Barry, Mar 11 2004
Equals row sums of even row terms of triangle A158303. - Gary W. Adamson, Mar 15 2009
It appears that a(n) is the n-th record value in A120437, which gives the  differences of A037314 (positive integers n such that the sum of the base 3 digits of n equals the sum of the base 9 digits of n). - John W. Layman, Dec 14 2010
Numbers in base 9 are 1, 6+1, 66+1, 666+1, 6666+1, 66666+1, etc.; that is, n 6's + 1. - Yuchun Ji, Aug 15 2019
All prime factors of a(n) are 1 mod 6. In addition, if n is not 1 mod 3 (first index being n=0), then 3 is a cubic residue modulo all prime factors of a(n). This provides a simple proof that there are infinitely many primes 1 mod 6 that have 3 as a cubic residue. - William Hu, Jul 26 2024

			From _Michael B. Porter_, Aug 22 2016: (Start)
Give coordinates (a,b,c) to the vertices of the cube, where a, b, and c are either 0 or 1. For n = 1, the a(1) = 7 paths of length 2n + 1 = 3 from (0,0,0) to (0,0,1) are:
(0,0,0) -> (0,0,1) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (0,0,1) -> (0,1,1) -> (0,0,1)
(0,0,0) -> (0,0,1) -> (1,0,1) -> (0,0,1)
(0,0,0) -> (0,1,0) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (0,1,0) -> (0,1,1) -> (0,0,1)
(0,0,0) -> (1,0,0) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (1,0,0) -> (1,0,1) -> (0,0,1) (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..200
G. Benkart and D. Moon, A Schur-Weyl Duality Approach to Walking on Cubes, arXiv preprint arXiv:1409.8154 [math.RT], 2014 and Ann. Combin. 20 (3) (2016) 397-417.
E. Estrada and J. A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013. - _N. J. A. Sloane_, Feb 28 2013
E. Estrada and J. A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
M. Kac, Random walk and the theory of Brownian motion, Amer. Math. Monthly, 54:369-391, 1947.
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 5.
Vladimir Pletser, Congruence conditions on the number of terms in sums of consecutive squared integers equal to squared integers, arXiv:1409.7969 [math.NT], 2014.
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (10,-9).

Cf. A158303, A037314, A120437, A083234 (binomial transform), A083233 (inverse binomial transform), A054879 (recurrent walks), A125857 (walks ending on face diagonal), A054880 (walks ending on space diagonal).

[(3^(2*n+1)+1)/4: n in [0..20]]; // Vincenzo Librandi, Jun 16 2011

seq((3^(2*n+1) + 1)/4, n=0..18); # Zerinvary Lajos, Jun 16 2007

NestList[9 # - 2 &, 1, 18] (* or *)
Table[(3^(2 n + 1) + 1)/4, {n, 0, 18}] (* or *)
CoefficientList[Series[(1 - 3 x)/((1 - x) (1 - 9 x)), {x, 0, 18}], x] (* Michael De Vlieger, Aug 22 2016 *)

a(n)=3^(2*n+1)\/4 \\ Charles R Greathouse IV, Jul 02 2013

Vec((1-3*x)/((1-x)*(1-9*x)) + O(x^50)) \\ Altug Alkan, Nov 13 2015

a(n) = (3^(2*n+1)+1)/4. - Vladeta Jovovic, Dec 22 2002
a(n) = 9*a(n-1) - 2. - Matthew Vandermast, Mar 30 2003
From Paul Barry, Apr 21 2003: (Start)
G.f.: (1-3*x)/((1-x)*(1-9*x)).
E.g.f.: (3*exp(9*x) + exp(x))/4. (End)
a(n) = (-1)^n times the (i, i)-th element of M^n (for any i), where M = ((1, 1, 1, -2), (1, 1, -2, 1), (1, -2, 1, 1), (-2, 1, 1, 1)). - Simone Severini, Nov 25 2004
a(n) = Sum_{k=0..n} binomial(2*n+1, 2*k)*4^(n-k). - Paul Barry, Jan 22 2005
a(n) = A054880(n) + 1.
a(n) = A057660(3^n). - Henry Bottomley, Nov 08 2015
a(n) = Sum_{k=0..2n} (-3)^k == 1 + Sum_{k=1..n} 2*3^(2k-1). - Bob Selcoe, Aug 21 2016
a(n) = 3^(2*n+1) * a(-1-n) for all n in Z. - Michael Somos, Jul 02 2017
a(n) = 6*A002452(n) + 1. - Yuchun Ji, Aug 15 2019

Corrected by Vladeta Jovovic, Dec 22 2002

A122983 a(n) = (2 + (-1)^n + 3^n)/4.

Original entry on oeis.org

1, 1, 3, 7, 21, 61, 183, 547, 1641, 4921, 14763, 44287, 132861, 398581, 1195743, 3587227, 10761681, 32285041, 96855123, 290565367, 871696101, 2615088301, 7845264903, 23535794707, 70607384121, 211822152361, 635466457083

Offset: 0

Paul Barry, Sep 22 2006

Old definition was: "Binomial transform of aeration of A081294".
Binomial transform is A063376.
A122983 = (1,1,3,7,1,1,3,7,...) mod 10. - M. F. Hasler, Feb 25 2008
Equals row sums of triangle A158301. - Gary W. Adamson, Mar 15 2009
a(n) = the number of ternary sequences of length n where the numbers of (0's, 1's) are both even. A015518 covers the (odd, even) and (even, odd) cases, and A081251 covers (odd, odd). - Toby Gottfried, Apr 18 2010
This sequence also describes the number of moves of the k-th disk solving (non-optimally) the [RED ; NEUTRAL ; BLUE] pre-colored Magnetic Tower of Hanoi (MToH) puzzle. The sequence A183119 is the partial sums of the sequence in question (obviously describing the total number of moves associated with the specific solution algorithm). For other MToH-related sequences, Cf. A183111 - A183125.
Let B=[1,sqrt(2),0; sqrt(2),1,sqrt(2); 0,sqrt(2),1] be a 3 X 3 matrix. Then a(n)=[B^n](1,1), n=0,1,2,.... - _L. Edson Jeffery, Dec 21 2011
Also the domination number of the n-Hanoi graph. - Eric W. Weisstein, Jun 16 2017
Also the matching number of the n-Sierpinski gasket graph. - Eric W. Weisstein, Jun 17 2017
Let M = [1,1,1,0; 1,1,0,1; 1,0,1,1; 0,1,1,1], a 4 X 4 matrix. Then a(n) is the upper left entry in M^n. - Philippe Deléham, Aug 23 2020
Also the lower matching number (=independent domination number) of the n-Hanoi graph. - Eric W. Weisstein, Aug 01 2023

M. F. Hasler, Table of n, a(n) for n = 0..199.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Darleen Perez-Lavin, Peaks Sets of Classical Coxeter Groups, arXiv preprint, arXiv:1505.04479 [math.GR], 2015.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 99. Book's website
Uri Levy, The Magnetic Tower of Hanoi, arXiv:1003.0225 [math.CO], 2010.
Eric Weisstein's World of Mathematics, Domination Number.
Eric Weisstein's World of Mathematics, Hanoi Graph.
Eric Weisstein's World of Mathematics, Lower Independence Number.
Eric Weisstein's World of Mathematics, Matching Number.
Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
Index entries for linear recurrences with constant coefficients, signature (3,1,-3).

Cf. a(j+1) = A137822(2^j) and these are the record values of A137822.

Cf. A054879 (bisection), A066443 (bisection). Row sums of A158303.

A122983 := n -> ceil(3^n/4); 'A122983(n)' $ n=0..22; # M. F. Hasler, Feb 25 2008
a[ -1]:=1:a[0]:=1:a[1]:=3:for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2]-2 od: seq(a[n], n=-1..25); # Zerinvary Lajos, Apr 28 2008

CoefficientList[Series[(1 - 2 x - x^2)/((1 - x) (1 + x) (1 - 3 x)), {x, 0, 40}], x] (* Harvey P. Dale, Sep 03 2013 *)
LinearRecurrence[{3, 1, -3}, {1, 1, 3}, 40] (* Harvey P. Dale, Sep 03 2013 *)
Table[(2 + (-1)^n + 3^n)/4, {n, 0, 20}] (* Eric W. Weisstein, Jun 16 2017 *)
Table[Floor[3^n/4] + 1, {n, 0, 20}] (* Eric W. Weisstein, Jan 17 2018 *)
Floor[3^Range[0, 20]/4] + 1 (* Eric W. Weisstein, Jan 17 2018 *)

A122983(n)=3^n\4+1 \\ M. F. Hasler, Feb 25 2008

def A122983(n): return (1 if n&1 else 3)+3**n>>2 # Chai Wah Wu, Apr 12 2023

From Paul Barry, Jun 14 2007: (Start)
G.f.: (1-2*x-x^2)/((1-x)*(1+x)*(1-3*x));
a(n) = 3^n/4+(-1)^n/4+1/2;
E.g.f.: cosh(x)^2*exp(x). (End)
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3); a(0)=1, a(1)=1, a(2)=3. - Harvey P. Dale, Sep 03 2013
E.g.f.: Q(0)/2, where Q(k) = 1 + 3^k/( 2 - 2*(-1)^k/( 3^k + (-1)^k - 2*x*3^k/( 2*x + (k+1)*(-1)^k/Q(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Dec 22 2013
a(2*n) = 3*a(2*n-1); a(2*n+1) = 3*a(2*n) - 2. - Philippe Deléham, Aug 23 2020

Extended and corrected (existing Maple code) by M. F. Hasler, Feb 25 2008

Description changed to formula by Eric W. Weisstein, Jun 16 2017

A092812 Number of closed walks of length 2*n on the 4-cube.

Original entry on oeis.org

1, 4, 40, 544, 8320, 131584, 2099200, 33562624, 536903680, 8590065664, 137439477760, 2199025352704, 35184380477440, 562949986975744, 9007199388958720, 144115188612726784, 2305843011361177600

Offset: 0

Paul Barry, Mar 11 2004

With interpolated zeros this has a(n) = (6*0^n + 4^n + (-4)^n + 4*2^n + 4*(-2)^n)/16 and counts closed walks of length n at a vertex of the 4-cube. [Typo corrected by Alexander R. Povolotsky, May 26 2008]

Also, cogrowth sequence of the 16-element group C2^4. - Sean A. Irvine, Nov 10 2024

Vincenzo Librandi, Table of n, a(n) for n = 0..200
G. R. Franssens, On a number pyramid related to the binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.
Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]
L. Reyzin, Mathoverflow, Number of closed walks on an n-cube.
Index entries for linear recurrences with constant coefficients, signature (20,-64).

Essentially the same as A075878.

Cf. A026244, A081294, A054879, A121822.

[3*0^n/8+16^n/8+4^n/2: n in [0..30]]; // Vincenzo Librandi, May 31 2011

CoefficientList[Series[(1-16x+24x^2)/((1-4x)(1-16x)),{x,0,30}],x] (* or *) Join[{1},LinearRecurrence[{20,-64},{4,40},30]] (* Harvey P. Dale, Aug 23 2011 *)

G.f.: (1-16*x+24*x^2)/((1-4*x)*(1-16*x)).
a(n) = 3*0^n/8 + 16^n/8 + 4^n/2.
From Peter Bala, Nov 13 2006: (Start)
E.g.f.: cosh^4(x).
O.g.f.: 1/(1-4*1*x/(1-3*2*x/(1-2*3*x/(1-1*4*x)))) (continued fraction). (End)
(-1)^n*a(n) = Sum_{k=0..n} A086872(n,k)*(-5)^(n-k). - Philippe Deléham, Aug 17 2007
a(n) = 20*a(n-1) - 64*a(n-2); a(0) = 1, a(1) = 4, a(2) = 40. - Harvey P. Dale, Aug 23 2011
a(n) = 4*A026244(n-1), n > 0. - R. J. Mathar, Oct 24 2014
a(n) = (1/2^4)*Sum_{j = 0..4} binomial(4, j)*(4 - 2*j)^(2*n). See Reyzin link. - Peter Bala, Jun 03 2019

Title improved by Sean A. Irvine at the suggestion of Peter Bala, Jun 04 2019

A121314 Triangle T(n,k), 0 <= k <= n, read by rows given by [0, 1, 0, 0, 0, 0, ...] DELTA [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 5, 6, 1, 0, 1, 7, 15, 10, 1, 0, 1, 9, 28, 35, 15, 1, 0, 1, 11, 45, 84, 70, 21, 1, 0, 1, 13, 66, 165, 210, 126, 28, 1, 0, 1, 15, 91, 286, 495, 462, 210, 36, 1

Offset: 0

Philippe Deléham, Aug 25 2006

A054142 with first diagonal 1, 0, 0, 0, 0, 0, 0, 0, ...

Mirror image of triangle in A165253.

			Triangle begins
  1;
  0,  1;
  0,  1,  1;
  0,  1,  3,  1;
  0,  1,  5,  6,  1;
  0,  1,  7, 15, 10,  1;
  0,  1,  9, 28, 35, 15,  1;
  0,  1, 11, 45, 84, 70, 21,  1;

Alois P. Heinz, Rows n = 0..140, flattened
F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

Cf. A054142, A165253.

T(0,0)=1; T(n,0)=0 for n > 0; T(n+1,k+1) = binomial(2*n-k,k)for n >= 0 and k >= 0.
Sum_{k=0..n} T(n,k)*x^k = A001519(n), A047849(n), A165310(n), A165311(n), A165312(n), A165314(n), A165322(n), A165323(n), A165324(n) for x = 1,2,3,4,5,6,7,8,9 respectively.
Sum_{k=0..n} 2^k*T(n,k) = (4^n+2)/3.
Sum_{k=0..n} 2^(n-k)*T(n,k) = A001835(n).
Sum_{k=0..n} 3^k*4^(n-k)*T(n,k) = A054879(n). - Philippe Deléham, Aug 26 2006
Sum_{k=0..n} T(n,k)*(-1)^k*2^(3n-2k) = A143126(n). - Philippe Deléham, Oct 31 2008
Sum_{k=0..n} T(n,k)*(-1)^k*3^(n-k) = A138340(n)/4^n. - Philippe Deléham, Nov 01 2008
G.f.: (1-(y+1)*x)/(1-(2y+1)*x+y^2*x^2). - Philippe Deléham, Nov 01 2011
T(n,k) = T(n-1,k) + 2*T(n-1,k-1) - T(n-2,k-2), T(0,0) = T(1,1) = 1, T(1,0) = 0. - Philippe Deléham, Feb 19 2012

A086872 Triangle T(n, k) read by rows; given by [1, 2, 3, 4, 5, 6, ..] DELTA [1, 4, 9, 16, 25, 36, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 1, 1, 3, 8, 5, 15, 75, 121, 61, 105, 840, 2478, 3128, 1385, 945, 11025, 51030, 115350, 124921, 50521, 10395, 166320, 1105335, 3859680, 7365633, 7158128, 2702765

Offset: 0

Philippe Deléham, Aug 20 2003, Aug 17 2007

			Triangle begins:
1;
1, 1;
3, 8, 5;
15, 75, 121, 61;
105, 840, 2478, 3128, 1385;
945, 11025, 51030, 115350, 124921, 50521;
10395, 166320, 1105335, 3859680, 7365633, 7158128, 2702765 ; ...

Alois P. Heinz, Rows n = 0..140, flattened

Cf. A000182 (row sums), A000364 (first diagonal), A001147 (first column), A084938, A261065 (2nd column).

Sum( k>=0, T(n, k)*(-1)^k ) = 0; if n>0.
Sum( k>=0, T(n, k)*(-1/2)^k ) = (1/2)^n.
Sum_{k, 0<=k<=n}T(n,k)*x^(n-k) = (-1)^n*A121822(n), (-1)^n*A092812(n), (-1)^n*A054879(n), A009117(n), A033999(n), A000007(n), A000364(n), A000182(n+1) for x = -6, -5, -4, -3, -2, -1, 0, 1 respectively .

A121822 Number of closed walks of length 2*n on the 5-cube.

Original entry on oeis.org

1, 5, 65, 1205, 26465, 628805, 15424865, 382964405, 9550195265, 238539648005, 5961554097665, 149021418519605, 3725378557692065, 93133051794619205, 2328313585536338465, 58207725254446186805, 1455192101905494196865

Offset: 0

Philippe Deléham, Aug 27 2006

G. C. Greubel, Table of n, a(n) for n = 0..700
G. R. Franssens, On a number pyramid related to the binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.
L. Reyzin, Mathoverflow, Number of closed walks on an n-cube
Index entries for linear recurrences with constant coefficients, signature (35,-259,225).

Cf. A054879, A081294, A092812.

List([0..20], n-> (25^n +5*9^n +10)/16); # G. C. Greubel, Jun 07 2019

[(25^n +5*9^n +10)/16: n in [0..20]]; // G. C. Greubel, Jun 07 2019

Table[(25^n +5*9^n +10)/16, {n,0,20}] (* G. C. Greubel, Jun 07 2019 *)

a(n)=(25^n+5*9^n+10)>>4 \\ Charles R Greathouse IV, Jan 17 2012

[(25^n +5*9^n +10)/16 for n in (0..20)] # G. C. Greubel, Jun 07 2019

a(n) = (25^n + 5*9^n + 10)/16.
G.f.: (1 - 30*x + 149*x^2)/(1 - 35*x + 259*x^2 - 225*x^3).
From Peter Bala, Nov 13 2006: (Start)
E.g.f.: cosh^5(x).
O.g.f.: 1/(1-5*1x/(1-4*2x/(1-3*3x/(1-2*4x/(1-1*5x))))) (continued fraction). (End)
(-1)^n*a(n) = Sum_{k=0..n} A086872(n,k)*(-6)^(n-k). - Philippe Deléham, Aug 17 2007
a(n) = (1/2^5)*Sum_{j = 0..5} binomial(5,j)*(5 - 2*j)^(2*n). See Reyzin link. - Peter Bala, Jun 03 2019

Corrected by T. D. Noe, Nov 07 2006

A106285 Number of orbits of the 3-step recursion mod n.

Original entry on oeis.org

1, 4, 3, 12, 5, 12, 9, 44, 21, 20, 25, 36, 15, 66, 15, 172, 53, 84, 21, 60, 27, 144, 23, 132, 105, 116, 183, 482, 177, 60, 91, 684, 75, 420, 45, 252, 109, 162, 45, 220, 125, 198, 265, 520, 105, 92, 2259, 516, 359, 420, 159, 884, 2867, 732, 125, 3714, 63, 1408, 59, 180

Offset: 1

T. D. Noe, May 02 2005

nonn

Consider the 3-step recursion x(k)=x(k-1)+x(k-2)+x(k-3) mod n. For any of the n^3 initial conditions x(1), x(2) and x(3) in Zn, the recursion has a finite period. Each of these n^3 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths (A106288) for each n. For instance, the orbits mod 8 have lengths of 1, 2, 4, 8, 16. Interestingly, for n=2^k and n=3^k, the number of orbits appear to be A039301 and A054879, respectively.

			Orbits for n=2: {(0,0,0)}, {(1,1,1)}, {(0,1,0), (1,0,1)} and {(0,0,1), (0,1,1), (1,1,0), (1,0,0)}

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A015134 (orbits of Fibonacci sequences), A106286 (orbits of 4-step sequences), A106287 (orbits of 5-step sequences), A106288 (number of different orbit lengths), A106307 (n producing a simple orbit structure).

A270369 Expansion of g.f. (1-7x)/(1-9x).

Original entry on oeis.org

1, 2, 18, 162, 1458, 13122, 118098, 1062882, 9565938, 86093442, 774840978, 6973568802, 62762119218, 564859072962, 5083731656658, 45753584909922, 411782264189298, 3706040377703682, 33354363399333138, 300189270593998242, 2701703435345984178, 24315330918113857602, 218837978263024718418

Offset: 0

Colin Barker, Mar 18 2016

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (9).

Cf. A001019 (powers of 9), A054879 (partial sums), A132025.

Cf. similar sequences with g.f. (1-k*x)/(1-9*x) and k=0..8: A001019 (k=0; k=8 gives two initial 1's ), A055275 (k=1), A270472 (k=2), A092810 (k=3), A067403 (k=4), A270473 (k=5), A102518 (k=6), this sequence (k=7).

CoefficientList[Series[(1-7x)/(1-9x),{x,0,20}],x] (* or *) Join[ {1}, NestList[9#&,2,20]] (* Harvey P. Dale, Oct 15 2017 *)

PARI
```
Vec((1-7*x)/(1-9*x) + O(x^30))
```

G.f.: (1-7*x)/(1-9*x).
a(n) = 9*a(n-1) for n>1.
a(n) = 2*9^(n-1) for n>0.
From Amiram Eldar, May 08 2023: (Start)
Sum_{n>=0} 1/a(n) = 25/16.
Sum_{n>=0} (-1)^n/a(n) = 11/20.
Product_{n>=1} (1 - 1/a(n)) = A132025. (End)
E.g.f.: (2*exp(9*x) + 7)/9. - Elmo R. Oliveira, Mar 25 2025

A286899 Array read by antidiagonals: A(n, L) is the number of closed walks of length 2L along the edges of an n-cube based at a vertex, for n >= 1 and L >= 1.

Original entry on oeis.org

1, 1, 2, 1, 8, 3, 1, 32, 21, 4, 1, 128, 183, 40, 5, 1, 512, 1641, 544, 65, 6, 1, 2048, 14763, 8320, 1205, 96, 7, 1, 8192, 132861, 131584, 26465, 2256, 133, 8, 1, 32768, 1195743, 2099200, 628805, 64896, 3787, 176, 9, 1, 131072, 10761681, 33562624, 15424865

Offset: 1

Melvin Peralta, May 15 2017

			A(2, 2) = 8 because at each vertex of a 2-cube (i.e., a square), there are 8 closed walks of length 2(2) = 4.
A(1, k) = 1 because at the vertex of a 1-cube, there is 1 closed walk of any length 2*k.
Array A(n, L) begins:
   1         1         1         1         1         1 ...
   2         8        32       128       512      2048 ...
   3        21       183      1641     14763    132861 ...
   4        40       544      8320    131584   2099200 ...
   5        65      1205     26465    628805  15424865 ...
   6        96      2256     64896   2086656  71172096 ...
   7       133      3787    134953   5501167 243147373 ...

R. P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Springer, 2013.

Melvin Peralta, Table of n, a(n) for n = 1..120

Cf. A054879, A092812, A121822.

A286899 := proc(n,L)
    add(binomial(n,i)*(n-2*i)^L, i=0..n) ;
    %/2^n ;
end proc:
for n from 1 to 7 do
    for L from 2 to 12 by 2 do
        printf("%9d ",A286899(n,L)) ;
    end do:
    printf("\n") ;
end do: # R. J. Mathar, May 22 2017

f[n_, l_] := 1/2^n*Sum[Binomial[n, i]*(n - 2 i)^l, {i, 0, n}];
Table[f[n - l + 1, 2 l], {n, 1, 15}, {l, n, 1, -1}] // Flatten

A(n, L) = (1/2^n)*Sum_{i=0..n} binomial(n, i)*(n - 2*i)^(2*L). (Corrected by Peter Luschny, Jul 07 2019.)

cp's OEIS Frontend

A081294 Expansion of (1-2*x)/(1-4*x).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

PARI

Formula

A066443 Number of distinct paths of length 2n+1 along edges of a unit cube between two fixed adjacent vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A122983 a(n) = (2 + (-1)^n + 3^n)/4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A092812 Number of closed walks of length 2*n on the 4-cube.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A121314 Triangle T(n,k), 0 <= k <= n, read by rows given by [0, 1, 0, 0, 0, 0, ...] DELTA [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A086872 Triangle T(n, k) read by rows; given by [1, 2, 3, 4, 5, 6, ..] DELTA [1, 4, 9, 16, 25, 36, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A121822 Number of closed walks of length 2*n on the 5-cube.

Views

Author

A081294 Expansion of (1-2x)/(1-4x).

A270369 Expansion of g.f. (1-7x)/(1-9x).