The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #218 Feb 16 2025 08:32:20
%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 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
%C For every prime p, there are infinitely many terms of this sequence that are divisible by p (see IMO Compendium link and Doob reference). Corresponding indices n are: for p = 2, even numbers A299174; for p = 3, A047257; for p = 5, A349767. - _Bernard Schott_, Dec 10 2021
%C Primes are in A081296 and corresponding indices in A048744. - _Bernard Schott_, Dec 12 2021
%D Michael Doob, The Canadian Mathematical Olympiad & L'Olympiade Mathématique du Canada 1969-1993, Canadian Mathematical Society & Société Mathématique du Canada, Problem 4, 1983, page 158, 1993.
%H Vincenzo Librandi, <a href="/A000325/b000325.txt">Table of n, a(n) for n = 0..200</a>
%H Kassie Archer and Aaron Geary, <a href="https://arxiv.org/abs/2406.09369">Descents in powers of permutations</a>, arXiv:2406.09369 [math.CO], 2024.
%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="https://doi.org/10.37236/665">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="https://arxiv.org/abs/math/0210014">Pattern avoidance in circular permutations</a>, arXiv:math/0210014 [math.CO], 2002.
%H Charles Cratty, Samuel Erickson, Frehiwet Negass, and 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 and 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 and Jessica A. Tomasko, <a href="https://arxiv.org/abs/2112.03338">Restricted Grassmannian permutations</a>, arXiv:2112.03338 [math.CO], 2021.
%H Juan B. Gil and Michael D. Weiner, <a href="https://arxiv.org/abs/1812.01682">On pattern-avoiding Fishburn permutations</a>, arXiv:1812.01682 [math.CO], 2018.
%H The IMO Compendium, <a href="https://imomath.com/othercomp/Can/CanMO83.pdf">Problem 4</a>, 15th Canadian Mathematical Olympiad 1983.
%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="https://arxiv.org/abs/math/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="https://mathworld.wolfram.com/ChromaticInvariant.html">Chromatic Invariant</a>
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Clique.html">Clique</a>
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusLadder.html">Moebius Ladder</a>
%H Chunyan Yan and Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).
%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%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 A107907(a(n+2)) = A000051(n+2) for n > 0. - _Reinhard Zumkeller_, May 28 2005
%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
%F a(2^n) = (2^a(n) - 1)*2^n. - _Lorenzo Sauras Altuzarra_, Feb 01 2022
%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
%o (Python)
%o def A000325(n): return (1<<n)-n # _Chai Wah Wu_, Jan 11 2023
%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.
%Y Cf. A047257, A299174, A349767.
%Y Cf. A048744, A081296.
%K nonn,easy,changed
%O 0,3
%A Rosario Salamone (Rosario.Salamone(AT)risc.uni-linz.ac.at)