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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000325 a(n) = 2^n - n. 93

%I

%S 1,1,2,5,12,27,58,121,248,503,1014,2037,4084,8179,16370,32753,65520,

%T 131055,262126,524269,1048556,2097131,4194282,8388585,16777192,

%U 33554407,67108838,134217701,268435428,536870883,1073741794,2147483617

%N a(n) = 2^n - n.

%C 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)

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

%C 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

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

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

%C 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

%C A107907(a(n+2)) = A000051(n+2) for n > 0. - _Reinhard Zumkeller_, May 28 2005

%C 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

%C The chromatic invariant of the Mobius ladder graph M_n for n >= 2. - _Jonathan Vos Post_, Aug 29 2008

%C 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

%C 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

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

%C 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

%C 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

%C 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

%C For n > 0, a(n) is a B_2 sequence. - _Thomas Ordowski_, Sep 23 2014

%C See coefficients of the linear terms of the polynomials of the table on p. 10 of the Getzler link. - _Tom Copeland_, Mar 24 2016

%C 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

%C Also the number of cliques in the (n-1)-triangular honeycomb rook graph. - _Eric W. Weisstein_, Jul 14 2017

%C From _Eric M. Schmidt_, Jul 17 2017: (Start)

%C 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]

%C 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]

%C 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]

%C (End)

%C 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

%C From _Gus Wiseman_, Feb 10 2019: (Start)

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

%C {{1}} {{12}} {{123}} {{1234}}

%C {{1}{2}} {{1}{23}} {{1}{234}}

%C {{12}{3}} {{12}{34}}

%C {{13}{2}} {{123}{4}}

%C {{1}{2}{3}} {{124}{3}}

%C {{134}{2}}

%C {{14}{23}}

%C {{1}{2}{34}}

%C {{1}{23}{4}}

%C {{12}{3}{4}}

%C {{14}{2}{3}}

%C {{1}{2}{3}{4}}

%C (End)

%C Number of subsets of n-set without the single element subsets. - _Yuchun Ji_, Jul 16 2019

%H Vincenzo Librandi, <a href="/A000325/b000325.txt">Table of n, a(n) for n = 0..200</a>

%H Cory B. H. Ball, <a href="http://dc.etsu.edu/etd/2512">The Apprentices' Tower of Hanoi</a>, Electronic Theses and Dissertations, East Tennessee State University, Paper 2512, 2015.

%H Jean-Luc Baril, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p178">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178;

%H Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.

%H David Callan, <a href="http://arXiv.org/abs/math.CO/0210014">Pattern avoidance in circular permutations</a>, arXiv:math/0210014 [math.CO], 2002.

%H Charles Cratty, Samuel Erickson, Frehiwet Negass, Lara Pudwell, <a href="http://www.valpo.edu/mathematics-statistics/files/2015/07/Pattern-Avoidance-in-Double-Lists.pdf">Pattern Avoidance in Double Lists</a>, preprint, 2015.

%H Robert DeSario & LeRoy Wenstrom, <a href="http://www.jstor.org/stable/4145230">Invertible shuffles, Problem 10931</a>, Amer. Math. Monthly, 111 (No. 2, 2004), 169-170.

%H Askar Dzhumadil'daev and Pasha Zusmanovich, <a href="http://arxiv.org/abs/0906.1272">The alternative operad is not Koszul</a>, arXiv:0906.1272 [math.RA], 2009-2013.

%H Marty Getz, Dixon Jones and Ken Dutch, <a href="http://www.jstor.org/stable/30037399">Partitioning by Arithmetic Progressions: Problem 11005</a>, 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.)

%H E. Getzler, <a href="http://arxiv.org/abs/alg-geom/9612005">The semi-classical approximation for modular operads</a>, arXiv:alg-geom/9612005, 1996.

%H Juan B. Gil, Michael D. Weiner, <a href="https://arxiv.org/abs/1812.01682">On pattern-avoiding Fishburn permutations</a>, arXiv:1812.01682 [math.CO], 2018.

%H R. Kehinde, S. O. Makanjuola and A. Umar, <a href="http://arxiv.org/abs/1101.2558">On the semigroup of order-decreasing partial isometries of a finite chain</a>, arXiv:1101.2558 [math.GR], 2011.

%H Alain Lascoux and Marcel-Paul Schützenberger, <a href="http://dx.doi.org/10.1007/BF00398147">Schubert polynomials and the Littlewood Richardson rule</a>, Letters in Math. Physics 10 (1985) 111-124.

%H T. Mansour and J. West, <a href="http://arXiv.org/abs/math.CO/0207204">Avoiding 2-letter signed patterns</a>, arXiv:math/0207204 [math.CO], 2002.

%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChromaticInvariant.html">Chromatic Invariant</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Clique.html">Clique</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MoebiusLadder.html">Moebius Ladder</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).

%F a(n+1) = 2*a(n) + n - 1, a(0) = 1. - _Reinhard Zumkeller_, Apr 12 2003

%F 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

%F G.f.: (1-3x+3x^2)/((1-2x)*(1-x)^2). - _Emeric Deutsch_, Feb 22 2004

%F a(n+1) = sum of n-th row of the triangle in A109128. - _Reinhard Zumkeller_, Jun 20 2005

%F Row sums of triangle A133116. - _Gary W. Adamson_, Sep 14 2007

%F G.f.: 1 / (1 - x / (1 - x / ( 1 - x / (1 + x / (1 - 2*x))))). - _Michael Somos_, May 12 2012

%F First difference is A000225. PSUM transform is A084634. - _Michael Somos_, May 12 2012

%F 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

%F E.g.f.: (exp(x) - x)*exp(x). - _Ilya Gutkovskiy_, Aug 07 2016

%F a(n) = A125128(n) - A000225(n) + 1. - _Miquel Cerda_, Aug 12 2016

%F a(n) = 2*A125128(n) - A095151(n) + 1. - _Miquel Cerda_, Aug 12 2016

%F a(n) = A079583(n-1) - A000225(n-1). - _Miquel Cerda_, Aug 15 2016

%F a(n)^2 - 4*a(n-1)^2 = (n-2)*(a(n)+2*a(n-1)). - _Yuchun Ji_, Jul 13 2018

%F a(n) = 2^(-n) * A186947(n) = 2^n * A002064(-n) for all n in Z. - _Michael Somos_, Jul 18 2018

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

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

%p 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

%t Table[2^n - n, {n, 0, 39}] (* _Alonso del Arte_, Sep 15 2014 *)

%t LinearRecurrence[{4, -5, 2}, {1, 2, 5}, {0, 20}] (* _Eric W. Weisstein_, Jul 14 2017 *)

%o (PARI) {a(n) = 2^n - n}; /* _Michael Somos_, Nov 04 2006 */

%o (MAGMA) [2^n - n: n in [0..35]]; // _Vincenzo Librandi_, May 13 2011

%o (Haskell)

%o a000325 n = 2 ^ n - n

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

%o -- _Reinhard Zumkeller_, Jul 17 2012

%Y Column 1 of triangle A008518.

%Y Row sum of triangles A184049 and A184050.

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

%Y Cf. A001610, A066982, A323950, A323951.

%K nonn,easy

%O 0,3

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

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 November 14 22:32 EST 2019. Contains 329134 sequences. (Running on oeis4.)