A052548 -id:A052548 - cp's OEIS frontend

A000918 a(n) = 2^n - 2.

-1, 0, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534, 131070, 262142, 524286, 1048574, 2097150, 4194302, 8388606, 16777214, 33554430, 67108862, 134217726, 268435454, 536870910, 1073741822, 2147483646, 4294967294, 8589934590, 17179869182, 34359738366, 68719476734, 137438953470

Offset: 0

N. J. A. Sloane

For n > 1, a(n) is the expected number of tosses of a fair coin to get n-1 consecutive heads. - Pratik Poddar, Feb 04 2011
For n > 2, Sum_{k=1..a(n)} (-1)^binomial(n, k) = A064405(a(n)) + 1 = 0. - Benoit Cloitre, Oct 18 2002
For n > 0, the number of nonempty proper subsets of an n-element set. - Ross La Haye, Feb 07 2004
Numbers j such that abs( Sum_{k=0..j} (-1)^binomial(j, k)*binomial(j + k, j - k) ) = 1. - Benoit Cloitre, Jul 03 2004
For n > 2 this formula also counts edge-rooted forests in a cycle of length n. - Woong Kook (andrewk(AT)math.uri.edu), Sep 08 2004
For n >= 1, conjectured to be the number of integers from 0 to (10^n)-1 that lack 0, 1, 2, 3, 4, 5, 6 and 7 as a digit. - Alexandre Wajnberg, Apr 25 2005
Beginning with a(2) = 2, these are the partial sums of the subsequence of A000079 = 2^n beginning with A000079(1) = 2. Hence for n >= 2 a(n) is the smallest possible sum of exactly one prime, one semiprime, one triprime, ... and one product of exactly n-1 primes. A060389 (partial sums of the primorials, A002110, beginning with A002110(1)=2) is the analog when all the almost primes must also be squarefree. - Rick L. Shepherd, May 20 2005
From the second term on (n >= 1), the binary representation of these numbers is a 0 preceded by (n - 1) 1's. This pattern (0)111...1110 is the "opposite" of the binary 2^n+1: 1000...0001 (cf. A000051). - Alexandre Wajnberg, May 31 2005
The numbers 2^n - 2 (n >= 2) give the positions of 0's in A110146. Also numbers k such that k^(k + 1) = 0 mod (k + 2). - Zak Seidov, Feb 20 2006
Partial sums of A155559. - Zerinvary Lajos, Oct 03 2007
Number of surjections from an n-element set onto a two-element set, with n >= 2. - Mohamed Bouhamida, Dec 15 2007
It appears that these are the numbers n such that 3*A135013(n) = n*(n + 1), thus answering Problem 2 on the Mathematical Olympiad Foundation of Japan, Final Round Problems, Feb 11 1993 (see link Japanese Mathematical Olympiad).
Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if x is a proper subset of y or y is a proper subset of x and x and y are disjoint. Then a(n+1) = |R|. - Ross La Haye, Mar 19 2009
The permutohedron Pi_n has 2^n - 2 facets [Pashkovich]. - Jonathan Vos Post, Dec 17 2009
First differences of A005803. - Reinhard Zumkeller, Oct 12 2011
For n >= 1, a(n + 1) is the smallest even number with bit sum n. Cf. A069532. - Jason Kimberley, Nov 01 2011
a(n) is the number of branches of a complete binary tree of n levels. - Denis Lorrain, Dec 16 2011
For n>=1, a(n) is the number of length-n words on alphabet {1,2,3} such that the gap(w)=1. For a word w the gap g(w) is the number of parts missing between the minimal and maximal elements of w. Generally for words on alphabet {1,2,...,m} with g(w)=g>0 the e.g.f. is Sum_{k=g+2..m} (m - k + 1)*binomial((k - 2),g)*(exp(x) - 1)^(k - g). a(3)=6 because we have: 113, 131, 133, 311, 313, 331. Cf. A240506. See the Heubach/Mansour reference. - Geoffrey Critzer, Apr 13 2014
For n > 0, a(n) is the minimal number of internal nodes of a red-black tree of height 2*n-2. See the Oct 02 2015 comment under A027383. - Herbert Eberle, Oct 02 2015
Conjecture: For n>0, a(n) is the least m such that A007814(A000108(m)) = n-1. - L. Edson Jeffery, Nov 27 2015
Actually this follows from the procedure for determining the multiplicity of prime p in C(n) given in A000108 by Franklin T. Adams-Watters: For p=2, the multiplicity is the number of 1 digits minus 1 in the binary representation of n+1. Obviously, the smallest k achieving "number of 1 digits" = k is 2^k-1. Therefore C(2^k-2) is divisible by 2^(k-1) for k > 0 and there is no smaller m for which 2^(k-1) divides C(m) proving the conjecture. - Peter Schorn, Feb 16 2020
For n >= 0, a(n) is the largest number you can write in bijective base-2 (a.k.a. the dyadic system, A007931) with n digits. - Harald Korneliussen, May 18 2019
The terms of this sequence are also the sum of the terms in each row of Pascal's triangle other than the ones. - Harvey P. Dale, Apr 19 2020
For n > 1, binomial(a(n),k) is odd if and only if k is even. - Charlie Marion, Dec 22 2020
For n >= 2, a(n+1) is the number of n X n arrays of 0's and 1's with every 2 X 2 square having density exactly 2. - David desJardins, Oct 27 2022
For n >= 1, a(n+1) is the number of roots of unity in the unique degree-n unramified extension of the 2-adic field Q_2. Note that for each p, the unique degree-n unramified extension of Q_p is the splitting field of x^(p^n) - x, hence containing p^n - 1 roots of unity for p > 2 and 2*(2^n - 1) for p = 2. - Jianing Song, Nov 08 2022

			a(4) = 14 because the 14 = 6 + 4 + 4 rationals (in lowest terms) for n = 3 are (see the Jun 14 2017 formula above): 1/2, 1, 3/2, 2, 5/2, 3; 1/4, 3/4, 5/4, 7/4; 1/8, 3/8, 5/8, 7/8. - _Wolfdieter Lang_, Jun 14 2017

H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 212.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134. - Mohammad K. Azarian, Oct 27 2011
S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009 page 86, Exercise 3.16.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.
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).
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911, p. 31.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
O. Bagdasar, On some functions involving the lcm and gcd of integer tuples, Scientific Publications of the State University of Novi Pazar, Appl. Maths. Inform. and Mech., Vol. 6, 2 (2014), 91--100.
S. Bilotta, E. Grazzini, and E. Pergola, Enumeration of Two Particular Sets of Minimal Permutations, J. Int. Seq. 18 (2015) 15.10.2
R. B. Campbell, The effect of inbreeding constraints and offspring distribution on time to the most recent common ancestor, Journal of Theoretical Biology, Volume 382, 7 October 2015, Pages 74-80.
Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012
M. A. Hill, M. J. Hopkins and D. C. Ravenel, On the non-existence of elements of Kervaire invariant one. - _N. J. A. Sloane_, Sep 27 2010
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 77
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Milan Janjic and B. Petkovic, A Counting Function, arXiv 1301.4550 [math.CO], 2013.
Japanese Mathematical Olympiad 1993, Final Round - Problem 2, Feb 11 1993.
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.
T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015.
Kanstantsin Pashkovich, Symmetry in Extended Formulations of the Permutahedron [sic], arXiv:0912.3446 [math.CO], 2009-2013. [_Jonathan Vos Post_, Dec 17 2009]
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Pratik Poddar, Consecutive Heads Puzzle, Oct 2009.
H. P. Robinson, Letter to N. J. A. Sloane, Sep 1975
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911. [Annotated scans of pages 30-33 only]
Eric Weisstein's World of Mathematics, Sphere Line Picking
Index entries for linear recurrences with constant coefficients, signature (3,-2).
Index to sequences related to Olympiads.

Row sums of triangle A026998.
Cf. A000919, A001117, A001118, A095121, A110146.
Cf. A033484, A000225, A000325, A095151, A125128.
Cf. A058809 (3^n-3, n>0).

a000918 = (subtract 2) . (2 ^)
a000918_list = iterate ((subtract 2) . (* 2) . (+ 2)) (- 1)
-- Reinhard Zumkeller, Apr 23 2013

[2^n - 2: n in [0..40]]; // Vincenzo Librandi, Jun 23 2011

Maple
```
seq(2^n-2,n=0..20) ;
```

Table[2^n - 2, {n, 0, 29}] (* Alonso del Arte, Dec 01 2012 *)

a(n)=2^n-2 \\ Charles R Greathouse IV, Jun 16 2011

def A000918(n): return (1<Chai Wah Wu, Jun 10 2025

a(n) = 2*A000225(n-1).
G.f.: 1/(1 - 2*x) - 2/(1 - x), e.g.f.: (e^x - 1)^2 - 1. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001
For n >= 1, a(n) = A008970(n + 1, 2). - Philippe Deléham, Feb 21 2004
G.f.: (3*x - 1)/((2*x - 1)*(x - 1)). - Simon Plouffe in his 1992 dissertation for the sequence without the leading -1
a(n) = 2*a(n - 1) + 2. - Alexandre Wajnberg, Apr 25 2005
a(n) = A000079(n) - 2. - Omar E. Pol, Dec 16 2008
a(n) = A058896(n)/A052548(n). - Reinhard Zumkeller, Feb 14 2009
a(n) = A164874(n - 1, n - 1) for n > 1. - Reinhard Zumkeller, Aug 29 2009
a(n) = A173787(n,1); a(n) = A028399(2*n)/A052548(n), n > 0. - Reinhard Zumkeller, Feb 28 2010
a(n + 1) = A027383(2*n - 1). - Jason Kimberley, Nov 02 2011
G.f.: U(0) - 1, where U(k) = 1 + x/(2^k + 2^k/(x - 1 - x^2*2^(k + 1)/(x*2^(k + 1) - (k + 1)/U(k + 1) ))); (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Dec 01 2012
a(n+1) is the sum of row n in triangle A051601. - Reinhard Zumkeller, Aug 05 2013
a(n+1) = A127330(n,0). - Reinhard Zumkeller, Nov 16 2013
a(n) = Sum_{k=1..n-1} binomial(n, k) for n > 0. - Dan McCandless, Nov 14 2015
From Miquel Cerda, Aug 16 2016: (Start)
a(n) = A000225(n) - 1.
a(n) = A125128(n-1) - A000325(n).
a(n) = A095151(n) - A125128(n) - 1. (End)
a(n+1) = 2*(n + Sum_{j=1..n-1} (n-j)*2^(j-1)), n >= 1. This is the number of the rationals k/2, k = 1..2*n for n >= 1 and (2*k+1)/2^j for j = 2..n, n >= 2, and 2*k+1 < n-(j-1). See the example for n = 3 below. Motivated by the proposal A287012 by Mark Rickert. - Wolfdieter Lang, Jun 14 2017

Maple programs fixed by Vaclav Kotesovec, Dec 13 2014

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

Original entry on oeis.org

0, 4, 12, 28, 60, 124, 252, 508, 1020, 2044, 4092, 8188, 16380, 32764, 65532, 131068, 262140, 524284, 1048572, 2097148, 4194300, 8388604, 16777212, 33554428, 67108860, 134217724, 268435452, 536870908, 1073741820, 2147483644, 4294967292, 8589934588, 17179869180

Offset: 2

N. J. A. Sloane

Number of permutations of [n] with 2 sequences.
Number of 2 X n binary matrices that avoid simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (11;0). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1Sergey Kitaev, Nov 11 2004
The number of edges in the dual Edwards-Venn diagram graph with n-1 digits when n>2.
a(n) (n>=6) is the number of vertices in the molecular graph NS2[n-5], defined pictorially in the Ashrafi et al. reference (Fig. 2, where NS2[2] is shown). - Emeric Deutsch, May 16 2018
From Petros Hadjicostas, Aug 08 2019: (Start)
With regard to the comment above about a(n) being the "number of permutations of [n] with 2 sequences", we refer to Ex. 13 (pp. 260-261) of Comtet (1974), who uses the definition of a "séquence" given by André in several of his papers in the 19th century.
In the terminology of array A059427, these so-called "séquences" in permutations (defined by Comtet and André) are called "alternating runs" (or just "runs"). We discuss these so-called "séquences" below.
If b = (b_1, b_2, ..., b_n) is a permutation of [n], written in one-line notation (not in cycle notation), a "séquence" in a permutation of length l >= 2 (according to Comtet) is a maximal interval of integers {i, i+1, ..., i+l-1} for some i (where 1 <= i <= n-l+1) such that b_i < b_{i+1} < ... < b_{i+l-1} or b_i > b_{i+1} > ... > b_{i+l-1}. (The word "maximal" means that, in the first case, we have b_{i-1} > b_i and b_{i+l} < b_{i+l-1}, while in the second case, we have b_{i-1} < b_i and b_{i+l} > b_{i+l-1} provided b_{i-1} and b_{i+l} can be defined.)
When defining a "séquence", André (1884) actually refers to the list of terms (b_i, b_{i+1}, ..., b_{i+l-1}) rather than the corresponding index set {i, i+1, ..., i+l-1} (which is essentially the same thing).
For more details about these so-called "séquences" (or "alternate runs"), see the comments and examples for sequence A000708.
(End)
For n >= 1, a(n+2) is the number of shortest paths from (0,0) of a square grid to {(x,y): |x|+|y| = n} along the grid line. - Jianing Song, Aug 23 2021

			From _Petros Hadjicostas_, Aug 08 2019: (Start)
We have a(3) = 4 because each of the following permutations of [3] has the following so-called "séquences" ("alternate runs"):
   123 -> 123 (one),
   132 -> 13, 32 (two),
   213 -> 21, 13 (two),
   231 -> 23, 31 (two),
   312 -> 31, 12 (two),
   321 -> 321 (one).
Recall that a so-called "séquence" ("alternate run") must start with a "maximum" and end with "minimum", or vice versa, and it should not contain any other maxima and minima in between. Two consecutive such "séquences" ("alternate runs") have exactly one minimum or exactly one maximum in common.
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
A. W. F. Edwards, Cogwheels of the Mind, Johns Hopkins University Press, 2004, p. 82.

Muniru A Asiru, Table of n, a(n) for n = 2..700
Désiré André, Sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
Désiré André, Étude sur les maxima, minima et séquences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
Ali Reza Ashrafi and Parisa Nikzad, Kekulé index and bounds of energy for nanostar dendrimers, Digest J. of Nanomaterials and Biostructures, 4, No. 2, 2009, 383-388.
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, University of Kentucky Research Reports (2004).
László Németh, Pascal pyramid in the space H^2 x R, arXiv:1701.06022 [math.CO], 2017 (3rd line of Table 2 is a(n+1)).
I. Strazdins, Universal affine classification of Boolean functions, Acta Applic. Math. 46 (1997), 147-167.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Column k = 2 of A059427.
Row n = 2 of A371064.
Cf. A000225, A000918, A052548, A140504, A175164.
Cf. A000203, A003945.

a:=List([2..40], n->2^n-4); # Muniru A Asiru, May 17 2018

seq(2^n-4, n=2..40); # Muniru A Asiru, May 17 2018

2^Range[2,40]-4 (* Harvey P. Dale, Jul 05 2019 *)

PARI
```
a(n)=if(n<2, 0, 2^n-4)
```

def A028399(n): return (1<Chai Wah Wu, Jun 27 2023

O.g.f.: 4*x^3/((1-x)*(1-2*x)). - R. J. Mathar, Aug 07 2008
From Reinhard Zumkeller, Feb 28 2010: (Start)
a(n) = A175164(2*n)/A140504(n+2);
a(2*n) = A052548(n)*A000918(n) for n > 0;
a(n) = A173787(n,2). (End)
a(n) = a(n-1) + 2^(n-1) (with a(2)=0). - Vincenzo Librandi, Nov 22 2010
a(n) = 4*A000225(n-2). - R. J. Mathar, Dec 15 2015
E.g.f.: 3 + 2*x - 4*exp(x) + exp(2*x). - Stefano Spezia, Apr 06 2021
a(n) = sigma(A003945(n-2)) for n>=3. - Flávio V. Fernandes, Apr 20 2021

Additional comments from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 02 2001

A057168 Next larger integer with same binary weight (number of 1 bits) as n.

Original entry on oeis.org

2, 4, 5, 8, 6, 9, 11, 16, 10, 12, 13, 17, 14, 19, 23, 32, 18, 20, 21, 24, 22, 25, 27, 33, 26, 28, 29, 35, 30, 39, 47, 64, 34, 36, 37, 40, 38, 41, 43, 48, 42, 44, 45, 49, 46, 51, 55, 65, 50, 52, 53, 56, 54, 57, 59, 67, 58, 60, 61, 71, 62, 79, 95, 128, 66, 68, 69, 72, 70, 73, 75

Offset: 1

Marc LeBrun, Sep 14 2000

Binary weight is given by A000120.

			a(6)=9 since 6 has two one-bits (i.e., 6=2+4) and 9 is the next higher integer of binary weight two (7 is weight three and 8 is weight one).

Donald Knuth, The Art of Computer Programming, Vol. 4A, section 7.1.3, exercises 20-21.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
M. Beeler, R. W. Gosper, and R. Schroeppel, HAKMEM, MIT Artificial Intelligence Laboratory, Memo AIM-239, February 1972, Item 175 by Gosper, page 81. Also HTML transcription.
Donald E. Knuth, The Art of Computer Programming, Pre-Fascicle 1A, Draft of Section 7.1.3, 2008. Exercises 20 and 21 page 54 and answers pages 75-76.
Marc B. Reynolds, Popcount walks: next, previous, toward and nearest (2023)

Cf. A000120, A006519, A057169, A000051, A052548, A140504, A000225, A055010, A007283, A171942.

Cf. A000079, A018900, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (Hamming weight = 1, 2, ..., 9).

a057168 n = a057168_list !! (n-1)
a057168_list = f 2 $ tail a000120_list where
   f x (z:zs) = (x + length (takeWhile (/= z) zs)) : f (x + 1) zs
-- Reinhard Zumkeller, Aug 26 2012

a[n_] := (bw = DigitCount[n, 2, 1]; k = n+1; While[ DigitCount[k, 2, 1] != bw, k++]; k); Table[a[n], {n, 1, 71}](* Jean-François Alcover, Nov 28 2011 *)

a(n)=my(u=bitand(n,-n),v=u+n);(bitxor(v,n)/u)>>2+v \\ Charles R Greathouse IV, Oct 28 2009

A057168(n)=n+bitxor(n,n+n=bitand(n,-n))\n\4+n \\ M. F. Hasler, Aug 27 2014

def a(n): u = n&-n; v = u+n; return (((v^n)//u)>>2)+v
print([a(n) for n in range(1, 72)]) # Michael S. Branicky, Jul 10 2022 after Charles R Greathouse IV

def A057168(n): return ((n&~(b:=n+(a:=n&-n)))>>a.bit_length())^b # Chai Wah Wu, Mar 06 2025

From Reinhard Zumkeller, Aug 18 2008: (Start)
a(A000079(n)) = A000079(n+1);
a(A000051(n)) = A052548(n);
a(A052548(n)) = A140504(n);
a(A000225(n)) = A055010(n);
a(A007283(n)) = A000051(n+2). (End)
a(n) = MIN{m: A000120(m)=A000120(n) and m>n}. - Reinhard Zumkeller, Aug 15 2009
For k,m>0, a((2^k-1)*2^m) = 2^(k+m)+2^(k-1)-1. - Chai Wah Wu, Mar 07 2025
If n is odd, then a(n) = XOR(n,OR(a,a/2)) where a = AND(-n,n+1). - Chai Wah Wu, Mar 08 2025

A062709 a(n) = 2^n + 3.

Original entry on oeis.org

4, 5, 7, 11, 19, 35, 67, 131, 259, 515, 1027, 2051, 4099, 8195, 16387, 32771, 65539, 131075, 262147, 524291, 1048579, 2097155, 4194307, 8388611, 16777219, 33554435, 67108867, 134217731, 268435459, 536870915, 1073741827, 2147483651, 4294967299, 8589934595, 17179869187

Offset: 0

Henry Bottomley, Jul 13 2001

Written in binary a(n) is 1000...00011 for n > 1.

For n >= 2, a(n) is the minimal k for which A000120(k(2^n-1)) is not multiple of n. - Vladimir Shevelev, Jun 05 2009

			a(3) = 2^3 + 3 = 8 + 3 = 11.
a(4) = 2^4 + 3 = 16 + 3 = 19.

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

Primes in this sequence are A057733.

Cf. A000051, A000079, A000120, A000225, A004119, A030101, A052548, A173921.

[2^n+3: n in [0..40]] // Vincenzo Librandi, Jan 31 2012

LinearRecurrence[{3, -2}, {4, 5}, 40] (* Vincenzo Librandi, Jan 31 2012 *)
NestList[2 * # - 3 &, 4, 20] (* Zak Seidov, Mar 28 2015 *)
2^Range[0, 29] + 3 (* Alonso del Arte, Mar 28 2015 *)

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

[gaussian_binomial(n,1,2)+4 for n in range(0,32)] # Zerinvary Lajos, May 31 2009

a(n) = 2a(n-1) - 3 = A052548(n) + 1 = A000051(n) + 2 = A000079(n) + 3 = A000225(n) + 4 = A030101(A004119(n)) for n > 1.
G.f.: (4 - 7*x)/((1 - 2*x)*(1 - x)).
a(n) = A173921(A000051(n+1)). - Reinhard Zumkeller, Mar 04 2010
E.g.f.: exp(x)*(3 + exp(x)). - Stefano Spezia, May 06 2023

A173786 Triangle read by rows: T(n,k) = 2^n + 2^k, 0 <= k <= n.

Original entry on oeis.org

2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, 20, 24, 32, 33, 34, 36, 40, 48, 64, 65, 66, 68, 72, 80, 96, 128, 129, 130, 132, 136, 144, 160, 192, 256, 257, 258, 260, 264, 272, 288, 320, 384, 512, 513, 514, 516, 520, 528, 544, 576, 640, 768, 1024, 1025, 1026, 1028, 1032, 1040, 1056, 1088, 1152, 1280, 1536, 2048

Offset: 0

Reinhard Zumkeller, Feb 28 2010

Essentially the same as A048645. - T. D. Noe, Mar 28 2011

			Triangle begins as:
     2;
     3,    4;
     5,    6,    8;
     9,   10,   12,   16;
    17,   18,   20,   24,   32;
    33,   34,   36,   40,   48,   64;
    65,   66,   68,   72,   80,   96,  128;
   129,  130,  132,  136,  144,  160,  192,  256;
   257,  258,  260,  264,  272,  288,  320,  384,  512;
   513,  514,  516,  520,  528,  544,  576,  640,  768, 1024;
  1025, 1026, 1028, 1032, 1040, 1056, 1088, 1152, 1280, 1536, 2048;

T. D. Noe, Rows n = 0..100 of triangle, flattened
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints.org (2025).

Cf. A048645, A118413, A118416.

Cf. also A087112, A370121.

[2^n + 2^k: k in [0..n], n in [0..12]]; // G. C. Greubel, Jul 07 2021

Flatten[Table[2^n + 2^m, {n,0,10}, {m, 0, n}]] (* T. D. Noe, Jun 18 2013 *)

A173786(n) = { my(c = (sqrtint(8*n + 1) - 1) \ 2); 1 << c + 1 << (n - binomial(c + 1, 2)); }; \\ Antti Karttunen, Feb 29 2024, after David A. Corneth's PARI-program in A048645

from math import isqrt, comb
def A173786(n):
    a = (m:=isqrt(k:=n+1<<1))-(k<=m*(m+1))
    return (1<Chai Wah Wu, Jun 20 2025

flatten([[2^n + 2^k for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Jul 07 2021

1 <= A000120(T(n,k)) <= 2.
For n>0, 0<=kA048645(n+1,k+2) and T(n,n) = A048645(n+2,1).
Row sums give A006589(n).
Central terms give A161168(n).
T(2*n+1,n) = A007582(n+1).
T(2*n+1,n+1) = A028403(n+1).
T(n,k) = A140513(n,k) - A173787(n,k), 0<=k<=n.
T(n,k) = A059268(n+1,k+1) + A173787(n,k), 0T(n,k) * A173787(n,k) = A173787(2*n,2*k), 0<=k<=n.
T(n,0) = A000051(n).
T(n,1) = A052548(n) for n>0.
T(n,2) = A140504(n) for n>1.
T(n,3) = A175161(n-3) for n>2.
T(n,4) = A175162(n-4) for n>3.
T(n,5) = A175163(n-5) for n>4.
T(n,n-4) = A110287(n-4) for n>3.
T(n,n-3) = A005010(n-3) for n>2.
T(n,n-2) = A020714(n-2) for n>1.
T(n,n-1) = A007283(n-1) for n>0.
T(n,n) = 2*A000079(n).

Typo in first comment line fixed by Reinhard Zumkeller, Mar 07 2010

A271466 Number T(n,k) of set partitions of [n] such that k is the largest element of the last block; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 1, 4, 10, 0, 1, 6, 15, 30, 0, 1, 10, 29, 59, 104, 0, 1, 18, 63, 139, 250, 406, 0, 1, 34, 149, 365, 692, 1145, 1754, 0, 1, 66, 375, 1039, 2110, 3627, 5649, 8280, 0, 1, 130, 989, 3149, 6932, 12521, 20085, 29874, 42294, 0, 1, 258, 2703, 10039, 24190, 46299, 77133, 117488, 168509, 231950

Offset: 1

Alois P. Heinz, Apr 08 2016

Each set partition is written as a sequence of blocks, ordered by the smallest elements in the blocks.

			T(1,1) = 1: 1.
T(2,2) = 2: 12, 1|2.
T(3,2) = 1: 13|2.
T(3,3) = 4: 123, 12|3, 1|23, 1|2|3.
T(4,2) = 1: 134|2.
T(4,3) = 4: 124|3, 14|23, 14|2|3, 1|24|3.
T(4,4) = 10: 1234, 123|4, 12|34, 12|3|4, 13|24, 13|2|4, 1|234, 1|23|4, 1|2|34, 1|2|3|4.
T(5,2) = 1: 1345|2.
T(5,3) = 6: 1245|3, 145|23, 145|2|3, 14|25|3, 15|24|3, 1|245|3.
T(5,4) = 15: 1235|4, 125|34, 125|3|4, 12|35|4, 135|24, 135|2|4, 13|25|4, 15|234, 15|23|4, 1|235|4, 15|2|34, 1|25|34, 15|2|3|4, 1|25|3|4, 1|2|35|4.
Triangle T(n,k) begins:
  1;
  0, 2;
  0, 1,   4;
  0, 1,   4,  10;
  0, 1,   6,  15,   30;
  0, 1,  10,  29,   59,  104;
  0, 1,  18,  63,  139,  250,   406;
  0, 1,  34, 149,  365,  692,  1145,  1754;
  0, 1,  66, 375, 1039, 2110,  3627,  5649,  8280;
  0, 1, 130, 989, 3149, 6932, 12521, 20085, 29874, 42294;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Wikipedia, Partition of a set

Columns k=1-10 give: A000007(n-1), A054977(n-2), A052548(n-3) for n>3, A271743, A271744, A271745, A271746, A271747, A271748, A271749.
Main diagonal gives A186021(n-1).
Lower diagonals d=1-10 give: A271752, A271753, A271754, A271755, A271756, A271757, A271758, A271759, A271760, A271761.
Row sums give A000110.
T(2n,n) gives A271467.
T(2n+1,n+1) gives A271607.
Cf. A095149 (k is maximum of the first block), A113547 (k is minimum of the last block).

b:= proc(n, m, c) option remember; `if`(n=0, x^c, add(
      b(n-1, max(m, j), `if`(j>=m, n, c)), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, n-i), i=0..n-1))(b(n, 0$2)):
seq(T(n), n=1..12);

b[n_, m_, c_] := b[n, m, c] = If[n == 0, x^c, Sum[b[n-1, Max[m, j], If[j >= m, n, c]], {j, 1, m+1}]];
T[n_] := Function[p, Table[Coefficient[p, x, n-i], {i, 0, n-1}]][b[n, 0, 0]];
Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Apr 24 2016, translated from Maple *)

T(n,n) = 2 * A000110(n-1) = 2 * Sum_{j=0..n-1} T(n-1,j) for n>1.

A140504 a(n) = 2^n + 4.

Original entry on oeis.org

5, 6, 8, 12, 20, 36, 68, 132, 260, 516, 1028, 2052, 4100, 8196, 16388, 32772, 65540, 131076, 262148, 524292, 1048580, 2097156, 4194308, 8388612, 16777220, 33554436, 67108868, 134217732, 268435460, 536870916, 1073741828

Offset: 0

Paul Curtz, Jun 30 2008

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

Cf. A000051 (m=0), A052548 (m=2), this sequence (m=4), A153973 (m=6), A231643 (m=5), A175161 (m=8), A175162 (m=16), A175163 (m=32).

[2^n +4: n in [0..30]]; // G. C. Greubel, Jul 08 2021

Table[2^n + 4, {n, 0, 30}] (* Stefan Steinerberger, Aug 04 2008 *)
LinearRecurrence[{3,-2}, {5,6}, 40] (* Harvey P. Dale, May 26 2018 *)

a(n)=2^n+4 \\ Charles R Greathouse IV, Dec 21 2011

[2^n + 4 for n in range(0,31)] # Zerinvary Lajos, May 31 2009

G.f.: (5 - 9*x)/((1 - x)*(1 - 2*x)). - Jaume Oliver Lafont, Aug 30 2009
a(n) = 2*a(n-1) - 4 with a(0) = 5. - Vincenzo Librandi, Nov 24 2009
From Reinhard Zumkeller, Feb 28 2010: (Start)
a(n) = A173786(n,2) for n > 1.
a(n+2)*A028399(n) = A175164(2*n). (End)
From G. C. Greubel, Jul 08 2021: (Start)
a(n) = m*(2^(n-2) + 1), with m = 4.
E.g.f.: exp(2*x) + 4*exp(x). (End)

More terms from Stefan Steinerberger, Aug 04 2008

A213191 Total sum A(n,k) of k-th powers of parts in all partitions of n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 3, 0, 1, 4, 6, 0, 1, 6, 9, 12, 0, 1, 10, 17, 20, 20, 0, 1, 18, 39, 44, 35, 35, 0, 1, 34, 101, 122, 87, 66, 54, 0, 1, 66, 279, 392, 287, 180, 105, 86, 0, 1, 130, 797, 1370, 1119, 660, 311, 176, 128, 0, 1, 258, 2319, 5024, 4775, 2904, 1281, 558, 270, 192

Offset: 0

Alois P. Heinz, Feb 28 2013

In general, if k > 0 then column k is asymptotic to 2^((k-3)/2) * 3^(k/2) * k! * Zeta(k+1) / Pi^(k+1) * exp(Pi*sqrt(2*n/3)) * n^((k-1)/2). - Vaclav Kotesovec, May 27 2018

			Square array A(n,k) begins:
:   0,  0,   0,   0,    0,     0,     0, ...
:   1,  1,   1,   1,    1,     1,     1, ...
:   3,  4,   6,  10,   18,    34,    66, ...
:   6,  9,  17,  39,  101,   279,   797, ...
:  12, 20,  44, 122,  392,  1370,  5024, ...
:  20, 35,  87, 287, 1119,  4775, 21447, ...
:  35, 66, 180, 660, 2904, 14196, 73920, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-10 give: A006128, A066186, A066183, A229325, A229326, A229327, A229328, A229329, A229330, A229331, A229332.
Rows n=0-10 give: A000004, A000012, A052548, A229354, A229355, A229356, A229357, A229358, A229359, A229360, A229361.
Main diagonal gives A252761.
Cf. A213180.

b:= proc(n, p, k) option remember; `if`(n=0, [1, 0], `if`(p<1, [0, 0],
      add((l->`if`(m=0, l, l+[0, l[1]*p^k*m]))
          (b(n-p*m, p-1, k)), m=0..n/p)))
    end:
A:= (n, k)-> b(n, n, k)[2]:
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[n_, p_, k_] := b[n, p, k] = If[n == 0, {1, 0}, If[p < 1, {0, 0}, Sum[Function[l, If[m == 0, l, l + {0, First[l]*p^k*m}]][b[n - p*m, p - 1, k]], { m, 0, n/p}]]] ; a[n_, k_] := b[n, n, k][[2]]; Table[Table[a[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)
(* T = A066633 *) T[n_, n_] = 1; T[n_, k_] /; k, ] = 0; A[n_, k_] := Sum[T[n, j]*j^k, {j, 1, n}]; Table[A[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 15 2016 *)

A(n,k) = Sum_{j=1..n} A066633(n,j) * j^k.

A208447 Sum of the k-th powers of the numbers of standard Young tableaux over all partitions of n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 5, 1, 1, 2, 6, 10, 7, 1, 1, 2, 10, 24, 26, 11, 1, 1, 2, 18, 64, 120, 76, 15, 1, 1, 2, 34, 180, 596, 720, 232, 22, 1, 1, 2, 66, 520, 3060, 8056, 5040, 764, 30, 1, 1, 2, 130, 1524, 16076, 101160, 130432, 40320, 2620, 42

Offset: 0

Alois P. Heinz, Feb 26 2012

			A(3,2) = 1^2 + 2^2 + 1^2 = 6 = 3! because 3 has partitions 111, 21, 3 with 1, 2, 1 standard Young tableaux, respectively:
  .111.    . 21 . . . . . . .    . 3 . . . .
  +---+    +------+  +------+    +---------+
  | 1 |    | 1  2 |  | 1  3 |    | 1  2  3 |
  | 2 |    | 3 .--+  | 2 .--+    +---------+
  | 3 |    +---+     +---+
  +---+
Square array A(n,k) begins:
   1,  1,   1,    1,      1,       1,        1, ...
   1,  1,   1,    1,      1,       1,        1, ...
   2,  2,   2,    2,      2,       2,        2, ...
   3,  4,   6,   10,     18,      34,       66, ...
   5, 10,  24,   64,    180,     520,     1524, ...
   7, 26, 120,  596,   3060,   16076,    86100, ...
  11, 76, 720, 8056, 101160, 1379176, 19902600, ...

Alois P. Heinz, Antidiagonals n = 0..50
Wikipedia, Young tableau

Columns 0-10 give: A000041, A000085, A000142, A130721, A129627, A218432, A218433, A218434, A218435, A218436, A218437.
Rows 0+1, 2, 3 give: A000012, A007395, A052548.
Main diagonal gives A319607.

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
       +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, k, l) `if`(n=0, h(l)^k, `if`(i<1, 0, g(n, i-1, k, l)
       + `if`(i>n, 0, g(n-i, i, k, [l[], i]))))
    end:
A:= (n, k)-> `if`(n=0, 1, g(n, n, k, [])):
seq(seq(A(n, d-n), n=0..d), d=0..10);

h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]! / Product[Product[1 + l[[i]] - j + Sum [If[l[[k]] >= j, 1, 0], { k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]]; g[n_, i_, k_, l_] := If[n == 0, h[l]^k, If[i < 1, 0, g[n, i-1, k, l] + If[i > n, 0, g[n-i, i, k, Append[l, i]]]]]; a [n_, k_] := If[n == 0, 1, g[n, n, k, {}]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 11 2013, translated from Maple *)

A325973 Arithmetic mean of {sum of unitary divisors} and {sum of squarefree divisors}: a(n) = (1/2) * (A034448(n) + A048250(n)).

Original entry on oeis.org

1, 3, 4, 4, 6, 12, 8, 6, 7, 18, 12, 16, 14, 24, 24, 10, 18, 21, 20, 24, 32, 36, 24, 24, 16, 42, 16, 32, 30, 72, 32, 18, 48, 54, 48, 31, 38, 60, 56, 36, 42, 96, 44, 48, 42, 72, 48, 40, 29, 48, 72, 56, 54, 48, 72, 48, 80, 90, 60, 96, 62, 96, 56, 34, 84, 144, 68, 72, 96, 144, 72, 51, 74, 114, 64, 80, 96, 168, 80, 60, 43, 126

Offset: 1

Antti Karttunen, Jun 02 2019

nonn

This is not multiplicative: a(4) = 4, a(9) = 7, but a(36) = 31, not 28. However, the function acts multiplicatively on certain subsequences of natural numbers, like for example when restricted to A048107, where this sequence coincides with A326043.

			For n = 36, its divisors are 1, 2, 3, 4, 6, 9, 12, 18, 36. Of these, unitary divisors are 1, 4, 9 and 36, so A034448(36) = 1+4+9+36 = 50, while the squarefree divisors are 1, 2, 3 and 6, so A048250(36) = 1+2+3+6 = 12, thus a(36) = (50+12)/2 = 31.
For n = 495, its divisors are 1, 3, 5, 9, 11, 15, 33, 45, 55, 99, 165, 495. Of these, unitary are 1, 5, 9, 11, 45, 55, 99, 495, whose sum is A034448(495) = 720, while the squarefree divisors are 1, 3, 5, 11, 15, 33, 55, 165, and their sum is A048250(495) = 288. Thus a(495) = (720+288)/2 = 504. Also for 495, whose prime factorization is 3^2 * 5^1 * 11^1 this can be computed faster as the average of ((3^2)+1)*(5+1)*(11+1) and (3+1)*(5+1)*(11+1), thus (1/2)*(3+(3^2)+2)*(5+1)*(11+1) = 504.

Antti Karttunen, Table of n, a(n) for n = 1..20000

Cf. A000203, A034448, A048107, A048250, A052548, A289521, A306633, A325974, A325975, A325977, A325978, A325981, A326043.

Array[(1/2) If[# == 1, 2, Times @@ (1 + Power @@@ #) + Times @@ (1 + #[[;; , 1]]) &@ FactorInteger[#]] &, 90] (* Michael De Vlieger, Jun 06 2019, after Giovanni Resta at A034448 and Amiram Eldar at A048250. *)

A034448(n) = { my(f=factorint(n)); prod(k=1, #f~, 1+(f[k, 1]^f[k, 2])); }; \\ After code in A034448
A048250(n) = factorback(apply(p -> p+1,factor(n)[,1]));
A325973(n) = ((A034448(n)+A048250(n))/2);

A325973(n) = (1/2)*sumdiv(n, d, d*(issquarefree(d) + (1==gcd(d, n/d))));

a(n) = (1/2) * (A034448(n) + A048250(n)).
a(n) = A000203(n) - A325974(n).
a(n) = n + A325977(n).
a(A048107(n)) = A326043(A048107(n)).
For n >= 1, a(2^n) = A052548(n-1) = 2^(n-1) + 2.
For n >= 1, a(3^n) = A289521(n) = (3^n + 5)/2.
Sum_{k=1..n} a(k) ~ c * n^2, where c = (zeta(2)/zeta(3) + 1)/4 = 0.5921081944... . - Amiram Eldar, Feb 22 2024

Showing 1-10 of 69 results. Next

cp's OEIS Frontend

A000918 a(n) = 2^n - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Python

Formula

Extensions

A057168 Next larger integer with same binary weight (number of 1 bits) as n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Python

Formula

A062709 a(n) = 2^n + 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A173786 Triangle read by rows: T(n,k) = 2^n + 2^k, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python