A005023 -id:A005023 - cp's OEIS frontend

A094256 Expansion of x / ( (x-1)(x^3 - 9x^2 + 6*x - 1) ).

1, 7, 34, 143, 560, 2108, 7752, 28101, 100947, 360526, 1282735, 4552624, 16131656, 57099056, 201962057, 714012495, 2523515514, 8916942687, 31504028992, 111295205284, 393151913464, 1388758662221, 4905479957435, 17327203698086, 61202661233823, 216176614077600

Offset: 1

Gary W. Adamson, Apr 25 2004

Previous name was: Let M = the 4 X 4 matrix [0 1 0 0 / 0 0 1 0 / 0 0 0 1 / -1 10 -15 7]. Perform M^n * [1 0 0 0] = [p q r s]. Then a(n-3), a(n-2), a(n-1), a(n) = -p, -q, -r, -s respectively.
a(n)/a(n-1) tends to 3.53208888624... = 4*cos^2(Pi/9), which is an eigenvalue of the matrix and a root of the polynomial x^4 - 6x^3 + 15x^2 -10x + 1 = 0 (having roots 4*cos^2(r*Pi/9), with r = 1,2,3,4).
Number of (s(0), s(1), ..., s(2n+4)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+4, s(0) = 1, s(2n+4) = 7. - Herbert Kociemba, Jun 13 2004
From Wolfdieter Lang, Mar 27 2020: (Start)
This sequence, with offset -5, starting with -85, -10, -1, 0, 0, 0, 1, 7, ... appears in the formula for the n-th power of the 4 X 4 tridiagonal matrix given in A332602 as M_4 = matrix([1,1,0,0], [1,2,1,0], [0,1,2,1], [0,0,1,2]): (M_4)^n = a(n-2)*(M_4)^3 + b(n)*(M_4)^2 + c(n)*M_4 - a(n-3)*1_4, for n >= 0, with the 4 X 4 unit Matrix 1_4, b(n) = -15*a(n-3) + 10*a(n-4) - a(n-5), and c(n) = 10*a(n-3) - a(n-4). Proof from the characteristc polynomial of M_4 (see a comment in A332602) and the Cayley-Hamilton theorem.
From the proof that A094829(n+3)/A094829(n+2) -> rho(9)^2 = A332438 for n-> infinitiy, with rho(9) = 2*cos(Pi/9) = A332437 (see a comment in A094829), and a formula given below the same limit is obtained for a(n+1)/a(n) for n -> infinity, as stated in a comment above. (End)

			a(2), a(3), a(4), a(5) = 7, 34, 143, 560, since M^5 * [1 0 0 0] = [ -7 -34 -143 -560].
Cayley-Hamilton: (M_4)^5 = a(3)*(M_4)^3 + b(5)*(M_4)^2 + c(5)*M_4 - a(2)*1_4 = 34*(M_4)^3 - 95*(M_4)^2 + 69*M_4 - 7*1_4. - _Wolfdieter Lang_, Mar 27 2020

C. V. Durell and A. Robson, "Advanced Trigonometry", Dover 2003, p. 216.

Michael De Vlieger, Table of n, a(n) for n = 1..1824
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Index entries for linear recurrences with constant coefficients, signature (7,-15,10,-1).

a(n) = A005023(n-1), n > 1. - R. J. Mathar, Sep 05 2008

Cf. A080938, A094829, A332602, A332437, A332438.

I:=[1,7,34,143]; [n le 4 select I[n] else 7*Self(n-1) - 15*Self(n-2) + 10*Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jul 25 2015

Table[ (MatrixPower[{{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {-1, 10, -15, 7}}, n].{-1, 0, 0, 0})[[4]], {n, 24}] (* Robert G. Wilson v, Apr 28 2004 *)
LinearRecurrence[{7, -15, 10, -1}, {1, 7, 34, 143}, 40] (* Vincenzo Librandi, Jul 25 2015 *)

Vec(x / ( (x-1)*(x^3-9*x^2+6*x-1) ) + O(x^30)) \\ Michel Marcus, Jul 25 2015

From Herbert Kociemba, Jun 13 2004: (Start)
a(n) = (2/9)*Sum_{r=1..8} sin(r*Pi/9)*sin(7*r*Pi/9)*(2*cos(r*Pi/9))^(2n+4).
a(n) = 7*a(n-1) - 15*a(n-2) + 10*a(n-3) - a(n-4).
G.f.: x / ( (x-1)*(x^3 - 9*x^2 + 6*x - 1) ). (End)
3*a(n) = 1 - A094829(n+2) + 8*A094829(n+1) - A094829(n). - R. J. Mathar, Jun 29 2012 [offset corrected, and A094829(1) = 0. - Wolfdieter Lang, Mar 27 2020]
a(n) = (1/3)*(1 + 2*A094829(n+1) + 8*A094829(n) - A094829(n-1)), for n >= 1, with A094829(1) and A094829(0) = 0. - Wolfdieter Lang, Mar 27 2020

More terms from Robert G. Wilson v, Apr 28 2004
a(25)-a(26) from Vincenzo Librandi, Jul 25 2015
New name (using g.f. from Herbert Kociemba) from Joerg Arndt, Jul 25 2015

A188843 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally or vertically.

Original entry on oeis.org

2, 4, 3, 8, 8, 4, 16, 21, 13, 5, 32, 55, 40, 19, 6, 64, 144, 121, 66, 26, 7, 128, 377, 364, 221, 100, 34, 8, 256, 987, 1093, 728, 364, 143, 43, 9, 512, 2584, 3280, 2380, 1288, 560, 196, 53, 10, 1024, 6765, 9841, 7753, 4488, 2108, 820, 260, 64, 11, 2048, 17711, 29524

Offset: 1

R. H. Hardin, Apr 12 2011

Table starts
4   8   16   32    64    128    256     512     1024     2048      4096
8  21   55  144   377    987   2584    6765    17711    46368    121393
13  40  121  364  1093   3280   9841   29524    88573   265720    797161
19  66  221  728  2380   7753  25213   81927   266110   864201   2806272
26 100  364 1288  4488  15504  53296  182688   625184  2137408   7303360
34 143  560 2108  7752  28101 100947  360526  1282735  4552624  16131656
43 196  820 3264 12597  47652 177859  657800  2417416  8844448  32256553
53 260 1156 4845 19551  76912 297275 1134705  4292145 16128061  60304951
64 336 1581 6954 29260 119416 476905 1874730  7283640 28048800 107286661
76 425 2109 9709 42504 179630 740025 2991495 11920740 46981740 183579396

			Some solutions for 5 X 3:
  0 0 1    1 1 0    1 1 1    0 1 0    1 1 0    1 1 0    1 1 1
  0 0 0    1 0 0    1 1 0    0 0 0    1 1 0    1 1 0    1 1 1
  0 0 0    0 0 0    1 1 0    0 0 0    1 0 0    1 1 0    0 1 1
  0 0 0    0 0 0    1 1 0    0 0 0    1 0 0    1 0 0    0 0 0
  0 0 0    0 0 0    0 0 0    0 0 0    0 0 0    0 0 0    0 0 0

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

Diagonal is A143388.
Column 2 is A034856(n+1).
Column 3 is A137742(n+1).
Row 2 is A001906(n+1).
Row 3 is A003462(n+1).
Row 4 is A005021.
Row 5 is A005022.
Row 6 is A005023.
Row 7 is A005024.
Row 8 is A005025.

Row recurrence
Empirical: T(n,k) = Sum_{i=1..floor((n+2)/2)} binomial(n+2-i,i)*T(n,k-i)*(-1)^(i-1).
E.g.,
empirical: T(1,k) = 2*T(1,k-1),
empirical: T(2,k) = 3*T(2,k-1) -    T(2,k-2),
empirical: T(3,k) = 4*T(3,k-1) -  3*T(3,k-2),
empirical: T(4,k) = 5*T(4,k-1) -  6*T(4,k-2) +    T(4,k-3),
empirical: T(5,k) = 6*T(5,k-1) - 10*T(5,k-2) +  4*T(5,k-3),
empirical: T(6,k) = 7*T(6,k-1) - 15*T(6,k-2) + 10*T(6,k-3) -    T(6,k-4),
empirical: T(7,k) = 8*T(7,k-1) - 21*T(7,k-2) + 20*T(7,k-3) -  5*T(7,k-4),
empirical: T(8,k) = 9*T(8,k-1) - 28*T(8,k-2) + 35*T(8,k-3) - 15*T(8,k-4) + T(8,k-5).
Columns are polynomials for n > k-3.
Empirical: T(n,1) = n + 1.
Empirical: T(n,2) = (1/2)*n^2 + (5/2)*n + 1.
Empirical: T(n,3) = (1/6)*n^3 + 2*n^2 + (35/6)*n.
Empirical: T(n,4) = (1/24)*n^4 + (11/12)*n^3 + (155/24)*n^2 + (163/12)*n - 6 for n > 1.
Empirical: T(n,5) = (1/120)*n^5 + (7/24)*n^4 + (89/24)*n^3 + (473/24)*n^2 + (1877/60)*n - 33 for n > 2.
Empirical: T(n,6) = (1/720)*n^6 + (17/240)*n^5 + (203/144)*n^4 + (647/48)*n^3 + (2659/45)*n^2 + (1379/20)*n - 143 for n > 3.
Empirical: T(n,7) = (1/5040)*n^7 + (1/72)*n^6 + (143/360)*n^5 + (53/9)*n^4 + (33667/720)*n^3 + (12679/72)*n^2 + (9439/70)*n - 572 for n > 4.
Empirical: T(n,8) = (1/40320)*n^8 + (23/10080)*n^7 + (17/192)*n^6 + (269/144)*n^5 + (43949/1920)*n^4 + (228401/1440)*n^3 + (1054411/2016)*n^2 + (9941/56)*n - 2210 for n > 5.

A005024 Number of walks of length 2n+8 in the path graph P_9 from one end to the other.

Original entry on oeis.org

8, 43, 196, 820, 3264, 12597, 47652, 177859, 657800, 2417416, 8844448, 32256553, 117378336, 426440955, 1547491404, 5610955132, 20332248992, 73645557469, 266668876540, 965384509651, 3494279574288, 12646311635088, 45764967830976

Offset: 1

N. J. A. Sloane

W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
C. J. Everett, P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45.
C. J. Everett, P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45. [Annotated scanned copy]
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
Index entries for linear recurrences with constant coefficients, signature (8,-21,20,-5).

Cf. A005023. Truncated version of A094865.

I:=[8, 43, 196, 820]; [n le 4 select I[n] else 8*Self(n-1)-21*Self(n-2)+20*Self(n-3)-5*Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 08 2013

a:=k->sum(binomial(8+2*k,10*j+k-2),j=ceil((2-k)/10)..floor((10+k)/10))-sum(binomial(8+2*k,10*j+k-1),j=ceil((1-k)/10)..floor((9+k)/10)): seq(a(k),k=1..28);
A005024:=-(-8+21*z-20*z**2+5*z**3)/(5*z**2-5*z+1)/(z**2-3*z+1); # conjectured by Simon Plouffe in his 1992 dissertation

CoefficientList[Series[(-5 z^3 + 20 z^2 - 21 z + 8)/((z^2 - 3 z + 1) (5 z^2 - 5 z + 1)), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 27 2011 *)
CoefficientList[Series[(1 / x) (1 / (1 - 8 x + 21 x^2 - 20 x^3 + 5 x^4) - 1), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 08 2013 *)

x='x+O('x^66); Vec(-1+1/((1-3*x+x^2)*(1-5*x+5*x^2))) \\ Joerg Arndt, May 01 2013

From Emeric Deutsch, Apr 02 2004: (Start)
G.f. (assuming a(0)=1): 1/(1 - 8x + 21x^2 - 20x^3 + 5x^4) - 1.
a(n) = 8*a(n-1) - 21*a(n-2) + 20*a(n-3) - 5*a(n-4). (End)
a(k) = sum(binomial(8+2k, 10j+k-2)-binomial(8+2k, 10j+k-1), j=-infinity..infinity) (a finite sum).

Better definition from Emeric Deutsch, Apr 02 2004

cp's OEIS Frontend

A094256 Expansion of x / ( (x-1)(x^3 - 9x^2 + 6*x - 1) ).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A188843 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally or vertically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A005024 Number of walks of length 2n+8 in the path graph P_9 from one end to the other.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

cp's OEIS Frontend

A094256 Expansion of x / ( (x-1)*(x^3 - 9*x^2 + 6*x - 1) ).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A188843 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally or vertically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A005024 Number of walks of length 2n+8 in the path graph P_9 from one end to the other.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A094256 Expansion of x / ( (x-1)(x^3 - 9x^2 + 6*x - 1) ).