login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000325 2^n - n. 57
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

Chromatic invariant of the Moebius ladder M_n.

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

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;

David Callan, Pattern avoidance in circular permutations.

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 [Pasha Zusmanovich, Jun 09 2009]

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.)

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

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.CO/0207204

Eric W. Weisstein, Chromatic Invariant.

Eric Weisstein's World of Mathematics, Chromatic Invariant

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, binom(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 for 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

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 *)

PROG

(PARI) {a(n) = if( n<0, 0, 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

Cf. A000108.

Column 1 of triangle A008518.

Cf. A133116.

A160692. - Reinhard Zumkeller, May 24 2009

Row sum of triangles A184049 and A184050.

Cf. A005803, A006127.

Sequence in context: A096766 A111000 * A076878 A129983 A083378 A116712

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 27 23:23 EDT 2015. Contains 260049 sequences.