login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000325 a(n) = 2^n - n. 102
1, 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, 2037, 4084, 8179, 16370, 32753, 65520, 131055, 262126, 524269, 1048556, 2097131, 4194282, 8388585, 16777192, 33554407, 67108838, 134217701, 268435428, 536870883, 1073741794, 2147483617 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of permutations of degree n with at most one fall; called "Grassmannian permutations" by Lascoux and Schützenberger. - Axel Kohnert (Axel.Kohnert(AT)uni-bayreuth.de)

Number of different permutations of a deck of n cards that can be produced by a single shuffle. [DeSario]

Number of Dyck paths of semilength n having at most one long ascent (i.e., ascent of length at least two). Example: a(4)=12 because among the 14 Dyck paths of semilength 4, the only paths that have more than one long ascent are UUDDUUDD and UUDUUDDD (each with two long ascents). Here U = (1, 1) and D = (1, -1). Also number of ordered trees with n edges having at most one branch node (i.e., vertex of outdegree at least two). - Emeric Deutsch, Feb 22 2004

Number of {12,1*2*,21*}-avoiding signed permutations in the hyperoctahedral group.

Number of 1342-avoiding circular permutations on [n+1].

2^n - n is the number of ways to partition {1, 2, ..., n} into arithmetic progressions, where in each partition all the progressions have the same common difference and have lengths at least 1. - Marty Getz (ffmpg1(AT)uaf.edu) and Dixon Jones (fndjj(AT)uaf.edu), May 21 2005

A107907(a(n+2)) = A000051(n+2) for n > 0. - Reinhard Zumkeller, May 28 2005

if b(0) = x and b(n) = b(n-1) + b(n-1)^2*x^(n-2) for n > 0, then b(n) is a polynomial of degree a(n). - Michael Somos, Nov 04 2006

The chromatic invariant of the Mobius ladder graph M_n for n >= 2. - Jonathan Vos Post, Aug 29 2008

Dimension sequence of the dual alternative operad (i.e., associative and satisfying the identity xyz + yxz + zxy + xzy + yzx + zyx = 0) over the field of characteristic 3. - Pasha Zusmanovich, Jun 09 2009

An elephant sequence, see A175654. For the corner squares six A[5] vectors, with decimal values between 26 and 176, lead to this sequence (without the first leading 1). For the central square these vectors lead to the companion sequence A168604. - Johannes W. Meijer, Aug 15 2010

a(n+1) is also the number of order-preserving and order-decreasing partial isometries (of an n-chain). - Abdullahi Umar, Jan 13 2011

A040001(n) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, May 12 2012

A130103(n+1) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, May 12 2012

The number of labeled graphs with n vertices whose vertex set can be partitioned into a clique and a set of isolated points. - Alex J. Best, Nov 20 2012

For n > 0, a(n) is a B_2 sequence. - Thomas Ordowski, Sep 23 2014

See coefficients of the linear terms of the polynomials of the table on p. 10 of the Getzler link. - Tom Copeland, Mar 24 2016

Consider n points lying on a circle, then for n>=2 a(n-1) is the maximum number of ways to connect two points with non-intersecting chords. - Anton Zakharov, Dec 31 2016

Also the number of cliques in the (n-1)-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017

From Eric M. Schmidt, Jul 17 2017: (Start)

Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) < e(k). [Martinez and Savage, 2.7]

Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i), e(j), e(k) pairwise distinct. [Martinez and Savage, 2.7]

Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) >= e(k) and e(i) != e(k) pairwise distinct. [Martinez and Savage, 2.7]

(End)

Number of F-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are F-equivalent iff the positions of pattern F are identical in these paths. -  Sergey Kirgizov, Apr 08 2018

From Gus Wiseman, Feb 10 2019: (Start)

Also the number of connected partitions of an n-cycle. For example, the a(1) = 1 through a(4) = 12 connected partitions are:

  {{1}}  {{12}}    {{123}}      {{1234}}

         {{1}{2}}  {{1}{23}}    {{1}{234}}

                   {{12}{3}}    {{12}{34}}

                   {{13}{2}}    {{123}{4}}

                   {{1}{2}{3}}  {{124}{3}}

                                {{134}{2}}

                                {{14}{23}}

                                {{1}{2}{34}}

                                {{1}{23}{4}}

                                {{12}{3}{4}}

                                {{14}{2}{3}}

                                {{1}{2}{3}{4}}

(End)

Number of subsets of n-set without the single element subsets. - Yuchun Ji, Jul 16 2019

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cory B. H. Ball, The Apprentices' Tower of Hanoi, Electronic Theses and Dissertations, East Tennessee State University, Paper 2512, 2015.

Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178;

Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.

David Callan, Pattern avoidance in circular permutations, arXiv:math/0210014 [math.CO], 2002.

Charles Cratty, Samuel Erickson, Frehiwet Negass, Lara Pudwell, Pattern Avoidance in Double Lists, preprint, 2015.

Robert DeSario & LeRoy Wenstrom, Invertible shuffles, Problem 10931, Amer. Math. Monthly, 111 (No. 2, 2004), 169-170.

Askar Dzhumadil'daev and Pasha Zusmanovich, The alternative operad is not Koszul, arXiv:0906.1272 [math.RA], 2009-2013.

Marty Getz, Dixon Jones and Ken Dutch, Partitioning by Arithmetic Progressions: Problem 11005, American Math. Monthly, Vol. 112, 2005, p. 89. (The published solution is incomplete. Letting d be the common difference of the arithmetic progressions, the solver's expression q_1(n,d)=2^(n-d) must be summed over all d=1,...,n and duplicate partitions must be removed.)

E. Getzler, The semi-classical approximation for modular operads, arXiv:alg-geom/9612005, 1996.

Juan B. Gil, Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.

R. Kehinde, S. O. Makanjuola and A. Umar, On the semigroup of order-decreasing partial isometries of a finite chain, arXiv:1101.2558 [math.GR], 2011.

Alain Lascoux and Marcel-Paul Schützenberger, Schubert polynomials and the Littlewood Richardson rule, Letters in Math. Physics 10 (1985) 111-124.

T. Mansour and J. West, Avoiding 2-letter signed patterns, arXiv:math/0207204 [math.CO], 2002.

Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

Eric Weisstein's World of Mathematics, Chromatic Invariant

Eric Weisstein's World of Mathematics, Clique

Eric Weisstein's World of Mathematics, Moebius Ladder

Chunyan Yan, Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.

Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

FORMULA

a(n+1) = 2*a(n) + n - 1, a(0) = 1. - Reinhard Zumkeller, Apr 12 2003

Binomial transform of 1, 0, 1, 1, 1, .... The sequence starting 1, 2, 5, ...has a(n) = 1 + n + 2*Sum_{k=2..n} binomial(n, k) = 2^(n+1) - n - 1. This is the binomial transform of 1, 1, 2, 2, 2, 2, .... a(n) = 1 + Sum_{k=2..n} C(n, k). - Paul Barry, Jun 06 2003

G.f.: (1-3x+3x^2)/((1-2x)*(1-x)^2). - Emeric Deutsch, Feb 22 2004

a(n+1) = sum of n-th row of the triangle in A109128. - Reinhard Zumkeller, Jun 20 2005

Row sums of triangle A133116. - Gary W. Adamson, Sep 14 2007

G.f.: 1 / (1 - x / (1 - x / ( 1 - x / (1 + x / (1 - 2*x))))). - Michael Somos, May 12 2012

First difference is A000225. PSUM transform is A084634. - Michael Somos, May 12 2012

a(n) = [x^n](B(x)^n-B(x)^(n-1)), n>0, a(0)=1, where B(x) = (1+2*x+sqrt(1+4*x^2))/2. - Vladimir Kruchinin, Mar 07 2014

E.g.f.: (exp(x) - x)*exp(x). - Ilya Gutkovskiy, Aug 07 2016

a(n) = A125128(n) - A000225(n) + 1. - Miquel Cerda, Aug 12 2016

a(n) = 2*A125128(n) - A095151(n) + 1. - Miquel Cerda, Aug 12 2016

a(n) = A079583(n-1) - A000225(n-1). - Miquel Cerda, Aug 15 2016

a(n)^2 - 4*a(n-1)^2 = (n-2)*(a(n)+2*a(n-1)). - Yuchun Ji, Jul 13 2018

a(n) = 2^(-n) * A186947(n) = 2^n * A002064(-n) for all n in Z. - Michael Somos, Jul 18 2018

EXAMPLE

G.f. = 1 + x + 2*x^2 + 5*x^3 + 12*x^4 + 27*x^5 + 58*x^6 + 121*x^7 + ...

MAPLE

A000325 := proc(n) option remember; if n <=1 then n+1 else 2*A000325(n-1)+n-1; fi; end;

g:=1/(1-2*z): gser:=series(g, z=0, 43): seq(coeff(gser, z, n)-n, n=0..31); # Zerinvary Lajos, Jan 09 2009

MATHEMATICA

Table[2^n - n, {n, 0, 39}] (* Alonso del Arte, Sep 15 2014 *)

LinearRecurrence[{4, -5, 2}, {1, 2, 5}, {0, 20}] (* Eric W. Weisstein, Jul 14 2017 *)

PROG

(PARI) {a(n) = 2^n - n}; /* Michael Somos, Nov 04 2006 */

(MAGMA) [2^n - n: n in [0..35]]; // Vincenzo Librandi, May 13 2011

(Haskell)

a000325 n = 2 ^ n - n

a000325_list = zipWith (-) a000079_list [0..]

-- Reinhard Zumkeller, Jul 17 2012

CROSSREFS

Column 1 of triangle A008518.

Row sum of triangles A184049 and A184050.

Cf. A000108, A002064, A133116, A160692, A005803, A006127, A186947.

Cf. A001610, A066982, A323950, A323951.

Sequence in context: A292799 A111000 A328882 * A076878 A129983 A307265

Adjacent sequences:  A000322 A000323 A000324 * A000326 A000327 A000328

KEYWORD

nonn,easy

AUTHOR

Rosario Salamone (Rosario.Salamone(AT)risc.uni-linz.ac.at)

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 12:27 EDT 2020. Contains 337904 sequences. (Running on oeis4.)