A016209 -id:A016209 - cp's OEIS frontend

A007798 Expected number of random moves in Tower of Hanoi problem with n disks starting with a randomly chosen position and ending at a position with all disks on the same peg.

0, 0, 2, 18, 116, 660, 3542, 18438, 94376, 478440, 2411882, 12118458, 60769436, 304378620, 1523487422, 7622220078, 38125449296, 190670293200, 953480606162, 4767790451298, 23840114517956, 119204059374180, 596030757224102, 2980185167180118, 14901019979079416

Offset: 0

David G. Poole (dpoole(AT)trentu.ca)

All 3^n possible starting positions are chosen with equal probability.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
M. A. Alekseyev and T. Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 65-79. ISBN 978-0-691-16403-8
Index entries for linear recurrences with constant coefficients, signature (9,-23,15).
Index entries for sequences related to Towers of Hanoi

Partial sums of A005058.

Cf. A134939.

[(5^n-2*3^n+1)/4: n in [0..25]]; // Vincenzo Librandi, Oct 11 2011

seq( (1 -2*3^n +5^n)/4, n=0..25); # G. C. Greubel, Mar 05 2020

Table[(1 -2*3^n +5^n)/4, {n,0,25}] (* G. C. Greubel, Mar 05 2020 *)

concat([0,0], Vec(-2*x^2/((x-1)*(3*x-1)*(5*x-1)) + O(x^30))) \\ Colin Barker, Sep 17 2014

[(1 -2*3^n +5^n)/4 for n in (0..25)] # G. C. Greubel, Mar 05 2020

For n>1, a(n) = 8*a(n-1) - 15*a(n-2) + 2 = 2*A016209(n-2). - Henry Bottomley, Jun 06 2000
a(n) = (5^n - 2*3^n + 1) / 4. - Henry Bottomley, Jun 06 2000, proved by Max Alekseyev, Feb 04 2008
From Colin Barker, Sep 17 2014: (Start)
a(n) = 9*a(n-1) - 23*a(n-2) + 15*a(n-3).
G.f.: 2*x^2/((1-x)*(1-3*x)*(1-5*x)). (End)
E.g.f.: (exp(x) - 2*exp(3*x) + exp(5*x))/4. - G. C. Greubel, Mar 05 2020

More precise definition and more terms from Max Alekseyev, Feb 04 2008

a(0)=0 prepended by Max Alekseyev, Sep 08 2014

A016234 Expansion of 1/((1-x) * (1-5x) (1-9*x)).

Original entry on oeis.org

1, 15, 166, 1650, 15631, 144585, 1320796, 11984820, 108351661, 977606355, 8810664226, 79357013190, 714518294491, 6432190529325, 57897344158456, 521114244398760, 4690218934452121, 42212924084385495, 379921085131051486, 3419313608037373530, 30773941681625912551

Offset: 0

N. J. A. Sloane

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (15, -59, 45).

Cf. A000012, A003463.
Cf. A016209, A016223, A016247.
Cf. A016307, A018054.

CoefficientList[Series[1/((1-x)(1-5x)(1-9x)),{x,0,30}],x] (* or *) LinearRecurrence[{15,-59,45},{1,15,166},30] (* Harvey P. Dale, Oct 16 2014 *)

Vec(1/((1-x)*(1-5*x)*(1-9*x))+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

a(n) = (9^(n+2) - 2*5^(n+2) + 1)/32; \\ Joerg Arndt, Aug 13 2013

a(0)=1, a(1)=15, a(n) = 14*a(n-1) - 45*a(n-2) + 1. - Vincenzo Librandi, Feb 10 2011
a(n) = (9^(n+2) - 2*5^(n+2) + 1)/32. - Yahia Kahloune, Aug 13 2013
a(0)=1, a(1)=15, a(2)=166, a(n) = 15*a(n-1) - 59*a(n-2) + 45*a(n-3). - Harvey P. Dale, Oct 16 2014
O.g.f.: see the name.
E.g.f.: (d^2/dx^2) (exp(x)*((exp(4*x) - 1)^2)/(4^2*2!)) = exp(x)*(1 - 50*exp(4*x) + 81*exp(8*x))/32.
From Seiichi Manyama, May 05 2025: (Start)
a(n) = Sum_{k=0..n} 4^k * binomial(n+2,k+2) * Stirling2(k+2,2).
a(n) = Sum_{k=0..n} (-4)^k * 9^(n-k) * binomial(n+2,k+2) * Stirling2(k+2,2). (End)

A021424 Expansion of 1/((1-x)(1-3x)(1-5x)(1-7x)).

Original entry on oeis.org

1, 16, 170, 1520, 12411, 96096, 719860, 5278240, 38153621, 273134576, 1942326750, 13748476560, 97001079631, 682818667456, 4798793396840, 33686888924480, 236284962774441, 1656378634646736, 11606570499786130

Offset: 0

N. J. A. Sloane

a(n) is h^{(4)}n, the complete homogeneous symmetric function of the four symbols s_j = 1 + 2*j, j = 0..3, of degree n >= 1, with h^{(4)}_0 = 1. See an example below. Thus it is the (dimensionless) volume of all multichoose(4, n) = binomial(n+3, 3) polytopes of dimension n with side lengths from the set {1, 3, 5, 7}. - _Wolfdieter Lang, May 26 2017

			a(2) = h^{(4)}_2 = (1^2 + 3^2 + 5^2 + 7^2) +  (1^1*(3^1 + 5^1 + 7^1) + 3^1*(5^1 + 7^1) + 5^1*7^1)  = 84 + 86  = 120. - _Wolfdieter Lang_, May 26 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (16,-86,176,-105).

Cf. A039755 (column k=3), A016209.

m:=25; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1/((1-x)*(1-3*x)*(1-5*x)*(1-7*x)))); // Vincenzo Librandi, Jul 09 2013

I:=[1, 16, 170, 1520]; [n le 4 select I[n] else 16*Self(n-1)-86*Self(n-2)+176*Self(n-3)-105*Self(n-4): n in [1..25]]; // Vincenzo Librandi, Jul 09 2013

Table[(7^n - 3*5^n + 3^(n + 1) - 1)/48, {n, 3, 60}]
CoefficientList[Series[1 / ((1 - x) (1 - 3 x) (1 - 5 x) (1 - 7 x)), {x, 0, 20}], x] (* Vincenzo Librandi, Jul 09 2013 *)
LinearRecurrence[{16,-86,176,-105},{1,16,170,1520},30] (* Harvey P. Dale, May 26 2014 *)

x='x+O('x^99); Vec(1/((1-x)*(1-3*x)*(1-5*x)*(1-7*x))) \\ Altug Alkan, Oct 11 2017

a(n) = (7^n- 3*5^n+ 3^(n+1)-1)/48. - Victor Adamchik (adamchik(AT)cs.cmu.edu), Jul 21 2001
a(n) = 12*a(n-1) - 35*a(n-2) + (3^n-1)/2 with a(0)=1, a(1)=16. - Vincenzo Librandi, Jul 09 2013
a(n) = 16*a(n-1) - 86*a(n-2) + 176*a(n-3) - 105*a(n-4), with a(0)=1, a(1)=16, a(2)=170, a(3)=1520. - Vincenzo Librandi, Jul 09 2013
G.f.: 1/((1-x)*(1-3*x)*(1-5*x)*(1-7*x)). See the name.
E.g.f.: (343*exp(7*x) - 375*exp(5*x) + 81*exp(3*x) - exp(x))/48, from the e.g.f. of the fourth column (k=3) of A039755. - Wolfdieter Lang, May 26 2017

A200859 a(n) = 2a(n-1)+3a(n-2)+5^n for n>1, a(0)=-2, a(1)=1.

Original entry on oeis.org

-2, 1, 21, 170, 1028, 5691, 30091, 155380, 791658, 4002581, 20145761, 101127390, 506832688, 2537750671, 12699515031, 63529860200, 317746156118, 1589021345961, 7945978425901, 39732507217810, 198670381353948, 993375442564451, 4966947820206371, 24834950923184220

Offset: 0

Bruno Berselli, Nov 23 2011

B. Satyanarayana and K. S. Prasad, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd. (Eastern Economy Edition), 2009, p. 81 (3.1;4)

Bruno Berselli, Table of n, a(n) for n = 0..1000.
Index entries for linear recurrences with constant coefficients, signature (7,-7,-15).

Cf. A016209, A200864.

[n le 2 select 3*n-5 else 2*Self(n-1)+3*Self(n-2)+5^(n-1): n in [1..24]];

A200859:=n->(50*5^n-81*3^n-17*(-1)^n)/24; seq(A200859(n), n=0..30); # Wesley Ivan Hurt, Dec 26 2013

LinearRecurrence[{7,-7,-15}, {-2,1,21}, 24]
nxt[{n_,a_,b_}]:={n+1,b,2b+3a+5^(n+1)}; NestList[nxt,{1,-2,1},30][[All,2]] (* Harvey P. Dale, Dec 28 2021 *)

makelist(coeff(taylor(-(2-15*x)/((1+x)*(1-3*x)*(1-5*x)), x, 0, n), x, n), n, 0, 23);

for(n=0, 23, print1((50*5^n-81*3^n-17*(-1)^n)/24", "));

def lr(a0, a1, a2, a3, a4, a5):
    x, y, z = a0, a1, a2
    while True:
       yield x
       x, y, z = y, z, a5*x+a4*y+a3*z
A200859 = lr(-2, 1, 21, 7, -7, -15)
print([next(A200859) for n in range(24)]) # Bruno Berselli, May 09 2014

G.f.: -(2-15*x)/((1+x)*(1-3*x)*(1-5*x)).
a(n) = 7*a(n-1)-7*a(n-1)-15*a(n-3) for n>2, a(0)=-2, a(1)=1, a(2)=21.
a(n) = (50*5^n-81*3^n-17*(-1)^n)/24.

A200864 Expansion of 1/((1+x)(1-3x)(1-5x)).

Original entry on oeis.org

1, 7, 42, 230, 1211, 6237, 31732, 160300, 806421, 4046867, 20278622, 101525970, 508028431, 2541337897, 12710276712, 63562145240, 317843011241, 1589311911327, 7946850122002, 39735122306110, 198678226618851, 993398978359157, 4967018427590492, 24835162745336580

Offset: 0

Bruno Berselli, Nov 23 2011

Bruno Berselli, Table of n, a(n) for n = 0..1000.
Index entries for linear recurrences with constant coefficients, signature (7,-7,-15).

Cf. A016209, A200859.

m:=24; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1/((1+x)*(1-3*x)*(1-5*x))));

CoefficientList[Series[1/((1+x)(1-3x)(1-5x)), {x, 0, 24}], x]
LinearRecurrence[{7,-7,-15},{1,7,42},30] (* Harvey P. Dale, May 26 2015 *)

makelist(coeff(taylor(1/((1+x)*(1-3*x)*(1-5*x)), x, 0, n), x, n), n, 0, 23);

PARI
```
Vec(1/((1+x)*(1-3*x)*(1-5*x))+O(x^24))
```

G.f.: 1/((1+x)*(1-3*x)*(1-5*x)).
a(n) = (50*5^n-27*3^n+(-1)^n)/24.
a(n) = 2*a(n-1)+3*a(n-2)+5^n for n>1, a(0)=1, a(1)=7.
a(n) = 7*a(n-1)-7*a(n-2)-15*a(n-3) for n>2, a(0)=1, a(1)=7, a(2)=42.
a(n+1)+a(n) = A005059(n+2).
a(n+2)-a(n) = A081625(n+2).

A016247 Expansion of 1/((1-x) * (1-6x) (1-11*x)).

Original entry on oeis.org

1, 18, 241, 2910, 33565, 378546, 4219993, 46755846, 516329845, 5691721530, 62681496241, 689931815118, 7591862105101, 83526155988930, 918881752875145, 10108263503608086, 111194283871577893, 1223157434578690506, 13454853652313597665, 148004121407137586910, 1628049722868641531581

Offset: 0

N. J. A. Sloane

nonn

Index entries for linear recurrences with constant coefficients, signature (18, -83, 66).

Cf. A016209, A016223, A016234.

CoefficientList[Series[1/((1-x)(1-6x)(1-11x)),{x,0,30}],x] (* or *) LinearRecurrence[{18,-83,66},{1,18,241},30] (* Harvey P. Dale, Sep 23 2012 *)

a(n) = (11^(n+2) - 2*6^(n+2) + 1)/50; \\ Joerg Arndt, Aug 13 2013

a(0)=1, a(1)=18, a(n)=17*a(n-1)-66*a(n-2)+1. - Vincenzo Librandi, Feb 10 2011
a(0)=1, a(1)=18, a(2)=241, a(n)=18*a(n-1)-83*a(n-2)+66*a(n-3). - Harvey P. Dale, Sep 23 2012
a(n) = (11^(n+2) - 2*6^(n+2) + 1)/50. [Yahia Kahloune, Aug 13 2013]
From Seiichi Manyama, May 05 2025: (Start)
a(n) = Sum_{k=0..n} 5^k * binomial(n+2,k+2) * Stirling2(k+2,2).
a(n) = Sum_{k=0..n} (-5)^k * 11^(n-k) * binomial(n+2,k+2) * Stirling2(k+2,2). (End)

A286719 Column k=4 of triangle A039755, Sheffer(exp(x), (exp(2*x) - 1)/2).

Original entry on oeis.org

1, 25, 395, 5075, 58086, 618870, 6289690, 61885450, 595122671, 5629238615, 52605474285, 487197745125, 4481780785756, 41018845739260, 373968405050180, 3399402534376100, 30830907772159341, 279134548584080805, 2523817507756513375, 22795663165336810375, 205730405672107235426, 1855561201430080303250, 16727971116048518559870, 150747219419372400319950, 1358093516662781192486011

Offset: 0

Wolfdieter Lang, May 26 2017

For a combinatorial interpretation following from the g.f. and the a(n) = h^{(5)}_n formula below see A039755.

			a(2) =  h^{(5)}_2 = 1^2 + 3^2 + 5^2 + 7^2 + 9^2 + 1^1*(3^1 + 5^1 + 7^1 + 9^1) + 3^1*(5^1 + 7^1 + 9^1) + 5^1*(7^1 + 9^1) + 7^1*9^1 = 165 + 230 = 395. The multichoose(5, 2) = binomial(6, 2) = 15 polytopes are five squares and ten rectangles of total area 165 and 230, respectively.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (25,-230,950,-1689,945).

Cf. A003462 (k=1), A016209 (k=2), A021424 (k=3), A039755.

Vec(1 / ((1 - x)*(1 - 3*x)*(1 - 5*x)*(1 - 7*x)*(1 - 9*x)) + O(x^40)) \\ Colin Barker, Dec 23 2017

a(n) =  A039755(n+4,4),  n >= 0.
G.f.: 1/Product_{j=0..4}(1 - (1+2*j)*x).
E.g.f.: (d^4/dx^4)(exp(x)*((exp(2*x)-1)/2)^4/4!) = (2187/128)*exp(9*x) - (2401/96)*exp(7*x) + (625/64)*exp(5*x) - (27/32)*exp(3*x) + (1/384)*exp(x).
a(n) = h^{(5)}_n, the complete homogeneous symmetric function of degree n of the five symbols 1, 3, 5, 7, 9.
From Colin Barker, Dec 23 2017: (Start)
G.f.: 1 / ((1 - x)*(1 - 3*x)*(1 - 5*x)*(1 - 7*x)*(1 - 9*x)).
a(n) = (1 - 4*3^(4+n) + 6*5^(4+n) - 4*7^(4+n) + 9^(4+n)) / 384.
a(n) = 25*a(n-1) - 230*a(n-2) + 950*a(n-3) - 1689*a(n-4) + 945*a(n-5) for n>4.
(End)

A016198 Expansion of g.f. 1/((1-x)(1-2x)(1-5x)).

Original entry on oeis.org

1, 8, 47, 250, 1281, 6468, 32467, 162590, 813461, 4068328, 20343687, 101722530, 508620841, 2543120588, 12715635707, 63578244070, 317891351421, 1589457019248, 7947285620527, 39736429151210, 198682147853201, 993410743460308, 4967053725690147, 24835268645227950

Offset: 0

N. J. A. Sloane, Dec 11 1999

Index entries for linear recurrences with constant coefficients, signature (8,-17,10).

Cf. A000225, A000392, A002275, A002452, A003462, A003463, A003464, A016123, A016125, A016208, A016209, A016218, A016256, A023000, A023001.

Cf. A016127.

a:=n->sum((5^(n-j)-2^(n-j))/3,j=0..n): seq(a(n), n=1..20); # Zerinvary Lajos, Jan 04 2007

Join[{a=1,b=8},Table[c=7*b-10*a+1;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Feb 06 2011 *)

a(n) = (25*5^n - 16*2^n + 3)/12. - Bruno Berselli, Feb 09 2011
a(n) = [(5^0-2^0) + (5^1-2^1) + ... + (5^n-2^n)]/3. - r22lou(AT)cox.net, Nov 14 2005
a(0)=1, a(n) = 5*a(n-1) + 2^(n+1) - 1. - Vincenzo Librandi, Feb 07 2011
From Elmo R. Oliveira, Mar 26 2025: (Start)
E.g.f.: exp(x)*(25*exp(4*x) - 16*exp(x) + 3)/12.
a(n) = 8*a(n-1) - 17*a(n-2) + 10*a(n-3).
a(n) = A016127(n+1) - A003463(n+2). (End)

More terms from Wesley Ivan Hurt, May 05 2014

cp's OEIS Frontend

A007798 Expected number of random moves in Tower of Hanoi problem with n disks starting with a randomly chosen position and ending at a position with all disks on the same peg.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A016234 Expansion of 1/((1-x) * (1-5*x) * (1-9*x)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A021424 Expansion of 1/((1-x)(1-3x)(1-5x)(1-7x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Magma

Mathematica

PARI

Formula

A200859 a(n) = 2*a(n-1)+3*a(n-2)+5^n for n>1, a(0)=-2, a(1)=1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Sage

Formula

A200864 Expansion of 1/((1+x)*(1-3*x)*(1-5*x)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Formula

A016247 Expansion of 1/((1-x) * (1-6*x) * (1-11*x)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A286719 Column k=4 of triangle A039755, Sheffer(exp(x), (exp(2*x) - 1)/2).

Views

A016234 Expansion of 1/((1-x) * (1-5x) (1-9*x)).

A200859 a(n) = 2a(n-1)+3a(n-2)+5^n for n>1, a(0)=-2, a(1)=1.

A200864 Expansion of 1/((1+x)(1-3x)(1-5x)).

A016247 Expansion of 1/((1-x) * (1-6x) (1-11*x)).

A016198 Expansion of g.f. 1/((1-x)(1-2x)(1-5x)).