A127984 -id:A127984 - cp's OEIS frontend

A045883 a(n) = ((3n+1)2^n - (-1)^n)/9.

0, 1, 3, 9, 23, 57, 135, 313, 711, 1593, 3527, 7737, 16839, 36409, 78279, 167481, 356807, 757305, 1601991, 3378745, 7107015, 14913081, 31224263, 65244729, 136081863, 283348537, 589066695, 1222872633, 2535223751, 5249404473, 10856722887, 22429273657, 46290203079

Offset: 0

Edward Early

Without the initial zero, PSumSIGN transform of A001787. - Michael Somos, Jul 10 2003
Number of rises (drops) in the compositions of n+2 with parts in N.
From Michel Lagneau, Jan 13 2012: (Start)
This sequence is connected with the Collatz problem. We consider the array T(i,j) where the i-th row gives the parity trajectory of i, for example for i = 6, the infinite trajectory is 6 -> 3 -> 10 ->5 -> 16 ->8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4->2-> 1 ... and T(6,j) = [0,1,0,1,0,0,0,0,1,0,0,1,...,1,0,0,1,...]. Now, we consider the sum of the digits 1 of each array T(i,j), where
a(1) = sum of the digits "1" of T(i,j), i = 1..2^1 and j = 1;
a(2) = sum of the digits "1" of T(i,j), i = 1..2^2 and j = 1..2;
a(3) = sum of the digits "1" of T(i,j), i = 1..2^3 and j = 1..3;
a(n) = Sum_{i=1..2^n}(Sum_{j=1..n} T(i,j)) = Sum_{i=1..n} A001045(n)*2^(n-i) = convolution of A001045 and A000079 (see the formula below).
The number of digits "0" equals A113861(n) = n*2^n - a(n) because n and 2^n are the dimensions of each array.
An important result is that the ratio r = A113861(n) / A045883(n) tends towards 2 when n tends towards infinity. In other words, when the array tends towards infinity, the ratio r = (number of divisions by 2) / (number of multiplications by 3) tends towards 2, even if there exists divergent trajectories. That is the problem! For each possible divergent infinite trajectory, r < 2 even though the global ratio r is 2.
Conclusion:
1. For each number n with a convergent trajectory T(n,k), k = 1..infinity, or for each row of the array T(i,j), the ratio r tends towards 2 (the proof is easy because the trajectory becomes periodic from a certain index 1001001001...).
2. For each array of dimension n X 2^n, the radio r tends towards 2.
3. If there exists a number n such that the trajectory is divergent, this trajectory is random and r tends towards a real x such that 1 < = r < = x < 2.
4. In order to establish a proof of the Collatz problem from this considerations (if that is possible), it is necessary to prove that a ratio < 2 for an infinite row (or several rows) of an infinite array T(i,j) is incompatible with r = 2, the exact ratio for this array. (End)
a(n) is the distance spectral radius of the dimension-regular generalized recursive circulant graph (commonly known as multiplicative circulant graph) of order 2^n. - John Rafael M. Antalan, Sep 25 2020
Total sum over all compositions of n of the absolute differences between consecutive parts, assuming an initial part 0. - Alois P. Heinz, Apr 30 2025

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
John Rafael M. Antalan and Francis Joseph H. Campeña, Distance eigenvalues and forwarding indices of dimension-regular generalized recursive circulant graph of order power of two and three, arXiv:2009.11608[math.CO], 2020.
M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
Silvia Heubach and Toufik Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
F. K. Hwang, Three versions of a group testing game, SIAM J. Algebraic Discrete Methods 5 (1984), no. 2, 145--153. MR0745434(85d:90120). See p. 151, f(n) (but divide by 2). - _N. J. A. Sloane_, Apr 13 2014
Peter J. Larcombe and Eric J. Fennessey, On a Scaled Balanced-Power Product Recurrence, Fibonacci Quart. 54 (2016), no. 3, 242-246. See Remark 2.2 p. 244.
Peter J. Larcombe, Julius Fergy T. Rabago, and Eric J. Fennessey, On two derivative sequences from scaled geometric mean sequence terms, Palestine Journal of Mathematics (2018) Vol. 7(2), 397-405.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Partial sums of A059570, bisection: A014916.
Row sums of triangle A094953.
Cf. A059260, A127984.
Cf. A000079, A001045, A001787, A045883, A049260, A113861, A140960, A188545.
Cf. A238343, A238344.

[((3*n+1)*2^n-(-1)^n)/9: n in [0..35]]; // Vincenzo Librandi, Jun 15 2017

A045883:=n->((3*n+1)*2^n-(-1)^n)/9; seq(A045883(n), n=0..30); # Wesley Ivan Hurt, Mar 21 2014

nn=31;a=x^2(1-x)/(1-x-2x^2)/(1-2x);b=x^2/(1-2x)^2;Drop[CoefficientList[Series[(b-a)/2,{x,0,nn}],x],2] (* Geoffrey Critzer, Mar 21 2014 *)
CoefficientList[Series[x / ((1 + x) (1 - 2 x)^2), {x, 0, 33}], x] (* Vincenzo Librandi, Jun 15 2017 *)
LinearRecurrence[{3, 0, -4}, {0, 1, 3}, 33] (* Jean-François Alcover, Sep 27 2017 *)

{a(n) = if( n<-1, 0, ((3*n + 1)*2^n - (-1)^n) / 9)};

G.f.: x/((1+x)*(1-2*x)^2).
a(n) = 3*a(n-1) - 4*a(n-3).
Convolution of A001045 and A000079. G.f.: x/((1-2*x)(1-x-2*x^2)). - Paul Barry, May 21 2004
Starting with "1" = triangle A049260 * the odd integers as a vector. - Gary W. Adamson, Mar 06 2012
a(n) = A140960(n)/2. - J. M. Bergot, May 21 2013
From Wolfdieter Lang, Jun 14 2017: (Start)
a(n) = f(n)*2^n, where f(n) is a rational Fibonacci type sequence based on fuse(a,b) = (a+b+1)/2 with f(0) = 0, f(1) = 1/2 and f(n) = fuse(f(n-1), f(n-2)), for n >= 2. For fuse(a,b) see the Jeff Erickson link under A188545. Proof with f(n) = (3*n+1 - (-1)^n/2^n)/9, n >= 0, by induction.
a(n) = a(n-1) + 2*a(n-2) + 2^(n-1), n >= 0, with input a(-2) = 1/4 and a(-1) = 0. See also A127984. (End)
E.g.f.: (exp(2*x)*(1 + 6*x) - cosh(x) + sinh(x))/9. - Stefano Spezia, Apr 09 2025
a(n) = Sum_{k=0..n+2} k * A238343(n+2,k). - Alois P. Heinz, Apr 30 2025

Simpler description from Vladeta Jovovic, Jul 18 2002

A059570 Number of fixed points in all 231-avoiding involutions in S_n.

Original entry on oeis.org

1, 2, 6, 14, 34, 78, 178, 398, 882, 1934, 4210, 9102, 19570, 41870, 89202, 189326, 400498, 844686, 1776754, 3728270, 7806066, 16311182, 34020466, 70837134, 147266674, 305718158, 633805938, 1312351118, 2714180722, 5607318414, 11572550770, 23860929422

Offset: 1

Emeric Deutsch, Feb 16 2001

Number of odd parts in all compositions (ordered partitions) of n: a(3)=6 because in 3=2+1=1+2=1+1+1 we have 6 odd parts. Number of even parts in all compositions (ordered partitions) of n+1: a(3)=6 because in 4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1 we have 6 even parts.
Convolved with (1, 2, 2, 2, ...) = A001787: (1, 4, 12, 32, 80, ...). - Gary W. Adamson, May 23 2009
An elephant sequence, see A175654. For the corner squares 36 A[5] vectors, with decimal values between 15 and 480, lead to this sequence. For the central square these vectors lead to the companion sequence 4*A172481, for n>=-1. - Johannes W. Meijer, Aug 15 2010
a(n) is the total number of runs of equal parts in the compositions of n. a(5) = 34 because there are 34 runs of equal parts in the compositions of 5, with parentheses enclosing each run: (5), (4)(1), (1)(4), (3)(2), (2)(3), (3)(1,1), (1)(3)(1), (1,1)(3), (2,2)(1), (2)(1)(2), (1)(2,2), (2)(1,1,1), (1)(2)(1,1), (1,1)(2)(1), (1,1,1)(2), (1,1,1,1,1). - Gregory L. Simay, Apr 28 2017
a(n) - a(n-2) is the number of 1's in all compositions of n and more generally, the number of k's in all compositions of n+k-1. - Gregory L. Simay, May 01 2017

			a(3) = 6 because in the 231-avoiding involutions of {1,2,3}, i.e., in 123, 132, 213, 321, we have altogether 6 fixed points (3+1+1+1).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
Brian Hopkins, Andrew V. Sills, Thotsaporn "Aek" Thanatipanonda, and Hua Wang, Parts and subword patterns in compositions, Preprint 2015.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 30.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Cf. A001787, A027934, A045623, A127984, A128255, A172481, A225084.

[(3*n+4)*2^n/18-2*(-1)^n/9: n in [1..40]]; // Vincenzo Librandi, May 01 2017

LinearRecurrence[{3,0,-4},{1,2,6},30] (* Harvey P. Dale, Dec 29 2013 *)
Table[(3 n + 4) 2^n/18 - 2 (-1)^n/9, {n, 30}] (* Vincenzo Librandi, May 01 2017 *)

a(n) = (3*n+4)*2^n/18 - 2*(-1)^n/9.
G.f.: z*(1-z)/((1+z)*(1-2*z)^2).
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j)*2^k. - Paul Barry, Aug 29 2004
a(n) = Sum_{k=0..n+1} (-1)^(k+1)*binomial(n+1, k+j)*A001045(k). - Paul Barry, Jan 30 2005
Convolution of "Expansion of (1-x)/(1-x-2*x^2)" (A078008) with "Powers of 2" (A000079), treating the result as if offset=1. - Graeme McRae, Jul 12 2006
Convolution of "Difference sequence of A045623" (A045891) with "Positive integers repeated" (A008619), treating the result as if offset=1. - Graeme McRae, Jul 12 2006
a(n) = 3*a(n-1)-4*a(n-3); a(1)=1,a(2)=2,a(3)=6. - Philippe Deléham, Aug 30 2006
Equals row sums of A128255. (1, 2, 6, 14, 34, ...) - (0, 0, 1, 2, 6, 14, 34, ...) = A045623: (1, 2, 5, 12, 28, 64, ...). - Gary W. Adamson, Feb 20 2007
Equals triangle A059260 * [1, 2, 3, ...] as a vector. - Gary W. Adamson, Mar 06 2012
a(n) + a(n-1) = A001792(n-1). - Gregory L. Simay, Apr 30 2017
a(n) - a(n-2) = A045623(n-1). - Gregory L. Simay, May 01 2017
a(n) = A045623(n-1) + A045623(n-3) + A045623(n-5) + ... - Gregory L. Simay, Feb 19 2018
a(n) = A225084(2n,n). - Alois P. Heinz, Aug 30 2018

More terms from Eugene McDonnell (eemcd(AT)mac.com), Jan 13 2005

A172481 a(n) = (3n2^n+2^(n+4)+2*(-1)^n)/18.

Original entry on oeis.org

1, 2, 5, 11, 25, 55, 121, 263, 569, 1223, 2617, 5575, 11833, 25031, 52793, 111047, 233017, 487879, 1019449, 2126279, 4427321, 9204167, 19107385, 39612871, 82021945, 169636295, 350457401, 723284423, 1491308089, 3072094663, 6323146297, 13004206535, 26724240953

Offset: 0

Paul Curtz, Feb 04 2010

The binomial transform is in A126184.
An elephant sequence, see A175654 and A175655. There are 24 A[5] vectors, with decimal values between 7 and 448, that lead for the corner squares to this sequence. Its companion sequence for the central square is A175656. Furthermore there are 36 A[5] vectors, with decimal values between 15 and 480, that lead for the central square to four times this sequence for n >= -1. Its companion sequence for the corner squares is A059570. - Johannes W. Meijer, Aug 15 2010
a(n) is also the number of runs of weakly increasing parts in all compositions of n+1. a(2) = 5: (111), (12), (2)(1), (3). - Alois P. Heinz, Apr 30 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,0,-4)

Cf. A059570, A151529, A127984.

[(3*n*2^n+2^(n+4)+2*(-1)^n)/18: n in [0..40]]; // Vincenzo Librandi, Aug 04 2011

Table[(3n 2^n+2^(n+4)+2(-1)^n)/18,{n,0,40}]  (* or *)
CoefficientList[Series[(1-x-x^2)/((1+x)(1-2x)^2), {x,0,40}], x]  (* Harvey P. Dale, Mar 28 2011 *)

a(n)=(3*n*2^n+2^(n+4)+2*(-1)^n)/18 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: (1-x-x^2)/((1+x)*(1-2*x)^2).
a(n) = A001045(n-1)+2*a(n-1), n>0.
a(n)+A139790(n) = 2^(n+1) = A000079(n+1).
a(n) = A139790(n)+A140960(n).
a(n) = A001045(n)+(-1)^n*A084219(n).
a(n) = A127984(n) + 2^(n-1).  Application:  Problem 11623, AMM 119 (2012) 161. - Stephen J. Herschkorn, Feb 11 2012

Definition replaced by explicit formula by R. J. Mathar, Feb 11 2010

A127985 a(n) = floor(2^n*(n/3 + 4/9)).

Original entry on oeis.org

0, 1, 4, 11, 28, 67, 156, 355, 796, 1763, 3868, 8419, 18204, 39139, 83740, 178403, 378652, 800995, 1689372, 3553507, 7456540, 15612131, 32622364, 68040931, 141674268, 294533347, 611436316, 1267611875, 2624702236, 5428361443

Offset: 0

Artur Jasinski, Feb 09 2007

Vincenzo Librandi, Table of n, a(n) for n = 0..1000 (corrected by Ray Chandler, Jan 19 2019)
Wieb Bosma, Signed bits and fast exponentiation, J. Th. Nombres de Bordeaux, 13 no. 1 (2001), p. 27-41.
Index entries for linear recurrences with constant coefficients, signature (4,-3,-4,4).

Cf. A073371, A127976, A127978, A127979, A127980, A127981, A127982, A127983, A127984, A073371, A000337.

[(n/3 + 4/9)*2^n - 1/2 + (-1)^n/18: n in [1..40]]; // Vincenzo Librandi, May 26 2011

Table[(n/3 + 4/9) 2^n - 1/2 + (-1)^n/18, {n, 1, 50}]
LinearRecurrence[{4,-3,-4,4},{1,4,11,28},50] (* Harvey P. Dale, May 15 2011 *)

PARI
```
a(n)=(n*3+4)<M. F. Hasler, Oct 07 2014
```

a(n) = (n/3 + 4/9)*2^n - 1/2 + (-1)^n/18.
a(1)=1, a(2)=4, a(3)=11, a(4)=28, a(n) = 4*a(n-1)-3*a(n-2)-4*a(n-3)+4*a(n-4). - Harvey P. Dale, May 15 2011
G.f.: x*(1-2*x^2)/((1-2*x)^2*(1-x^2)). - Harvey P. Dale, May 15 2011
E.g.f.: ((4 + 6*x)*cosh(2*x) - 5*sinh(x) + 4*cosh(x)*((2 + 3*x)*sinh(x) - 1))/9. - Stefano Spezia, May 25 2023

Definition simplified by M. F. Hasler, Oct 07 2014

Sequence extended to a(0)=0 by M. F. Hasler, Oct 08 2014

A331944 a(n)/ceiling(6^(n-7)) is the expected number of rolls of a fair 6-sided die in a game where the player starts at 0, advances the position by the outcome of the die's roll until exactly position n is reached. Positions beyond n are avoided by staying at the last visited position, but counting the rolls.

Original entry on oeis.org

6, 6, 6, 6, 6, 6, 7, 43, 265, 1639, 10177, 63463, 397585, 2456503, 15189313, 93961351, 581260273, 3594003799, 22197096865, 136829952295, 843199062097, 5193720847351, 31972185139201, 196686016677319, 1209120275495089, 7428214177132183, 45613560985649761

Offset: 1

Hugo Pfoertner, Feb 19 2020

nonn

a(100)/6^93 = 33.333333333333370756088277230775... is the expected playing time of the "Snakes and Ladders" game on the empty board with all snakes and ladders removed. Althoen et al. (see link p. 74) cite this as "almost exactly 33 moves". One can assume that the omission of the addend of 1/3 was an obvious oversight.

Hugo Pfoertner, Table of n, a(n) for n = 1..200
S. C. Althoen, L. King, K. Schilling, How long is a game of snakes and ladders? The Mathematical Gazette, Vol. 77, No. 478 (Mar., 1993), pp. 71-76.

Cf. A000400, A127984.

xpected(n,m)={my(M=matrix(n+1,n+1,i,j,0)); for(i=1,n+1,my(kadd=0); for(j=i+1,i+m,if(j>n+1,kadd++,M[i,j]=1));M[i,i]+=kadd); vecsum((1/(matid(n)-M[1..n,1..n]/m))[1,])};
for(k=1,27,my(x=xpected(k,6));print1(numerator(x),", "))

Conjectures from Colin Barker, Feb 21 2020: (Start)
G.f.: x*(6 - 36*x - 36*x^2 - 36*x^3 - 36*x^4 - 36*x^5 - 35*x^6 + 279930*x^7 + 279900*x^8 + 279720*x^9 + 278640*x^10 + 272160*x^11 + 233280*x^12) / ((1 - 6*x)^2*(1 + 5*x + 24*x^2 + 108*x^3 + 432*x^4 + 1296*x^5)).
a(n) = 7*a(n-1) - 46656*a(n-7) for n>13.
(End)

cp's OEIS Frontend

A045883 a(n) = ((3*n+1)*2^n - (-1)^n)/9.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A059570 Number of fixed points in all 231-avoiding involutions in S_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A172481 a(n) = (3*n*2^n+2^(n+4)+2*(-1)^n)/18.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A127985 a(n) = floor(2^n*(n/3 + 4/9)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A045883 a(n) = ((3n+1)2^n - (-1)^n)/9.

A172481 a(n) = (3n2^n+2^(n+4)+2*(-1)^n)/18.