A014916 -id:A014916 - cp's OEIS frontend

A047849 a(n) = (4^n + 2)/3.

1, 2, 6, 22, 86, 342, 1366, 5462, 21846, 87382, 349526, 1398102, 5592406, 22369622, 89478486, 357913942, 1431655766, 5726623062, 22906492246, 91625968982, 366503875926, 1466015503702, 5864062014806, 23456248059222, 93824992236886, 375299968947542

Offset: 0

Clark Kimberling

Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6. - Paul Barry, Mar 10 2004
The number of closed walks of odd length of the cyclic graph is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case. - Wolfdieter Lang, Nov 08 2011
A. A. Ivanov conjectures that the dimension of the universal embedding of the unitary dual polar space DSU(2n,4) is a(n). - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004
Permutations with two fixed points avoiding 123 and 132.
Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302. - Paul Curtz, Mar 25 2008
Also the number of permutations of length n which avoid 4321 and 4123 (or 4321 and 3412, or 4123 and 3214, or 4123 and 2143). - Vincent Vatter, Aug 17 2009; minor correction by Henning Ulfarsson, May 14 2017
This sequence is related to A014916 by A014916(n) = n*a(n)-Sum_{i=0..n-1} a(i). - Bruno Berselli, Jul 27 2010, Mar 02 2012
For n >= 2, a(n) equals 2^n times the permanent of the (2n-2) X (2n-2) tridiagonal matrix with 1/sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
For n > 0, counts closed walks of length (n) at a vertex of a triangle with two (x2) loops at each vertex. - David Neil McGrath, Sep 11 2014
From Michel Lagneau, Feb 26 2015: (Start)
a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.
Proof:
All integers of the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} are of the form 2^k(2m+1) where k and m integers. The greatest odd divisor of a such integer is 2m+1. Reciprocally, if 2m+1 is an odd integer <= 2^n, there exists a unique integer in the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} where 2m+1 is the greatest odd divisor. Hence the recurrence relation:
   a(n) = a(n+1) + (1 + 3 + ... + 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) for n >= 2.
We obtain immediately: a(n) = a(1) + 4 + ... + 4^n = (4^n+2)/3. (End)
The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - Peter Bala, Aug 12 2021
Let q = 2^(2n+1) and Omega_n be the Suzuki ovoid with q^2 + 1 points. Then a(n) is the number of orbits of the finite Suzuki group Sz(q) on 3-subsets of Omega_n. Link to result in References. - Paul M. Bradley, Jun 04 2023
Also the cogrowth sequence for the 8-element dihedral group D8 = . - Sean A. Irvine, Nov 04 2024

			a(2) = 6 for the number of round trips in C_6 from the six round trips from, say, vertex no. 1: 12121, 16161, 12161, 16121, 12321 and 16561. - _Wolfdieter Lang_, Nov 08 2011

Bruno Berselli, Table of n, a(n) for n = 0..1000
Jeffrey M. Barnes, Georgia Benkart, and Tom Halverson, McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 37-51.
Pascal Caron, Jean-Gabriel Luque, and Bruno Patrou, A combinatorial approach for the state complexity of the Shuffle product, arXiv:1905.08120 [cs.FL], 2019.
Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, and Seyed Ahmad Mojallal, Riordan graphs I: structural properties, Linear Algebra and its Applications, 579. pp. 89-135, Prop. 2.8. (2019).
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 37-48. See Conjecture 5.5.
Kittitat Iamthong, Ji-Hwan Jung, and Sergey Kitaev, Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations, arXiv:2009.01410 [math.CO], 2020.
D. Kremer and W. C. Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Mathematics 268 (2003), 171-183.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.
Wikipedia, Permutation classes avoiding two patterns of length 4.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A000302, A001045, A002450, A007583, A024493, A047848, A078008, A121314, A131708, A178789, A199571.

Cf. A014916, A073724, A020988, A039301.

[(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015

(4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* Harvey P. Dale, Nov 27 2015 *)

PARI
```
a(n)=(4^n+2)/3;
```

def A047849(n): return (pow(4, n) +2)//3
print([A047849(n) for n in range(41)]) # G. C. Greubel, Jan 17 2025

def A047849(n): return ((1 << (2 * n)) + 2) // 3 # John Reimer Morales, Aug 05 2025

n-th difference of a(n), a(n-1), ..., a(0) is 3^(n-1) for n >= 1.
From Henry Bottomley, Aug 29 2000: (Start)
a(n) = (4^n + 2)/3.
a(n) = 4*a(n-1) - 2.
a(n) = 5*a(n-1) - 4*a(n-2).
a(n) = 2*A007583(n-1) = A002450(n) + 1. (End)
a(n) = A047848(1,n).
With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - Paul Barry, Aug 26 2003
a(n) = A007583(n) - A002450(n) = A001045(2n+1) - A001045(2n) . - Philippe Deléham, Feb 25 2004
Second binomial transform of A078008. Binomial transform of 1, 1, 3, 9, 81, ... (3^n/3 + 2*0^n/3). a(n) = A078008(2n). - Paul Barry, Mar 14 2004
G.f.: (1-3*x)/((1-x)*(1-4*x)). - Herbert Kociemba, Jun 06 2004
a(n) = Sum_{k=0..n} 2^k*A121314(n,k). - Philippe Deléham, Sep 15 2006
a(n) = (A001045(2*n+1) + 1)/2. - Paul Barry, Dec 05 2007
From Bruno Berselli, Jul 27 2010: (Start)
a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2.
Sum_{i=0..n} a(i) = A073724(n). (End)
For n >= 3, a(n) equals [2, 1, 1; 1, 2, 1; 1, 1, 2]^(n - 2)*{1, 1, 2}*{1, 1, 2}. - John M. Campbell, Jul 09 2011
a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - Oboifeng Dira, May 29 2020
From Elmo R. Oliveira, Dec 21 2023: (Start)
E.g.f.: (exp(x)*(exp(3*x) + 2))/3.
a(n) = A178789(n+1)/3. (End)
a(n) = A000302(n) - A020988(n). - John Reimer Morales, Aug 03 2025

New name from Charles R Greathouse IV, Dec 22 2011

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

Original entry on oeis.org

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

A014825 a(n) = 4*a(n-1) + n with n > 1, a(1)=1.

Original entry on oeis.org

1, 6, 27, 112, 453, 1818, 7279, 29124, 116505, 466030, 1864131, 7456536, 29826157, 119304642, 477218583, 1908874348, 7635497409, 30541989654, 122167958635, 488671834560, 1954687338261, 7818749353066

Offset: 1

N. J. A. Sloane

			G.f. = x + 6*x^2 + 27*x^3 + 112*x^4 + 453*x^5 + 1818*x^6 + 7279*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See pp. 9, 18.
Hacène Belbachir and El-Mehdi Mehiri, Enumerating moves in the optimal solution of the Tower of Hanoi, arXiv:2210.08657 [math.CO], 2022.
László Tóth, On Schizophrenic Patterns in b-ary Expansions of Some Irrational Numbers, arXiv:2002.06584 [math.NT], 2020. See also Proc. Amer. Math. Soc. 148 (2020), 461-469.
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Cf. A002450 (first differences), A052161 (partial sums).
Cf. A001045, A006314, A014916, A053142, A091919.
Cf. A171654 (mod 10).

[(4^(n+1)-3*n-4)/9: n in [1..30]]; // Vincenzo Librandi, Aug 23 2011

RecurrenceTable[{a[1]==1,a[n]==4a[n-1]+n},a[n],{n,30}] (* Harvey P. Dale, Oct 12 2011 *)
a[ n_]:= SeriesCoefficient[x/((1-4x)(1-x)^2), {x, 0, n}] (* Michael Somos, Jun 20 2012 *)

{a(n) = polcoeff( x / ((1 - x)^2 * (1 - 4*x)) + x * O(x^n), n)} /* Michael Somos, Jun 20 2012 */

def A014825(n): return (((1<<(n+1<<1))-4)//3-n)//3 # Chai Wah Wu, Nov 12 2024

[(4^(n+1) -3*n -4)/9 for n in (1..30)] # G. C. Greubel, Feb 18 2020

a(n) = (4^(n+1) - 3*n - 4)/9.
G.f.: x/((1-4*x)*(1-x)^2).
a(n) = Sum_{k=0..n} (n-k)*4^k = Sum_{k=0..n} k*4^(n-k). - Paul Barry, Jul 30 2004
a(n) = Sum_{k=0..n} binomial(n+2, k+2)*3^k [Offset 0]. - Paul Barry, Jul 30 2004
a(n) = Sum_{k=0..n} Sum_{j=0..2k} (-1)^(j+1)*J(j)*J(2k-j), J(n) = A001045(n). - Paul Barry, Oct 23 2009
Convolution square of A006314. - Michael Somos, Jun 20 2012
E.g.f.: (4*exp(4*x) - (4+3*x)*exp(x))/9. - G. C. Greubel, Feb 18 2020
a(n) = A014916(-n-1)*4^(n+1) = A091919(2*n-2) for all n in Z. - Michael Somos, Oct 02 2020
a(n) = Sum_{k=0..n} A002450(k). - Joseph Brown, May 11 2021
Last digits give A171654. - Paul Curtz, Oct 10 2021

A193843 Mirror image of the triangle A193842.

Original entry on oeis.org

1, 4, 1, 13, 7, 1, 40, 34, 10, 1, 121, 142, 64, 13, 1, 364, 547, 334, 103, 16, 1, 1093, 2005, 1549, 643, 151, 19, 1, 3280, 7108, 6652, 3478, 1096, 208, 22, 1, 9841, 24604, 27064, 17086, 6766, 1720, 274, 25, 1, 29524, 83653, 105796, 78322, 37384, 11926

Offset: 0

Clark Kimberling, Aug 07 2011

A193843 is obtained by reversing the rows of the triangle A193842.

Consider the transformation 1 + x + x^2 + x^3 + ... + x^n = A_0*(x-3)^0 + A_1*(x-3)^1 + A_2*(x-3)^2 + ... + A_n*(x-3)^n. This sequence gives A_0, ... A_n as the entries in the n-th row of this triangle, starting at n = 0. - Derek Orr, Oct 14 2014

			First six rows:
    1;
    4,   1;
   13,   7,   1;
   40,  34,  10,   1;
  121, 142,  64,  13,  1;
  364, 547, 334, 103, 16, 1;

E. Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 (2001) 33-51.

Cf. A193842.
Cf. A000225 (alt.row sums), A002450 (row sums), A014916 (weighted sums).
Cf. A003462 (first col.), A082574 (anti-diag.sums).

T := proc(n,k) option remember;
if k<0 or k>n then 0 elif n=k then 1 elif n=1 and k=0 then 4
else 4*T(n-1,k) + T(n-1,k-1) -3*T(n-2,k) - T(n-2,k-1) fi end;
seq(seq(T(n,k), k=0..n), n=0..9); # Peter Luschny, Jan 18 2014

z = 10;
p[n_, x_] := (x + 1)^n;
q[n_, x_] := (x + 2)^n
p1[n_, k_] := Coefficient[p[n, x], x^k];
p1[n_, 0] := p[n, x] /. x -> 0;
d[n_, x_] := Sum[p1[n, k]*q[n - 1 - k, x], {k, 0, n - 1}]
h[n_] := CoefficientList[d[n, x], {x}]
TableForm[Table[Reverse[h[n]], {n, 0, z}]]
Flatten[Table[Reverse[h[n]], {n, -1, z}]]  (* A193842 *)
TableForm[Table[h[n], {n, 0, z}]]  (* A193843 *)
Flatten[Table[h[n], {n, -1, z}]]

for(n=0,20,for(k=0,n,print1(1/k!*sum(i=0,n,(3^(i-k)*prod(j=0,k-1,i-j))),", "))) \\ Derek Orr, Oct 14 2014

Write w(n,k) for the triangle at A193842.  The triangle at A193843 is then given by w(n,n-k).
From Peter Bala, Jul 31 2012: (Start)
Matrix product of the shifted Pascal triangle {C(n+1,k+1)}n,k>=0 and the square of the Pascal triangle {2^(n-k)*C(n,k)}n,k>=0. Thus the triangle is the product of two triangular Galton arrays and so is also a Galton array (Neuwirth, Theorem 10).
T(n,k) = Sum_{i = 0..n} C(n+1,i+1)*C(i,k)*2^(i-k).
Riordan array (1/((1 - x)*(1 - 3*x)), x/(1 - 3*x)).
O.g.f.: 1/((1 - x)*(1 - (3 + t)*x)) = 1 + (4 + t)*x + (13 + 7*t + t^2)*x^2 + ....
First column A003462. Row sums A002450. Alternating row sums A000225.
Antidiagonal sums (Sum_{k} T(n-k,k)) A082574. Weighted sums (Sum_{k} k*T(n,k)) A014916. (End)
T(n,k) = 4*T(n-1,k) + T(n-1,k-1) - 3*T(n-2,k) - T(n-2,k-1), T(0,0) = T(1,1) = 1, T(1,0) = 4, T(n,k) = 0 if k < 0 or if k > n. - Philippe Deléham, Jan 17 2014

A323222 A(n, k) = [x^k] (1 - 4x)^(-n/2)x/(1 - x), square array read by ascending antidiagonals with n >= 0 and k >= 0.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 5, 9, 1, 0, 1, 7, 21, 29, 1, 0, 1, 9, 37, 85, 99, 1, 0, 1, 11, 57, 177, 341, 351, 1, 0, 1, 13, 81, 313, 807, 1365, 1275, 1, 0, 1, 15, 109, 501, 1593, 3579, 5461, 4707, 1, 0, 1, 17, 141, 749, 2811, 7737, 15591, 21845, 17577, 1

Offset: 0

Peter Luschny, Jan 24 2019

General asymptotic formula for g.f. (1 - 4*x)^(-j/2)*x/(1 - x) and fixed j>0 is a(n) ~ n^(j/2 - 1) * 4^n / (3*Gamma(j/2)). - Vaclav Kotesovec, Jan 29 2019

			[n\k] 0  1   2    3     4      5       6       7        8         9
-------------------------------------------------------------------
[0]   0, 1,  1,   1,    1,     1,      1,      1,       1,        1, ... A057427
[1]   0, 1,  3,   9,   29,    99,    351,   1275,    4707,    17577, ... A006134
[2]   0, 1,  5,  21,   85,   341,   1365,   5461,   21845,    87381, ... A002450
[3]   0, 1,  7,  37,  177,   807,   3579,  15591,   67071,   285861, ... A277178
[4]   0, 1,  9,  57,  313,  1593,   7737,  36409,  167481,   757305, ... A014916
[5]   0, 1, 11,  81,  501,  2811,  14823,  74883,  366603,  1752273, ... A323223
[6]   0, 1, 13, 109,  749,  4589,  26093, 140781,  730605,  3679725, ...
[7]   0, 1, 15, 141, 1065,  7071,  43107, 247311, 1355847,  7175661, ...
[8]   0, 1, 17, 177, 1457, 10417,  67761, 411825, 2377905, 13191345, ...
[9]   0, 1, 19, 217, 1933, 14803, 102319, 656587, 3982195, 23104441, ...
Triangle given by antidiagonals:
0;
0, 1;
0, 1,  1;
0, 1,  3,   1;
0, 1,  5,   9,   1;
0, 1,  7,  21,  29,    1;
0, 1,  9,  37,  85,   99,    1;
0, 1, 11,  57, 177,  341,  351,    1;
0, 1, 13,  81, 313,  807, 1365, 1275,    1;
0, 1, 15, 109, 501, 1593, 3579, 5461, 4707, 1;

Sums of antidiagonals are A323217. Main diagonal is A323219.
Rows: A057427 (n=0), A006134 (n=1), A002450 (n=2), A277178 (n=3), A014916 (n=4), A323223 (n=5).
Columns: A005408 (k=2), A059993 (k=3), A323218 (k=4).
Similar array based on Catalan numbers is A323224.

Row := proc(n, len) local ogf, ser; ogf := (1 - 4*x)^(-n/2)*x/(1 - x);
ser := series(ogf, x, (n+1)*len+1); seq(coeff(ser, x, j), j=0..len) end:
for n from 0 to 9 do Row(n, 9) od;

BF[N_, K_] := Module[{}, r[n_, k_] := FrobeniusSolve[ConstantArray[1, n], k];
X[n_] := Flatten[Table[r[N, j], {j, 0, n - 1}], 1];
CentralBinomial[n_] := Binomial[2 n, n];
Sum[Product[CentralBinomial[m[[i]]], {i, 1, N}], {m , X[K]}]];
Trow[n_] := Table[BF[n, k], {k, 0, 9}]; Table[Trow[n], {n, 1, 9}]

For n>0 and k>0 let X(n, k) denote the set of all tuples of length n with elements from {0, ..., k-1} with sum < k. Let b(m) = binomial(2*m, m). Then A(n, k) = Sum_{(j1,...,jn) in X(n, k)} b(j1)*b(j2)*...*b(jn).

A378727 The total number of fires in a rooted undirected infinite 4-ary tree with a self-loop at the root, when the chip-firing process starts with (4^n-1)/3 chips at the root.

Original entry on oeis.org

0, 1, 10, 67, 380, 1973, 9710, 46119, 213600, 970905, 4349650, 19262731, 84507460, 367855997, 1590728630, 6840133103, 29269406760, 124713124449, 529394487450, 2239745908435, 9447655468300, 39745309211461, 166799986198910, 698474942207927, 2918999758480880, 12176398992520233, 50707195804467810

Offset: 1

Tanya Khovanova and the MIT PRIMES STEP senior group, Dec 05 2024

Each vertex of this tree has degree 5. If a vertex has at least 5 chips, the vertex fires, and one chip is sent to each neighbor. The root sends 1 chip to each of its four children and one chip to itself.
The order of the firings doesn't affect the number of firings.
This number of chips is interesting because the stable configuration has 1 chip for every vertex in the top n layers.
a(n) is partial sums of A014916.
For binary trees, the corresponding sequence is A045618.
For ternary trees, the corresponding sequence is A212337.
For 5-ary trees, the corresponding sequence is A378728.
a(2k-1) is divisible by 10.

Yifan Xie, Table of n, a(n) for n = 1..2000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 15.
Wikipedia, Chip-firing game.
Index entries for linear recurrences with constant coefficients, signature (10,-33,40,-16).

Cf. A045618, A014916, A212337, A378728.

Table[((3 n - 5) 4^n + 3 n + 5)/27, {n, 30}]

a(n) = ((3*n - 5)*4^n + 3*n + 5)/27.

A014917 a(1)=1, a(n) = n*5^(n-1) + a(n-1).

Original entry on oeis.org

1, 11, 86, 586, 3711, 22461, 131836, 756836, 4272461, 23803711, 131225586, 717163086, 3890991211, 20980834961, 112533569336, 600814819336, 3194808959961, 16927719116211, 89406967163086, 470876693725586, 2473592758178711, 12964010238647461, 67800283432006836, 353902578353881836

Offset: 1

Olivier Gérard

From Gary Detlefs, Aug 31 2021 (Start)
This is the x=5 member of the x-family of sequences with member a(x, n) = x^n*Sum_{k=1..n} S(x, k), with S(x, k) = Sum_{j=1..k} 1/x^j.
S(x, k) = (x^k - 1)/((x-1)*x^k) = (1/x^k)*Sum_{j=0..k-1} x^j, and a(x,n) = ((n*(x-1) - 1)*x^n + 1)/(x-1)^2.
The sequence {x^k*S(x, k)} with recurrence signature (x+1, -x) leads to sequence {a(x, n)} with recurrence signature (2*x+1, -x*(x+2), x^2). (End) [Rewritten by Wolfdieter Lang, Nov 30 2021]

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 16.
Index entries for linear recurrences with constant coefficients, signature (11,-35,25).

Cf. A000351, A003463, A014915, A014916, A014917, A014918, A014920, A014921, A014923.

I:=[1, 11]; [n le 2 select I[n] else 10*Self(n-1)-25*Self(n-2)+ 1: n in [1..30]]; // Vincenzo Librandi, Oct 23 2012

CoefficientList[Series[1/((1 - x)(1 - 5 x)^2), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 23 2012 *)
LinearRecurrence[{11,-35,25},{1,11,86},20] (* Harvey P. Dale, May 06 2013 *)

From Vincenzo Librandi, Oct 23 2012: (Start)
a(n) = 10*a(n-1) - 25*a(n-2) + 1; a(1)=1, a(2)=11.
G.f.: x/((1-x)*(1-5*x)^2). (End)
a(n) = 11*a(n-1) - 35*a(n-2) + 25*a(n-3); a(1)=1, a(2)=11, a(3)=86. - Harvey P. Dale, May 06 2013
a(n) = 5^n*Sum_{k=1..n} (Sum_{j=1..k} 1/x^j) = ((4*n - 1)*5^n + 1)/4^2. See the general comment above, and the first formula. - Gary Detlefs, Aug 31 2021 [Edited by Wolfdieter Lang, Nov 30 2021]
E.g.f.: exp(x)*(1 + exp(4*x)*(20*x - 1))/16. - Elmo R. Oliveira, May 24 2025

A059045 Square array T(n,k) read by antidiagonals where T(0,k) = 0 and T(n,k) = 1 + 2k + 3k^2 + ... + n*k^(n-1).

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 6, 5, 1, 0, 1, 10, 17, 7, 1, 0, 1, 15, 49, 34, 9, 1, 0, 1, 21, 129, 142, 57, 11, 1, 0, 1, 28, 321, 547, 313, 86, 13, 1, 0, 1, 36, 769, 2005, 1593, 586, 121, 15, 1, 0, 1, 45, 1793, 7108, 7737, 3711, 985, 162, 17, 1, 0, 1, 55, 4097, 24604, 36409

Offset: 0

Henry Bottomley, Dec 18 2000

			   0,   0,   0,    0,     0,      0,      0,      0,       0, ...
   1,   1,   1,    1,     1,      1,      1,      1,       1, ...
   1,   3,   5,    7,     9,     11,     13,     15,      17, ...
   1,   6,  17,   34,    57,     86,    121,    162,     209, ...
   1,  10,  49,  142,   313,    586,    985,   1534,    2257, ...
   1,  15, 129,  547,  1593,   3711,   7465,  13539,   22737, ...
   1,  21, 321, 2005,  7737,  22461,  54121, 114381,  219345, ...
   1,  28, 769, 7108, 36409, 131836, 380713, 937924, 2054353, ...

Cf. A000004, A000012, A005408, A056109, A056578, A056579 (rows 1-6).

Cf. A057427, A000217, A000337, A014915, A014916, A014917, A014918, A014920 (columns 1-7).

A059045 := proc(n,k)
    if k = 1 then
        n*(n+1) /2 ;
    else
        (1+n*k^(n+1)-k^n*(n+1))/(k-1)^2 ;
    end if;
end proc: # R. J. Mathar, Mar 29 2013

T(n,k) = n*k^(n-1)+T(n-1, k) = (n*k^(n+1)-(n+1)*k^n+1)/(k-1)^2.

A108283 Triangle read by rows, generated from (..., 3, 2, 1).

Original entry on oeis.org

1, 1, 3, 1, 5, 6, 1, 7, 17, 10, 1, 9, 34, 49, 15, 1, 11, 57, 142, 129, 21, 1, 13, 86, 313, 547, 321, 28, 1, 15, 121, 586, 1593, 2005, 769, 36, 1, 17, 162, 985, 3711, 7737, 7108, 1793, 45, 1, 19, 209, 1534, 7465, 22461, 36409, 24604, 4097, 55, 1, 21, 262, 2257, 13539, 54121, 131836, 167481, 83653, 9217, 66

Offset: 1

Gary W. Adamson, May 30 2005

Inverse binomial transforms of each column form the rows of A108284. Rightmost diagonal = triangular numbers, (A000217); while diagonals going to the left from (1, 3, 6, ...) are A000337 starting with 1: (1, 5, 17, 49, ...); A014915: (1, 7, 34, 142, ...); A014916: (1, 9, 57, ...); A014917: (1, 11, 86, ...).

			4th column = 10, 49, 142, 313, ... = f(x), x = 1, 2, 3; 4x^3 + 3x^2 + 2x + 1. f(3) = 142.
First few rows of the triangle:
  1;
  1,  3;
  1,  5,  6;
  1,  7, 17,  10;
  1,  9, 34,  49,  15;
  1, 11, 57, 142, 129, 21;
  ...

Cf. A059045, A108284, A000217, A000337, A014915, A014916, A014917.

A108283 := proc(n,k)
    local x ;
    x := n-k+1 ;
    add( i*x^(i-1),i=1..k) ;
end proc:
seq(seq( A108283(n,k),k=1..n),n=1..10) ; # R. J. Mathar, Sep 14 2016

T[, 1] := 1; T[n, n_] := n (n + 1)/2; T[n_, k_] := (1 - (n - k + 1)^k*(k^2 - k*n + 1))/(n - k)^2; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 13 2016 *)

n-th column = f(x), x = 1, 2, 3; n*x^(n-1) + (n-1)*x^(n-2) + (n-3)*x^(n-3) + ... + 1.

T(n,k) = (1+ (n-k+1)^k*(n*k-k^2-1))/ (n-k)^2, n>k. - Jean-François Alcover, Sep 13 2016

More terms from Jean-François Alcover, Sep 13 2016

A113071 Expansion of g.f. ((1+x)/(1-3*x))^2.

Original entry on oeis.org

1, 8, 40, 168, 648, 2376, 8424, 29160, 99144, 332424, 1102248, 3621672, 11809800, 38263752, 123294312, 395392104, 1262703816, 4017693960, 12741829416, 40291730856, 127073920392, 399817944648, 1255242384360, 3933092804328

Offset: 0

Paul Barry, Oct 14 2005

Binomial transform is A014916. In general, ((1+x)/(1-r*x))^2 expands to a(n) = ((r+1)*r^n*((r+1)*n + r-1) + 0^n)/r^2, which is also a(n) = Sum_{k=0..n} C(n,k)*Sum_{j=0..k} (j+1)*(r+1)^j. This is the self-convolution of the coordination sequence for the infinite tree with valency r.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-9).

Cf. A003946, A014916, A081038.

a:=[1,8,40];; for n in [4..30] do a[n]:=6*a[n-1]-9*a[n-2]; od; a; # G. C. Greubel, May 24 2019

I:=[8,40]; [1] cat [n le 2 select I[n] else 6*Self(n-1) - 9*Self(n-2): n in [1..30]]; // G. C. Greubel, May 24 2019

CoefficientList[Series[(1+x)^2/(1-3x)^2, {x, 0, 30}], x] (* Georg Fischer, May 24 2019 *)
LinearRecurrence[{6,-9}, {1,8,40}, 30] (* G. C. Greubel, May 24 2019 *)

my(x='x+O('x^30)); Vec(((1+x)/(1-3*x))^2) \\ G. C. Greubel, May 24 2019

(((1+x)/(1-3*x))^2).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 24 2019

G.f.: (1+x)^2/(1-3*x)^2. [Corrected by Georg Fischer, May 24 2019]
a(n) = (8*3^n*(2*n+1) + 0^n)/9 = (4*3^n*(4*n+2) + 0^n)/9;
a(n) = Sum_{k=0..n} A003946(k)*A003946(n-k).
a(n) = Sum_{k=0..n} C(n, k)*Sum_{j=0..k} (j+1)*4^j.
a(n) = 8*A081038(n-1), n>0. - R. J. Mathar, Nov 28 2014
E.g.f.: (1 + 8*exp(3*x)*(1 + 6*x))/9. - Stefano Spezia, Jan 31 2025

cp's OEIS Frontend

A047849 a(n) = (4^n + 2)/3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A014825 a(n) = 4*a(n-1) + n with n > 1, a(1)=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Sage

Formula

A193843 Mirror image of the triangle A193842.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A323222 A(n, k) = [x^k] (1 - 4*x)^(-n/2)*x/(1 - x), square array read by ascending antidiagonals with n >= 0 and k >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A378727 The total number of fires in a rooted undirected infinite 4-ary tree with a self-loop at the root, when the chip-firing process starts with (4^n-1)/3 chips at the root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A014917 a(1)=1, a(n) = n*5^(n-1) + a(n-1).

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

A323222 A(n, k) = [x^k] (1 - 4x)^(-n/2)x/(1 - x), square array read by ascending antidiagonals with n >= 0 and k >= 0.