A000302 -id:A000302 - cp's OEIS frontend

A002802 a(n) = (2n+3)!/(6n!*(n+1)!).

1, 10, 70, 420, 2310, 12012, 60060, 291720, 1385670, 6466460, 29745716, 135207800, 608435100, 2714556600, 12021607800, 52895074320, 231415950150, 1007340018300, 4365140079300, 18839025605400, 81007810103220, 347176329013800, 1483389769422600

Offset: 0

N. J. A. Sloane

For n >= 1 a(n) is also the number of rooted bicolored unicellular maps of genus 1 on n+2 edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 20 2001
a(n) is half the number of (n+2) X 2 Young tableaux with a three horizontal walls between the first and second column. If there is a wall between two cells, the entries may be decreasing; see [Banderier, Wallner 2021], A000984 for one horizontal wall, and A002457 for two. - Michael Wallner, Jan 31 2022
From Robert Coquereaux, Feb 12 2024: (Start)
Call B(p,g) the number of genus g partitions of a set with p elements (genus-dependent Bell number). Up to an appropriate shift the given sequence counts the genus 1 partitions of a set: we have a(n) = B(n+4,1), with a(0)= B(4,1)=1.
When shifted with an offset 4 (i.e., defining b(p)=a(p-4), which starts with 0,0,0,1,10,70, etc., and b(4)=1), the given sequence reads b(p) = (1/( 2^4 3 )) * (1/( (2 p - 1) (2 p - 3))) * (1/(p - 4)!) * (2p)!/p!. In this form it appears as a generalization of Catalan numbers (that indeed count the genus 0 partitions).
Call C[p, [alpha], g] the number of partitions of a set with p elements, of cyclic type [alpha], and of genus g (genus g Faa di Bruno coefficients of type [alpha]). Up to an appropriate shift the given sequence also counts the genus 1 partitions of p=2k into k parts of length 2, which is then called C[2k, [2^k], 1], and we have a(n) = C[2k, [2^k], 1] for k=n+2.
The two previous interpretations of this sequence, leading to a(n) = B(n+4, 1) and to a(n) = C[2(n+2), [2^(n+2)], 1] are not related in any obvious way. (End)

			G.f. = 1 + 10*x + 70*x^2 + 420*x^3 + 2310*x^4 + 12012*x^5 + 60060*x^6 + ...

C. Jordan, Calculus of Finite Differences. Röttig and Romwalter, Budapest, 1939; Chelsea, NY, 1965, p. 449.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
Cyril Banderier and Michael Wallner, Young Tableaux with Periodic Walls: Counting with the Density Method, Séminaire Lotharingien de Combinatoire, 85B (2021), Art. 47, 12 pp.
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See pp. 4, 12.
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus: a compendium of results, Journal of Integer Sequences, Vol. 27 (2024), Article 24.2.6. See p. 9. See also arXiv:2305.01100, 2023. See pp. 9, 19.
R. Cori and G. Hetyei, Counting genus one partitions and permutations, arXiv preprint arXiv:1306.4628 [math.CO], 2013.
R. Cori and G. Hetyei, How to count genus one partitions, FPSAC 2014, Chicago, Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France, 2014, 333-344.
Alain Goupil and Gilles Schaeffer, Factoring N-Cycles and Counting Maps of Given Genus, Europ. J. Combinatorics (1998) 19 819-834.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I, J. Comb. Theory B 13 (1972), 192-218 (Tab.1).
Liang Zhao and Fengyao Yan, Note on Total Positivity for a Class of Recursive Matrices, Journal of Integer Sequences, Vol. 19 (2016), Article 16.6.5.
Notes.

Cf. A035309, A000108 (for genus 0 maps), A046521 (third column).
Cf. A000984, A000911, A002457, A002697, A051133.
Column g=1 of A370235.

F:=Factorial;; List([0..25], n-> F(2*n+3)/(6*F(n)*F(n+1)) ); # G. C. Greubel, Jul 20 2019

F:=Factorial; [F(2*n+3)/(6*F(n)*F(n+1)): n in [0..25]]; // G. C. Greubel, Jul 20 2019

seq(simplify(4^n*hypergeom([-n,-3/2], [1], 1)),n=0..25); # Peter Luschny, Apr 26 2016

Table[(2*n+3)!/(6*n!*(n+1)!), {n, 0, 25}] (* Vladimir Joseph Stephan Orlovsky, Dec 13 2008 *)

{a(n) = if( n<0, 0, (2*n + 3)! / (6 * n! * (n+1)!))}; /* Michael Somos, Sep 16 2013 */

{a(n) = 2^(n+3) * polcoeff( pollegendre(n+4), n) / 3}; /* Michael Somos, Sep 16 2013 */

f=factorial; [f(2*n+3)/(6*f(n)*f(n+1)) for n in (0..25)] # G. C. Greubel, Jul 20 2019

G.f.: (1 - 4*x)^(-5/2) = 1F0(5/2;;4x).
Asymptotic expression for a(n) is a(n) ~ (n+2)^(3/2) * 4^(n+2) / (sqrt(Pi) * 48).
a(n) = Sum_{a+b+c+d+e=n} f(a)*f(b)*f(c)*f(d)*f(e) with f(n) = binomial(2n, n) = A000984(n). - Philippe Deléham, Jan 22 2004
a(n-1) = (1/4)*Sum_{k=1..n} k*(k+1)*binomial(2*k, k). - Benoit Cloitre, Mar 20 2004
a(n) = A051133(n+1)/3 = A000911(n)/6. - Zerinvary Lajos, Jun 02 2007
From Rui Duarte, Oct 08 2011: (Start)
Also convolution of A000984 with A002697, also convolution of A000302 with A002457.
a(n) = ((2n+3)(2n+1)/(3*1)) * binomial(2n, n).
a(n) = binomial(2n+4, 4) * binomial(2n, n) / binomial(n+2, 2).
a(n) = binomial(n+2, 2) * binomial(2n+4, n+2) / binomial(4, 2).
a(n) = binomial(2n+4, n+2) * (n+2)*(n+1) / 12. (End)
D-finite with recurrence: n*a(n) - 2*(2*n+3)*a(n-1) = 0. - R. J. Mathar, Jan 31 2014
a(n) = 4^n*hypergeom([-n,-3/2], [1], 1). - Peter Luschny, Apr 26 2016
Boas-Buck recurrence: a(n) = (10/n)*Sum_{k=0..n-1} 4^(n-k-1)*a(k), n >= 1, a(0) = 1. Proof from a(n) = A046521(n+2, 2). See a comment there. - Wolfdieter Lang, Aug 10 2017
a(n) = (-4)^n*binomial(-5/2, n). - Peter Luschny, Oct 23 2018
Sum_{n>=0} 1/a(n) = 12 - 2*sqrt(3)*Pi. - Amiram Eldar, Oct 13 2020
E.g.f.: (1/12) exp(2 x) x^2 BesselI[2, 2 x]. - Robert Coquereaux, Feb 12 2024

A075677 Reduced Collatz function R applied to the odd integers: a(n) = R(2n-1), where R(k) = (3k+1)/2^r, with r as large as possible.

Original entry on oeis.org

1, 5, 1, 11, 7, 17, 5, 23, 13, 29, 1, 35, 19, 41, 11, 47, 25, 53, 7, 59, 31, 65, 17, 71, 37, 77, 5, 83, 43, 89, 23, 95, 49, 101, 13, 107, 55, 113, 29, 119, 61, 125, 1, 131, 67, 137, 35, 143, 73, 149, 19, 155, 79, 161, 41, 167, 85, 173, 11, 179, 91, 185, 47, 191, 97, 197

Offset: 1

T. D. Noe, Sep 25 2002

The even-indexed terms a(2i+2) = 6i+5 = A016969(i), i >= 0 [Comment corrected by Bob Selcoe, Apr 06 2015]. The odd-indexed terms are the same as A067745. Note that this sequence is A016789 with all factors of 2 removed from each term. Also note that a(4i-1) = a(i). No multiple of 3 is in this sequence. See A075680 for the number of iterations of R required to yield 1.
From Bob Selcoe, Apr 06 2015: (Start)
All numbers in this sequence appear infinitely often.
From Eq. 1 and Eq. 2 in Formulas: Eq. 1 is used with 1/3 of the numbers in this sequence, Eq. 2 is used with 2/3 of the numbers.
(End)
Empirical: For arbitrary m, Sum_{n=2..A007583(m)} (a(n) - a(n-1)) = 0. - Fred Daniel Kline, Nov 23 2015
From Wolfdieter Lang, Dec 07 2021: (Start)
Only positive numbers congruent to 1 or 5 modulo 6 appear.
i) For the sequence entry with value A016921(m), for m >= 0, that is, a value from {1, 7, 13, ...}, the indices n are given by the row of array A178415(2*m+1, k), for k >= 1.
ii) For the sequence entry with value A007528(m), for m >= 1, that is, a value from {5, 11, 17, ...}, the indices n are given by the row of array A178415(2*m, k), for k >= 1.
See also the array A347834 with permuted row numbers and columns k >= 0. (End)

			a(11) = 1 because 21 is the 11th odd number and R(21) = 64/64 = 1.
From _Wolfdieter Lang_, Dec 07 2021: (Start)
i) 1 (mod 6) entry 1 = A016921(0) appears for n = A178415(1, k) = A347834(1, k-1) (the arrays), for k >= 1, that is, for {1, 5, 21, ..} = A002450.
ii) 5 (mod 6) entry 11 = A007528(2) appears for n = A178415(4, k) = A347835(3, k-1) (the arrays), for k >= 1, that is, for {7, 29, 117, ..} = A072261. (End)

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E16, pp. 330-336.
Victor Klee and Stan Wagon, Old and new unsolved problems in plane geometry and number theory, The Mathematical Association of America, 1991, p. 225, C(2n+1) = a(n+1), n >= 0.
Jeffrey C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 57, also (90-9), p. 306.

T. D. Noe, Table of n, a(n) for n = 1..1000
Marc Chamberland, Una actualizacio del problema 3x + 1, Butl. Soc. Catalana Mat. (18), 19-45, 2003.
Jeffrey C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Fabian S. Reid, The Visual Pattern in the Collatz Conjecture and Proof of No Non-Trivial Cycles, arXiv:2105.07955 [math.GM], 2021.
Eric Weisstein's World of Mathematics, Collatz Problem.
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A000265, A000302, A002450, A007528, A016789, A016921, A016969, A065677, A072197, A072261, A075680, A081294, A178415, A191669, A329480, A347834.
Cf. A006370, A014682 (for non-reduced Collatz maps), A087230 (A371093), A371094.
Odd bisection of A139391.
Even bisection of A067745, which is also the odd bisection of this sequence.
After the initial 1, the second leftmost column of A256598.
Row 2 of A372283.

a075677 = a000265 . subtract 2 . (* 6) -- Reinhard Zumkeller, Jan 08 2014

f:=proc(n) local t1;
if n=1 then RETURN(1) else
t1:=3*n+1;
while t1 mod 2 = 0 do t1:=t1/2; od;
RETURN(t1); fi;
end;
# N. J. A. Sloane, Jan 21 2011

nextOddK[n_] := Module[{m=3n+1}, While[EvenQ[m], m=m/2]; m]; (* assumes odd n *) Table[nextOddK[n], {n, 1, 200, 2}]
v[x_] := IntegerExponent[x, 2]; f[x_] := (3*x + 1)/2^v[3*x + 1]; Table[f[2*n - 1], {n, 66}] (* L. Edson Jeffery, May 06 2015 *)

a(n)=n+=2*n-1;n>>valuation(n,2) \\ Charles R Greathouse IV, Jul 05 2013

from sympy import divisors
def a(n):
    return max(d for d in divisors(n) if d % 2)
print([a(6*n - 2) for n in range(1, 101)]) # Indranil Ghosh, Apr 15 2017, after formula by Reinhard Zumkeller

a(n) = A000265(6*n-2) = A000265(3*n-1). - Reinhard Zumkeller, Jan 08 2014
From Bob Selcoe, Apr 05 2015: (Start)
For all n>=1 and for every k, there exists j>=0 dependent upon n and k such that either:
Eq. 1: a(n) = (3n-1)/2^(2j+1) when k = ((4^(j+1)-1)/3) mod 2^(2j+3). Alternatively: a(n) = A016789(n-1)/A081294(j+1) when k = A002450(j+1) mod A081294(j+2). Example: n=51; k=101 == 5 mod 32, j=1. a(51) = 152/8 = 19.
  or
Eq. 2: a(n) = (3n-1)/4^j when k = (5*2^(2j+1) - 1)/3 mod 4^(j+1). Alternatively: a(n) = A016789(n-1)/A000302(j) when k = A072197(j) mod A000302(j+1). Example: n=91; k=181 == 53 mod 64, j=2. a(91) = 272/16 = 17.
(End) [Definition corrected by William S. Hilton, Jul 29 2017]
a(n) = a(n + g*2^r) - 6*g, n > -g*2^r. Examples: n=59; a(59)=11, r=5. g=-1: 11 = a(27) = 5 - (-1)*6; g=1: 11 = a(91) = 17 - 1*6; g=2: 11 = a(123) = 23 - 2*6; g=3: 11 = a(155) = 29 - 3*6; etc. - Bob Selcoe, Apr 06 2015
a(n) = a((1 + (3*n - 1)*4^(k-1))/3), k>=1 (cf. A191669). - L. Edson Jeffery, Oct 05 2015
a(n) = a(4n-1). - Bob Selcoe, Aug 03 2017
a(n) = A139391(2n-1). - Antti Karttunen, May 06 2024
Sum_{k=1..n} a(k) ~ n^2. - Amiram Eldar, Aug 26 2024
G.f.: Sum_{k>=1} ((3 + 2*(-1)^k)*x^(3*2^(k - 1) - (-2)^k/3 + 1/3) + (3 - 2*(-1)^k)*x^(2^(k - 1) - (-2)^k/3 + 1/3))/(x^(2^k) - 1)^2. - Miles Wilson, Oct 26 2024

A047053 a(n) = 4^n * n!.

Original entry on oeis.org

1, 4, 32, 384, 6144, 122880, 2949120, 82575360, 2642411520, 95126814720, 3805072588800, 167423193907200, 8036313307545600, 417888291992371200, 23401744351572787200, 1404104661094367232000, 89862698310039502848000

Offset: 0

Joe Keane (jgk(AT)jgk.org)

Original name was "Quadruple factorial numbers".
For n >= 1, a(n) is the order of the wreath product of the cyclic group C_4 and the symmetric group S_n. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 07 2001
Number of n X n monomial matrices with entries 0, +/-1, +/-i.
a(n) is the product of the positive integers <= 4*n that are multiples of 4. - Peter Luschny, Jun 23 2011
Also, a(n) is the number of signed permutations of length 2*n that are equal to their reverse-complements. (See the Hardt and Troyka reference.) - Justin M. Troyka, Aug 13 2011.
Pi^n/a(n) is the volume of a 2*n-dimensional ball with radius 1/2. - Peter Luschny, Jul 24 2012
Equals the first right hand column of A167557, and also equals the first right hand column of A167569. - Johannes W. Meijer, Nov 12 2009
a(n) is the order of the group U_n(Z[i]) = {A in M_n(Z[i]): A*A^H = I_n}, the group of n X n unitary matrices over the Gaussian integers. Here A^H is the conjugate transpose of A. - Jianing Song, Mar 29 2021

			G.f. = 1 + 4*x + 32*x^2 + 384*x^3 + 6144*x^4 + 122880*x^5 + 2949120*x^6 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..100
R. B. Brent, Generalizing Tuenter's Binomial Sums, J. Int. Seq. 18 (2015), # 15.3.2.
CombOS - Combinatorial Object Server, Generate colored permutations
R. Coquereaux and J.-B. Zuber, Maps, immersions and permutations, arXiv preprint arXiv:1507.03163 [math.CO], 2015-2016. Also J. Knot Theory Ramifications 25, 1650047 (2016), DOI.
Sylvie Corteel and Lauren Williams, Tableaux Combinatorics for the Asymmetric Exclusion Process II, arXiv:0810.2916 [math.CO], 2008-2009.
A. Hardt and J. M. Troyka, Restricted symmetric signed permutations, Pure Mathematics and Applications, Vol. 23 (No. 3, 2012), pp. 179-217.
A. Hardt and J. M. Troyka, Slides (associated with the Hardt and Troyka reference above).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 492.
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, 5 (2002), Article 02.1.7.
M. D. Schmidt, Generalized j-Factorial Functions, Polynomials, and Applications, J. Int. Seq. 13 (2010), Article 10.6.7, p. 39.
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, 9 (2006), Article 06.1.1.

Cf. A000142, A000165, A007696, A008545, A032031, A047058, A087299, A092042, A092616.

a(n)= A051142(n+1, 0) (first column of triangle).

[4^n*Factorial(n): n in [0..20]]; // Vincenzo Librandi, Jul 20 2011

A047053:= n -> mul(k, k = select(k-> k mod 4 = 0, [$1..4*n])): seq(A047053(n), n = 0.. 16); # Peter Luschny, Jun 23 2011

a[n_]:= With[{m=2n}, If[ m<0, 0, m!*SeriesCoefficient[1 +Sqrt[Pi]*x*Exp[x^2]*Erf[x], {x, 0, m}]]]; (* Michael Somos, Jan 03 2015 *)
Table[4^n n!,{n,0,20}] (* Harvey P. Dale, Sep 19 2021 *)

PARI
```
a(n)=4^n*n!;
```

a(n) = 4^n * n!.
E.g.f.: 1/(1 - 4*x).
Integral representation as the n-th moment of a positive function on a positive half-axis: a(n) = Integral_{x=0..oo} x^n*exp(-x/4)/4, n >= 0. This representation is unique. - Karol A. Penson, Jan 28 2002 [corrected by Jason Yuen, May 04 2025]
Sum_{k>=0} (-1)^k/(2*k + 1)^n = (-1)^n * n * (PolyGamma[n-1, 1/4] - PolyGamma[n-1, 3/4]) / a(n) for n > 0. - Joseph Biberstine (jrbibers(AT)indiana.edu), Jul 27 2006
a(n) = Sum_{k=0..n} C(n,k)*(2k)!*(2(n-k))!/(k!(n-k)!) = Sum_{k=0..n} C(n,k)*A001813(k)*A001813(n-k). - Paul Barry, May 04 2007
E.g.f.: With interpolated zeros, 1 + sqrt(Pi)*x*exp(x^2)*erf(x). - Paul Barry, Apr 10 2010
From Gary W. Adamson, Jul 19 2011: (Start)
a(n) = sum of top row terms of M^n, M = an infinite square production matrix as follows:
  2, 2, 0, 0, 0, 0, ...
  4, 4, 4, 0, 0, 0, ...
  6, 6, 6, 6, 0, 0, ...
  8, 8, 8, 8, 8, 0, ...
  ... (End)
G.f.: 1/(1 - 4*x/(1 - 4*x/(1 - 8*x/(1 - 8*x/(1 - 12*x/(1 - 12*x/(1 - 16*x/(1 - ... (continued fraction). - Philippe Deléham, Jan 08 2012
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 8*x*(k + 1)/(8*x*(k + 1) - 1 + 8*x*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 30 2013
G.f.: 1/Q(0), where Q(k) = 1 - 4*x*(2*k + 1) - 16*x^2*(k + 1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Sep 28 2013
a(n) = A000142(n) * A000302(n). - Michel Marcus, Nov 28 2013
a(n) = A087299(2*n). - Michael Somos, Jan 03 2015
D-finite with recurrence: a(n) - 4*n*a(n-1) = 0. - R. J. Mathar, Jan 27 2020
From Amiram Eldar, Jun 25 2020: (Start)
Sum_{n>=0} 1/a(n) = e^(1/4) (A092042).
Sum_{n>=0} (-1)^n/a(n) = e^(-1/4) (A092616). (End)

Edited by Karol A. Penson, Jan 22 2002

A102376 a(n) = 4^A000120(n).

Original entry on oeis.org

1, 4, 4, 16, 4, 16, 16, 64, 4, 16, 16, 64, 16, 64, 64, 256, 4, 16, 16, 64, 16, 64, 64, 256, 16, 64, 64, 256, 64, 256, 256, 1024, 4, 16, 16, 64, 16, 64, 64, 256, 16, 64, 64, 256, 64, 256, 256, 1024, 16, 64, 64, 256, 64, 256, 256, 1024, 64, 256, 256, 1024, 256, 1024, 1024

Offset: 0

Paul Barry, Jan 05 2005

Consider a simple cellular automaton, a grid of binary cells c(i,j), where the next state of the grid is calculated by applying the following rule to each cell: c(i,j) = ( c(i+1,j-1) + c(i+1,j+1) + c(i-1,j-1) + c(i-1,j+1) ) mod 2 If we start with a single cell having the value 1 and all the others 0, then the aggregate values of the subsequent states of the grid will be the terms in this sequence. - Andras Erszegi (erszegi.andras(AT)chello.hu), Mar 31 2006. See link for initial states. - N. J. A. Sloane, Feb 12 2015
This is the odd-rule cellular automaton defined by OddRule 033 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
First differences of A116520. - Omar E. Pol, May 05 2010

			1 + 4*x + 4*x^2 + 16*x^3 + 4*x^4 + 16*x^5 + 16*x^6 + 64*x^7 + 4*x^8 + ...
From _Omar E. Pol_, Jun 07 2009: (Start)
Triangle begins:
  1;
  4;
  4,16;
  4,16,16,64;
  4,16,16,64,16,64,64,256;
  4,16,16,64,16,64,64,256,16,64,64,256,64,256,256,1024;
  4,16,16,64,16,64,64,256,16,64,64,256,64,256,256,1024,16,64,64,256,64,256,...
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
David Applegate, Omar E. Pol, and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
Nathan Epstein, Animation of CA generating A102376
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Illustration of generations 0-15 of the cellular automaton
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 13.
Index entries for sequences related to cellular automata

For generating functions Prod_{k>=0} (1+a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
A151783 is a very similar sequence.
Cf. A001316, A048883, A000079, A116520, A000302.
See A160239 for the analogous CA defined by Rule 204 on an 8-celled neighborhood.

a102376 = (4 ^) . a000120  -- Reinhard Zumkeller, Feb 13 2015

seq(4^convert(convert(n,base,2),`+`),n=0..100); # Robert Israel, Apr 30 2017

Table[4^DigitCount[n, 2, 1], {n, 0, 100}] (* Indranil Ghosh, Apr 30 2017 *)

{a(n) = if( n<0, 0, 4^subst( Pol( binary(n)), x, 1))} /* Michael Somos, May 29 2008 */
a(n) = 4^hammingweight(n); \\ Michel Marcus, Apr 30 2017

def a(n): return 4**bin(n)[2:].count("1") # Indranil Ghosh, Apr 30 2017

def A102376(n): return 1<<(n.bit_count()<<1) # Chai Wah Wu, Nov 15 2022

Formulas due to Paul D. Hanna: (Start)
G.f.: Product_{k>=0} 1 + 4x^(2^k).
a(n) = Product_{k=0..log_2(n)} 4^b(n, k), b(n, k)=coefficient of 2^k in binary expansion of n.
a(n) = Sum_{k=0..n} (C(n, k) mod 2)*3^A000120(n-k). (End)
a(n) = Sum_{k=0..n} (C(n, k) mod 2) * Sum_{j=0..k} (C(k, j) mod 2) * Sum_{i=0..j} (C(j, i) mod 2). - Paul Barry, Apr 01 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = w * (u^2 - 2*u*v + 5*v^2) - 4*v^3. - Michael Somos, May 29 2008
Run length transform of A000302. - N. J. A. Sloane, Feb 23 2015

A020522 a(n) = 4^n - 2^n.

Original entry on oeis.org

0, 2, 12, 56, 240, 992, 4032, 16256, 65280, 261632, 1047552, 4192256, 16773120, 67100672, 268419072, 1073709056, 4294901760, 17179738112, 68719214592, 274877382656, 1099510579200, 4398044413952, 17592181850112, 70368735789056, 281474959933440

Offset: 0

N. J. A. Sloane, Simon Plouffe

Number of walks of length 2*n+2 between any two diametrically opposite vertices of the cycle graph C_8. - Herbert Kociemba, Jul 02 2004
If we consider a(4*k+2), then 2^4 == 3^4 == 3 (mod 13); 2^(4*k+2) + 3^(4*k+2) == 3^k*(4+9) == 3*0 == 0 (mod 13). So a(4*k+2) can never be prime. - Jose Brox, Dec 27 2005
If k is odd, then a(n*k) is divisible by a(n), since: a(n*k) = (2^n)^k + (3^n)^k = (2^n + 3^n)*((2^n)^(k-1) - (2^n)^(k-2) (3^n) + - ... + (3^n)^(k-1)). So the only possible primes in the sequence are a(0) and a(2^n) for n>=1. I've checked that a(2^n) is composite for 3 <= n <= 15. As with Fermat primes, a probabilistic argument suggests that there are only finitely many primes in the sequence. - Dean Hickerson, Dec 27 2005
Let x,y,z be elements from some power set P(n), i.e., the power set of a set of n elements. Define a function f(x,y,z) in the following manner: f(x,y,z) = 1 if x is a subset of y and y is a subset of z and x does not equal z; f(x,y,z) = 0 if x is not a subset of y or y is not a subset of z or x equals z. Now sum f(x,y,z) for all x,y,z of P(n). This gives a(n). - Ross La Haye, Dec 26 2005
Number of monic (irreducible) polynomials of degree 1 over GF(2^n). - Max Alekseyev, Jan 13 2006
Let P(A) be the power set of an n-element set A and B be the Cartesian product of P(A) with itself. Then a(n) = the number of (x,y) of B for which x does not equal y. - Ross La Haye, Jan 02 2008
For n>1: central terms of the triangle in A173787. - Reinhard Zumkeller, Feb 28 2010
Pronic numbers of the form: (2^n - 1)*2^n, which is the n-th Mersenne number times 2^n, see A000225 and A002378. - Fred Daniel Kline, Nov 30 2013
Indices where records of A037870 occur. - Philippe Beaudoin, Sep 03 2014
Half the total edge length for a minimum linear arrangement of a hypercube of dimension n. (See Harper's paper below for proof). - Eitan Frachtenberg, Apr 07 2017
Number of pairs in GF(2)^{n+1} whose dot product is 1. - Christopher Purcell, Dec 11 2021

			n=5: a(5) = 4^5 - 2^5 = 1024 - 32 = 992 -> '1111100000'.

Vincenzo Librandi, Table of n, a(n) for n = 0..170
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.
Tom Copeland, The Kervaire-Milnor formula
John Elias, Illustration of initial terms: Twin 2^n hexagonal numbers
L. H. Harper, Optimal Assignment of Numbers to Vertices, J. SIAM 12(1), p. 131--135, March 1964; alternative link.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
The Sixtieth William Lowell Putnam Mathematical Competition, Question A6, Amer. Math. Monthly 107 (Oct 2000), 721-732; see p. 725.
Index entries for linear recurrences with constant coefficients, signature (6,-8).

Ratio of successive terms of A028365.
Cf. A000225, A060867, A161168, A006516, A059153, A065442.
Cf. A000079, A265736, A020988, A047849.
Cf. A000079, A000302.

a020522 = (* 2) . a006516  -- Reinhard Zumkeller, Dec 15 2015

[4^n - 2^n: n in [0..60]]; // Vincenzo Librandi, Apr 26 2011

A020522:=n->4^n-2^n; seq(A020522(n), n=0..50); # Wesley Ivan Hurt, Nov 29 2013

Table[4^n - 2^n, {n, 40}] (* or *) LinearRecurrence[{6, -8}, {0, 2}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2012 *)

a(n)=4^n-2^n \\ Charles R Greathouse IV, Jan 30 2012

def A020522(n): return (1<Chai Wah Wu, Mar 10 2025

[4^n - 2^n for n in range(0,23)] # Zerinvary Lajos, Jun 05 2009

From Herbert Kociemba, Jul 02 2004: (Start)
G.f.: 2*x/((-1 + 2*x)*(-1 + 4*x)).
a(n) = 6*a(n-1) - 8*a(n-2). (End)
E.g.f.: exp(4*x) - exp(2*x). - Mohammad K. Azarian, Jan 14 2009
From Reinhard Zumkeller, Feb 07 2006, Jaroslav Krizek, Aug 02 2009: (Start)
a(n) = A099393(n)-A000225(n+1) = A083420(n)-A099393(n).
In binary representation, n>0: n 1's followed by n 0's (A138147(n)).
A000120(a(n)) = n.
A023416(a(n)) = n.
A070939(a(n)) = 2*n.
2*a(n)+1 = A030101(A099393(n)). (End)
a(n) = A085812(n) - A001700(n). - John Molokach, Sep 28 2013
a(n) = 2*A006516(n) = A000079(n)*A000225(n) = A265736(A000225(n)). - Reinhard Zumkeller, Dec 15 2015
a(n) = (4^(n/2) - 4^(n/4))*(4^(n/2) + 4^(n/4)). - Bruno Berselli, Apr 09 2018
Sum_{n>0} 1/a(n) = E - 1, where E is the Erdős-Borwein constant (A065442). - Peter McNair, Dec 19 2022
a(n) = A000302(n) - A000079(n). - John Reimer Morales, Aug 04 2025

A114121 Expansion of (sqrt(1 - 4x) + (1 - 2x))/(2(1 - 4x)).

Original entry on oeis.org

1, 2, 7, 26, 99, 382, 1486, 5812, 22819, 89846, 354522, 1401292, 5546382, 21977516, 87167164, 345994216, 1374282019, 5461770406, 21717436834, 86392108636, 343801171354, 1368640564996, 5450095992964, 21708901408216, 86492546019214

Offset: 0

Paul Barry, Feb 13 2006

Second binomial transform of A032443 with interpolated zeros.
a(n) is the total number of lattice points, taken over all Dyck n-paths (A000108), that (i) lie on or above ground level and (ii) lie on or directly below a peak. For example with n = 2, UUDD has 1 peak contributing 3 lattice points--(2, 0), (2, 1) and (2, 2) when the path starts at the origin--and UDUD has 2 peaks, each contributing 2 lattice points and so a(2) = 3 + 4 = 7. - David Callan, Jul 14 2006
Hankel transform is binomial(n + 2, 2). - Paul Barry, Dec 04 2007
Image of (-1)^n under the Riordan array ((1/2)(1/(1 - 4x) + 1/sqrt(1 - 4x)), c(x) - 1), c(x) the g.f. of A000108. - Paul Barry, Jun 15 2008
From Gus Wiseman, Jun 21 2021: (Start)
Also the even bisection of A116406 = number compositions of n with alternating sum >= 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. The a(3) = 26 compositions are:
  (6)  (33)  (114)  (1122)  (11112)  (111111)
       (42)  (123)  (1131)  (11121)
       (51)  (132)  (1221)  (11211)
             (213)  (2112)  (12111)
             (222)  (2121)  (21111)
             (231)  (2211)
             (312)  (3111)
             (321)
             (411)
(End)

			G.f. = 1 + 2*x + 7*x^2 + 26*x^3 + 99*x^4 + 382*x^5 + 1486*x^6 + 5812*x^7 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000
G.-S. Cheon, H. Kim, L. W. Shapiro, Mutation effects in ordered trees, arXiv:1410.1249 [math.CO], 2014
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

Cf. A000984, A081294, A088218.
The case of alternating sum = 0 is A001700.
The case of alternating sum < 0 is A008549.
This is the even bisection of A116406.
The restriction to reversed partitions is A344611.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A124754 gives the alternating sum of standard compositions.
A316524 is the alternating sum of the prime indices of n.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
Cf. A000041, A000070, A000302, A000346, A003242, A027306, A032443, A058622, A058696, A119899, A344607, A344610.

seq(sum(binomial(2*n,2*k+irem(n,2)),k=0..floor((1/2)*n)),n=0..20)
seq(binomial(2*n-1,n)+4^(n-1)-(1/4)*0^n,n=0..20)

a[ n_] := SeriesCoefficient[((1 + 1/Sqrt[1 - 4 x])/2)^2, {x, 0, n}] (* Michael Somos, Dec 31 2013 *)
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],ats[#]>=0&]],{n,0,15,2}] (* Gus Wiseman, Jun 21 2021 *)

a(n) = Sum_{k=0..n} C(n, k)*2^(n-k-2)*(2^k + C(k, k/2))*(1 + (-1)^k).
a(n) = (A000984(n) + A081294(n))/2.
From Paul Barry, Jun 15 2008: (Start)
G.f.: (1 - 4*x + (1 - 2*x)*sqrt(1 - 4*x))/(2*(1 - 4*x)^(3/2)).
a(n) = Sum_{k=0..n} ( Sum_{j=0..n} C(2*n, n-k-j)*(-1)^j ). (End)
a(n) = Sum_{k=0..n} C(2*n, n-k)*(1 + (-1)^k)/2. - Paul Barry, Aug 06 2009
From Paul Barry, Sep 07 2009: (Start)
a(n) = C(2*n-1, n-1) + (4^n + 3*0^n)/4.
Integral representation a(n) = (1/(2*pi))*(Integral_{x=0..4} x^n/sqrt(x(4 - x))) + (4^n + 0^n)/4. (End)
a(n) = Sum_{k=0..floor(n/2)} C(2*n, 2*k + (n mod 2)). - Mircea Merca, Jun 21 2011
Conjecture: n*a(n) + 2*(3 - 4*n)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Nov 07 2012
Conjecture verified using the differential equation (16*x^2-8*x+1)*g'(x) + (8*x-2)*g(x)-2*x=0 satisfied by the G.f. - Robert Israel, Jul 27 2020
a(n) = Sum_{i=0..n} (sum_{j=0..n} binomial(n, i+j)*binomial(n, j-i)). - Yalcin Aktar, Jan 07 2013.
G.f.: (1 + (1 - 4*x)^(-1/2))^2 / 4. Convolution square of A088218. - Michael Somos, Dec 31 2013
0 = (1 + 2*n)*b(n) - (5 + 4*n)*b(n+1) + (4 + 2*n)*b(n+2) if n > 0 where b(n) = a(n) / 4^n. - Michael Somos, Dec 31 2013
0 = b(n+3) * (2*b(n+2) - 7*b(n+1) + 5*b(n)) + b(n+2) * (-b(n+2) + 7*b(n+1) - 7*b(n)) + b(n+1) * (-b(n+1) + 2*b(n)) if n > 0 where b(n) = a(n) / 4^n. - Michael Somos, Dec 31 2013
For n > 0, a(n) = 2^(2n-1) - A008549(n). - Gus Wiseman, Jun 27 2021
a(n) = [x^n] 1/((1-2*x) * (1-x)^(n-1)). - Seiichi Manyama, Apr 10 2024

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

Original entry on oeis.org

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

A009964 Powers of 20.

Original entry on oeis.org

1, 20, 400, 8000, 160000, 3200000, 64000000, 1280000000, 25600000000, 512000000000, 10240000000000, 204800000000000, 4096000000000000, 81920000000000000, 1638400000000000000, 32768000000000000000

Offset: 0

N. J. A. Sloane

Same as Pisot sequences E(1, 20), L(1, 20), P(1, 20), T(1, 20). Essentially same as Pisot sequences E(20, 400), L(20, 400), P(20, 400), T(20, 400). See A008776 for definitions of Pisot sequences.
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 20-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
a(n) gives the number of small cubes in the n-th iteration of the Menger sponge fractal. - Felix Fröhlich, Jul 09 2016
Equivalently, the number of vertices in the n-Menger sponge graph.

T. D. Noe, Table of n, a(n) for n = 0..100
Allan Bickle, Degrees of Menger and Sierpinski Graphs, Congr. Num. 227 (2016) 197-208.
Allan Bickle, MegaMenger Graphs, The College Mathematics Journal, 49 1 (2018) 20-26.
Tanya Khovanova, Recursive Sequences
Eric Weisstein's World of Mathematics, Menger Sponge
Eric Weisstein's World of Mathematics, Menger Sponge Graph
Eric Weisstein's World of Mathematics, Vertex Count
Wikipedia, Menger sponge
Index entries for linear recurrences with constant coefficients, signature (20).

Cf. A291066 (edge count).
Cf. A000079, A011557; A000302, A000351; A000244, A159991.
Cf. A291066, A083233, and A332705 on the surface area of the n-Menger sponge graph.

List([0..20],n->20^n); # Muniru A Asiru, Nov 21 2018

[20^n: n in [0..100]] // Vincenzo Librandi, Nov 21 2010

[20^n$n=0..20]; # Muniru A Asiru, Nov 21 2018

20^Range[0, 10] (* or *) LinearRecurrence[{20}, {1}, 20] (* Eric W. Weisstein, Aug 17 2017 *)

makelist(20^n,n,0,30); /* Martin Ettl, Nov 05 2012 */

a(n)=20^n \\ Charles R Greathouse IV, Jun 19 2015

powers(20,12) \\ Charles R Greathouse IV, Jun 19 2015

[20**n for n in range(21)] # Stefano Spezia, Nov 21 2018

[20^n for n in range(21)] # Zerinvary Lajos, Apr 29 2009

G.f.: 1/(1-20*x).
E.g.f.: exp(20*x).
a(n) = A159991(n)/A000244(n). - Reinhard Zumkeller, May 02 2009
From Vincenzo Librandi, Nov 21 2010: (Start)
a(n) = 20^n.
a(n) = 20*a(n-1) for n > 0, a(0) = 1. (End)
a(n) = A000079(n)*A011557(n) = A000302(n)*A000351(n). - Felix Fröhlich, Jul 09 2016

A046521 Array T(i,j) = binomial(-1/2-i,j)*(-4)^j, i,j >= 0 read by antidiagonals going down.

Original entry on oeis.org

1, 2, 1, 6, 6, 1, 20, 30, 10, 1, 70, 140, 70, 14, 1, 252, 630, 420, 126, 18, 1, 924, 2772, 2310, 924, 198, 22, 1, 3432, 12012, 12012, 6006, 1716, 286, 26, 1, 12870, 51480, 60060, 36036, 12870, 2860, 390, 30, 1, 48620, 218790, 291720, 204204, 87516, 24310

Offset: 0

Wolfdieter Lang

Or, a triangle related to A000984 (central binomial) and A000302 (powers of 4).
This is an example of a Riordan matrix. See the Shapiro et al. reference quoted under A053121 and Notes 1 and 2 of the Wolfdieter Lang reference, p. 306.
As a number triangle, this is the Riordan array (1/sqrt(1-4x),x/(1-4x)). - Paul Barry, May 30 2005
The A- and Z- sequences for this Riordan matrix are (see the Wolfdieter Lang link under A006232 for the D. G. Rogers, D. Merlini et al. and R. Sprugnoli references on Riordan A- and Z-sequences with a summary): A-sequence [1,4,0,0,0,...] and Z-sequence 4+2*A000108(n)*(-1)^(n+1)=[2, 2, -4, 10, -28, 84, -264, 858, -2860, 9724, -33592, 117572, -416024, 1485800, -5348880, 19389690, -70715340, 259289580, -955277400, 3534526380], n >= 0. The o.g.f. for the Z-sequence is 4-2*c(-x) with the Catalan number o.g.f. c(x). - Wolfdieter Lang, Jun 01 2007
As a triangle, T(2n,n) is A001448. Row sums are A046748. Diagonal sums are A176280. - Paul Barry, Apr 14 2010
From Wolfdieter Lang, Aug 10 2017: (Start)
The row polynomials R(n, x) of Riordan triangles R = (G(x), F(x)), with F(x)= x*Fhat(x), belong to the class of Boas-Buck polynomials (see the reference). Hence they satisfy the Boas-Buck identity (we use the notation of Rainville, Theorem 50, p. 141):
  (E_x - n*1)*R(n, x) = -Sum_{k=0..n-1} (alpha(k)*1 + beta(k)*E_x)*R(n-1.k, x), for n >= 0, where E_x = x*d/dx (Euler operator). The Boas-Buck sequences are given by alpha(k) := [x^k] ((d/dx)log(G(x))) and beta(k) := [x^k] (d/dx)log(Fhat(x)).
This entails a recurrence for the sequence of column m of the Riordan triangle T, n > m >= 0: T(n, m) = (1/(n-m))*Sum_{k=m..n-1} (alpha(n-1-k) + m*beta(n-1-k))*T(k, m), with input T(m,m).
For the present case the Boas-Buck identity for the row polynomials is (E_x - n*1)*R(n, x) = -Sum_{k=0..n-1} 2^(2*k+1)*(1 + 2*E_x)*R(n-1-k, x), for n >= 0. For the ensuing recurrence for the columns m of the triangle T see the formula and example section. (End)
From Peter Bala, Mar 04 2018: (Start)
The following two remarks are particular cases of more general results for Riordan arrays of the form (f(x), x/(1 - k*x)).
1) Let R(n,x) denote the n-th row polynomial of this triangle. The polynomial R(n,4*x) has the e.g.f. Sum_{k = 0..n} T(n,k)*(4*x)/k!. The e.g.f. for the n-th diagonal of the triangle (starting at n = 0 for the main diagonal) equals exp(x) * the e.g.f. for the polynomial R(n,4*x). For example, when n = 3 we have exp(x)*(20 + 30*(4*x) + 10*(4*x)^2/2! + (4*x)^3/3!) = 20 + 140*x + 420*x^2/2! + 924*x^3/3! + 1716*x^4/4! + ....
2) Let P(n,x) = Sum_{k = 0..n} T(n,k)*x^(n-k) denote the n-th row polynomial in descending powers of x. P(n,x) is the n-th degree Taylor polynomial of (1 + 4*x)^(n-1/2) about 0. For example, for n = 4 we have (1 + 4*x)^(7/2) = 70*x^4 + 140*x^3 + 70*x^2 + 14*x + 1 + O(x^5).
Let C(x) = (1 - sqrt(1 - 4*x))/(2*x) denote the o.g.f. of the Catalan numbers A000108. The derivatives of C(x) are determined by the identity (-1)^n * x^n/n! * (d/dx)^n(C(x)) = 1/(2*x)*( 1 - P(n,-x)/(1 - 4*x)^(n-1/2) ), n = 0,1,2,.... See Lang 2002. Cf. A283150 and A283151. (End)

			Array begins:
  1,  2,   6,  20,   70, ...
  1,  6,  30, 140,  630, ...
  1, 10,  70, 420, 2310, ...
  1, 14, 126, 924, 6006, ...
Recurrence from A-sequence: 140 = a(4,1) = 20 + 4*30.
Recurrence from Z-sequence: 252 = a(5,0) = 2*70 + 2*140 - 4*70 + 10*14 - 28*1.
From _Paul Barry_, Apr 14 2010: (Start)
As a number triangle, T(n, m) begins:
n\k       0      1       2       3      4      5     6    7   8  9 10 ...
0:        1
1:        2      1
2:        6      6       1
3:       20     30      10       1
4:       70    140      70      14      1
5:      252    630     420     126     18      1
6:      924   2772    2310     924    198     22     1
7:     3432  12012   12012    6006   1716    286    26    1
8:    12870  51480   60060   36036  12870   2860   390   30   1
9:    48620 218790  291720  204204  87516  24310  4420  510  34  1
10:  184756 923780 1385670 1108536 554268 184756 41990 6460 646 38  1
... [Reformatted and extended by _Wolfdieter Lang_, Aug 10 2017]
Production matrix begins
      2, 1,
      2, 4, 1,
     -4, 0, 4, 1,
     10, 0, 0, 4, 1,
    -28, 0, 0, 0, 4, 1,
     84, 0, 0, 0, 0, 4, 1,
   -264, 0, 0, 0, 0, 0, 4, 1,
    858, 0, 0, 0, 0, 0, 0, 4, 1,
  -2860, 0, 0, 0, 0, 0, 0, 0, 4, 1 (End)
Boas-Buck recurrence for column m = 2, and n = 4: T(4, 2) = (2*(2*2+1)/2) * Sum_{k=2..3} 4^(3-k)*T(k, 2) = 5*(4*1 + 1*10) = 70. - _Wolfdieter Lang_, Aug 10 2017
From _Peter Bala_, Feb 15 2018: (Start)
With C(x) = (1 - sqrt( 1 - 4*x))/(2*x),
-x^3/3! * (d/dx)^3(C(x)) = 1/(2*x)*( 1 - (1 - 10*x + 30*x^2 - 20*x^3)/(1 - 4*x)^(5/2) ).
x^4/4! * (d/dx)^4(C(x)) = 1/(2*x)*( 1 - (1 - 14*x + 70*x^2 - 140*x^3 + 70*x^4 )/(1 - 4*x)^(7/2) ). (End)

Ralph P. Boas, jr. and R. Creighton Buck, Polynomial Expansions of analytic functions, Springer, 1958, pp. 17 - 21, (last sign in eq. (6.11) should be -).
Earl D. Rainville, Special Functions, The Macmillan Company, New York, 1960, ch. 8, sect. 76, 140 - 146.

Muniru A Asiru, Antidiagonals n = 0..50, flattened
Peter Bala, A 4-parameter family of embedded Riordan arrays
Peter Bala, A note on the diagonals of a proper Riordan Array
Paul Barry, Embedding structures associated with Riordan arrays and moment matrices, arXiv preprint arXiv:1312.0583 [math.CO], 2013.
Jonathan W. Bober, Factorial ratios, hypergeometric series, and a family of step functions, arXiv:0709.1977 [math.NT], 2007; J. London Math. Soc. (2) 79 2009, 422-444.
Wolfdieter Lang, First 10 rows.
Wolfdieter Lang, On polynomials related to derivatives of the generating function of Catalan numbers, Fib. Quart. 40,4 (2002) 299-313; T(n,m) is called B(n,m) there.
Benjamin Lovitz and Nathaniel Johnston, A hierarchy of eigencomputations for polynomial optimization on the sphere, arXiv:2310.17827 [math.OC], 2023. See pp. 35, 39. See also Math. Prog. (2025) Series A.
Helmut Prodinger, Some information about the binomial transform, The Fibonacci Quarterly, 32, 1994, 412-415.

Columns include: A000984 (m=0), A002457 (m=1), A002802 (m=2), A020918 (m=3), A020920 (m=4), A020922 (m=5), A020924 (m=6), A020926 (m=7), A020928 (m=8), A020930 (m=9), A020932 (m=10).
Row sums: A046748.
Cf. A001147, A006882, A007318, A068555, A111959, A283150, A283151.

Flat(List([0..9],n->List([0..n],m->Binomial(2*n,n)*Binomial(n,m)/Binomial(2*m,m)))); # Muniru A Asiru, Jul 19 2018

[Binomial(n+1,k+1)*Catalan(n)/Catalan(k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jul 28 2024

t[i_, j_] := If[i < 0 || j < 0, 0, (2*i + 2*j)!*i!/(2*i)!/(i + j)!/j!]; Flatten[Reverse /@ Table[t[n, k - n] , {k, 0, 9}, {n, k, 0, -1}]][[1 ;; 51]] (* Jean-François Alcover, Jun 01 2011, after PARI prog. *)

T(i,j)=if(i<0 || j<0,0,(2*i+2*j)!*i!/(2*i)!/(i+j)!/j!)

def A046521(n,k): return binomial(n+1, k+1)*catalan_number(n)/catalan_number(k)
flatten([[A046521(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jul 28 2024

T(n, m) = binomial(2*n, n)*binomial(n, m)/binomial(2*m, m), n >= m >= 0.
G.f. for column m: ((x/(1-4*x))^m)/sqrt(1-4*x).
Recurrence from the A-sequence given above: a(n,m) = a(n-1,m-1) + 4*a(n-1,m), for n >= m >= 1.
Recurrence from the Z-sequence given above: a(n,0) = Sum_{j=0..n-1} Z(j)*a(n-1,j), n >= 1; a(0,0)=1.
As a number triangle, T(n,k) = C(2*n,n)*C(n,k)/C(2*k,k) = C(n-1/2,n-k)*4^(n-k). - Paul Barry, Apr 14 2010
From Peter Bala, Apr 11 2012: (Start):
One of three infinite families of integral factorial ratio sequences of height 1 (see Bober, Theorem 1.2). The other two are A007318 and A068555.
The triangular array equals exp(S), where the infinitesimal generator S has [2,6,10,14,18,...] on the main subdiagonal and zeros elsewhere.
Recurrence equation for the square array: T(n+1,k) = (k+1)/(4*n+2)*T(n,k+1). (End)
T(n,k) = 4^(n-k)*A006882(2*n - 1)/(A006882(2*n - 2*k)*A006882(2*k - 1)) = 4^(n-k)*(2*n - 1)!!/((2*n - 2*k)!*(2*k - 1)!!). - Peter Bala, Nov 07 2016
Boas-Buck recurrence for column m, m > n >= 0: T(n, m) = (2*(2*m+1)/(n-m))*Sum_{k=m..n-1} 4^(n-1-k)*T(k, m), with input T(n, n) = 1. See a comment above. - Wolfdieter Lang, Aug 10 2017
From Peter Bala, Aug 13 2021: (Start)
Analogous to the binomial transform we have the following sequence transformation formula: g(n) = Sum_{k = 0..n} T(n,k)*b^(n-k)*f(k) iff f(n) = Sum_{k = 0..n} (-1)^(n-k)*T(n,k)*b^(n-k)*g(k). See Prodinger, bottom of p. 413, with b replaced with 4*b, c = 1 and d = 1/2.
Equivalently, if F(x) = Sum_{n >= 0} f(n)*x^n and G(x) = Sum_{n >= 0} g(n)*x^n are a pair of  formal power series then
G(x) = 1/sqrt(1 - 4*b*x) * F(x/(1 - 4*b*x)) iff F(x) = 1/sqrt(1 + 4*b*x) * G(x/(1 + 4*b*x)).
The m-th power of this array has entries m^(n-k)*T(n,k). (End)

A027465 Cube of lower triangular normalized binomial matrix.

Original entry on oeis.org

1, 3, 1, 9, 6, 1, 27, 27, 9, 1, 81, 108, 54, 12, 1, 243, 405, 270, 90, 15, 1, 729, 1458, 1215, 540, 135, 18, 1, 2187, 5103, 5103, 2835, 945, 189, 21, 1, 6561, 17496, 20412, 13608, 5670, 1512, 252, 24, 1, 19683, 59049, 78732, 61236, 30618, 10206, 2268

Offset: 0

Olivier Gérard, N. J. A. Sloane

Rows of A013610 reversed. - Michael Somos, Feb 14 2002
Row sums are powers of 4 (A000302), antidiagonal sums are A006190 (a(n) = 3*a(n-1) + a(n-2)). - Gerald McGarvey, May 17 2005
Triangle of coefficients in expansion of (3+x)^n.
Also: Pure Galton board of scheme (3,1). Also: Multiplicity (number) of pairs of n-dimensional binary vectors with dot product (overlap) k. There are 2^n = A000079(n) binary vectors of length n and 2^(2n) = 4^n = A000302(n) different pairs to form dot products k = Sum_{i=1..n} v[i]*u[i] between these, 0 <= k <= n. (Since dot products are symmetric, there are only 2^n*(2^n-1)/2 different non-ordered pairs, actually.) - R. J. Mathar, Mar 17 2006
Mirror image of A013610. - Zerinvary Lajos, Nov 25 2007
T(i,j) is the number of i-permutations of 4 objects a,b,c,d, with repetition allowed, containing j a's. - Zerinvary Lajos, Dec 21 2007
The antidiagonals of the sequence formatted as a square array (see Examples section) and summed with alternating signs gives a bisection of Fibonacci sequence, A001906. Example: 81-(27-1)=55. Similar rule applied to rows gives A000079. - Mark Dols, Sep 01 2009
Triangle T(n,k), read by rows, given by (3,0,0,0,0,0,0,0,...)DELTA (1,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 09 2011
T(n,k) = binomial(n,k)*3^(n-k), the number of subsets of [2n] with exactly k symmetric pairs, where elements i and j of [2n] form a symmetric pair if i+j=2n+1. Equivalently, if n couples attend a (ticketed) event that offers door prizes, then the number of possible prize distributions that have exactly k couples as dual winners is T(n,k). - Dennis P. Walsh, Feb 02 2012
T(n,k) is the number of ordered pairs (A,B) of subsets of {1,2,...,n} such that the intersection of A and B contains exactly k elements. For example, T(2,1) = 6 because we have ({1},{1}); ({1},{1,2}); ({2},{2}); ({2},{1,2}); ({1,2},{1}); ({1,2},{2}). Sum_{k=0..n} T(n,k)*k = A002697(n) (see comment there by Ross La Haye). - Geoffrey Critzer, Sep 04 2013
Also the convolution triangle of A000244. - Peter Luschny, Oct 09 2022

			Example: n = 3 offers 2^3 = 8 different binary vectors (0,0,0), (0,0,1), ..., (1,1,0), (1,1,1). a(3,2) = 9 of the 2^4 = 64 pairs have overlap k = 2: (0,1,1)*(0,1,1) = (1,0,1)*(1,0,1) = (1,1,0)*(1,1,0) = (1,1,1)*(1,1,0) = (1,1,1)*(1,0,1) = (1,1,1)*(0,1,1) = (0,1,1)*(1,1,1) = (1,0,1)*(1,1,1) = (1,1,0)*(1,1,1) = 2.
For example, T(2,1)=6 since there are 6 subsets of {1,2,3,4} that have exactly 1 symmetric pair, namely, {1,4}, {2,3}, {1,2,3}, {1,2,4}, {1,3,4}, and {2,3,4}.
The present sequence formatted as a triangular array:
     1
     3     1
     9     6     1
    27    27     9     1
    81   108    54    12    1
   243   405   270    90   15    1
   729  1458  1215   540  135   18   1
  2187  5103  5103  2835  945  189  21  1
  6561 17496 20412 13608 5670 1512 252 24 1
  ...
A013610 formatted as a triangular array:
  1
  1  3
  1  6   9
  1  9  27   27
  1 12  54  108   81
  1 15  90  270  405   243
  1 18 135  540 1215  1458   729
  1 21 189  945 2835  5103  5103  2187
  1 24 252 1512 5670 13608 20412 17496 6561
   ...
A099097 formatted as a square array:
      1     0     0    0   0 0 0 0 0 0 0 ...
      3     1     0    0   0 0 0 0 0 0 ...
      9     6     1    0   0 0 0 0 0 ...
     27    27     9    1   0 0 0 0 ...
     81   108    54   12   1 0 0 ...
    243   405   270   90  15 1 ...
    729  1458  1215  540 135 ...
   2187  5103  5103 2835 ...
   6561 17496 20412 ...
  19683 59049 ...
  59049 ...

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
B. N. Cyvin et al., Isomer enumeration of unbranched catacondensed polygonal systems with pentagons and heptagons, Match, No. 34 (Oct 1996), pp. 109-121.
Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001).

Cf. A000244, A007318, A013610, A013610, A099097, A027471, A027472, A036216, A036217, A036219, A036220, A036221, A036222, A036223.

a027465 n k = a027465_tabl !! n !! k
a027465_row n = a027465_tabl !! n
a027465_tabl = iterate (\row ->
   zipWith (+) (map (* 3) (row ++ [0])) (map (* 1) ([0] ++ row))) [1]
-- Reinhard Zumkeller, May 26 2013

for i from 0 to 12 do seq(binomial(i, j)*3^(i-j), j = 0 .. i) od; # Zerinvary Lajos, Nov 25 2007
# Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.
PMatrix(10, n -> 3^(n-1)); # Peter Luschny, Oct 09 2022

t[n_, k_] := Binomial[n, k]*3^(n-k); Table[t[n, n-k], {n, 0, 9}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 19 2012 *)

{T(n, k) = polcoeff( (3 + x)^n, k)}; /* Michael Somos, Feb 14 2002 */

Numerators of lower triangle of (b^2)[ i, j ] where b[ i, j ] = binomial(i-1, j-1)/2^(i-1) if j <= i, 0 if j > i.
Triangle whose (i, j)-th entry is binomial(i, j)*3^(i-j).
a(n, m) = 4^(n-1)*Sum_{j=m..n} b(n, j)*b(j, m) = 3^(n-m)*binomial(n-1, m-1), n >= m >= 1; a(n, m) := 0, n < m. G.f. for m-th column: (x/(1-3*x))^m (m-fold convolution of A000244, powers of 3). - Wolfdieter Lang, Feb 2006
G.f.: 1 / (1 - x(3+y)).
a(n,k) = 3*a(n-1,k) + a(n-1,k-1) - R. J. Mathar, Mar 17 2006
From the formalism of A133314, the e.g.f. for the row polynomials of A027465 is exp(x*t)*exp(3x). The e.g.f. for the row polynomials of the inverse matrix is exp(x*t)*exp(-3x). p iterates of the matrix give the matrix with e.g.f. exp(x*t)*exp(p*3x). The results generalize for 3 replaced by any number. - Tom Copeland, Aug 18 2008
T(n,k) = A164942(n,k)*(-1)^k. - Philippe Deléham, Oct 09 2011
Let P and P^T be the Pascal matrix and its transpose and H = P^3 = A027465. Then from the formalism of A132440 and A218272,
  exp[x*z/(1-3z)]/(1-3z) = exp(3z D_z z) e^(x*z)= exp(3D_x x D_x) e^(z*x)
  = (1 z z^2 z^3 ...) H (1 x x^2/2! x^3/3! ...)^T
  = (1 x x^2/2! x^3/3! ...) H^T (1 z z^2 z^3 ...)^T = Sum_{n>=0} (3z)^n L_n(-x/3), where D is the derivative operator and L_n(x) are the regular (not normalized) Laguerre polynomials. - Tom Copeland, Oct 26 2012
E.g.f. for column k: x^k/k! * exp(3x). - Geoffrey Critzer, Sep 04 2013

cp's OEIS Frontend

A002802 a(n) = (2*n+3)!/(6*n!*(n+1)!).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A075677 Reduced Collatz function R applied to the odd integers: a(n) = R(2n-1), where R(k) = (3k+1)/2^r, with r as large as possible.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A047053 a(n) = 4^n * n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A102376 a(n) = 4^A000120(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Formula

A020522 a(n) = 4^n - 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

A002802 a(n) = (2n+3)!/(6n!*(n+1)!).

A114121 Expansion of (sqrt(1 - 4x) + (1 - 2x))/(2(1 - 4x)).