%I A000325
%S A000325 1,1,2,5,12,27,58,121,248,503,1014,2037,4084,8179,16370,32753,65520,
%T A000325 131055,262126,524269,1048556,2097131,4194282,8388585,16777192,33554407,
%U A000325 67108838,134217701,268435428,536870883,1073741794,2147483617
%N A000325 2^n - n.
%C A000325 Comment from Axel Kohnert (Axel.Kohnert(AT)uni-bayreuth.de): This is 
               the number of permutations of degree n with at most one fall; called 
               Grassmannian permutations by L. and S.
%C A000325 Number of different permutations of a deck of n cards that can be produced 
               by a single shuffle [DeSario]
%C A000325 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 (deutsch(AT)duke.poly.edu), Feb 22 2004
%C A000325 Number of {12,1*2*,21*}-avoiding signed permutations in the hyperoctahedral 
               group.
%C A000325 Number of 1342-avoiding circular permutations on [n+1].
%C A000325 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 A000325 A107907(a(n+2)) = A000051(n+2) for n>0. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               May 28 2005
%C A000325 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 A000325 The chromatic invariant of the Mobius ladder graph M_n for n=>2. [From 
               Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 29 2008]
%C A000325 Chromatic invariant of the Moebius ladder M_n
%C A000325 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. [From Pasha Zusmanovich (justpasha(AT)gmail.com), 
               Jun 09 2009]
%D A000325 R. DeSario et al., Invertible shuffles, Problem 10931, Amer. Math. Monthly, 
               111 (No. 2, 2004), 169-170.
%D A000325 Lascoux and Schutzenberger, Schubert polynomials and the Littlewood Richardson 
               rule, Letters in Math. Physics 10 (1985) 111-124.
%D A000325 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.)
%D A000325 A. Dzhumadil'daev and P. Zusmanovich, The alternative operad is not Koszul, 
               arXiv:0906.1272 [From Pasha Zusmanovich (justpasha(AT)gmail.com), 
               Jun 09 2009]
%H A000325 <a href="Sindx_Rea.html#recLCC">Index entries for sequences related to 
               linear recurrences with constant coefficients</a>
%H A000325 D. Callan, <a href="http://arXiv.org/abs/math.CO/0210014">Pattern avoidance 
               in circular permutations</a>.
%H A000325 T. Mansour and J. West, <a href="http://arXiv.org/abs/math.CO/0207204">
               Avoiding 2-letter signed patterns</a>.
%H A000325 Eric W. Weisstein, <a href="http://mathworld.wolfram.com/ChromaticInvariant.html">
               Chromatic Invariant.</a>
%H A000325 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               ChromaticInvariant.html">Chromatic Invariant</a>
%F A000325 a(n+1) = 2*a(n) + n - 1, a(0) = 1. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               Apr 12 2003
%F A000325 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 (pbarry(AT)wit.ie), Jun 06 2003
%F A000325 G.f. = (1-3x+3x^2)/[(1-2x)(1-x)^2]. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Feb 22 2004
%F A000325 a(n+1) = sum of n-th row for the triangle in A109128. - Reinhard Zumkeller 
               (reinhard.zumkeller(AT)gmail.com), Jun 20 2005
%F A000325 Row sums of triangle A133116 - Gary W. Adamson (qntmpkt(AT)yahoo.com), 
               Sep 14 2007
%p A000325 A000325 := proc(n) option remember; if n <=1 then n+1 else 2*A000325(n-1)+n-1; 
               fi; end;
%p A000325 g:=1/(1-2*z): gser:=series(g, z=0, 43): seq(coeff(gser, z, n)-n, n=0..31);
               # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jan 09 2009]
%t A000325 lst={};Do[AppendTo[lst, 2^n-n], {n, 0, 5!}];lst ...and/or... s=1;lst={1, 
               s};Do[s+=s+n++;AppendTo[lst, s], {n, 0, 5!}];lst [From Vladimir Orlovsky 
               (4vladimir(AT)gmail.com), Oct 25 2008]
%t A000325 s = 1; lst = {s}; Do[s += StirlingS2[n, 2]; AppendTo[lst, s], {n, 1, 
               31, 1}]; lst [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 
               Jul 14 2009]
%o A000325 (PARI) {a(n)=if(n<0, 0, 2^n-n)} /* Michael Somos Nov 04 2006 */
%Y A000325 Cf. A000108.
%Y A000325 Column 1 of triangle A008518.
%Y A000325 Cf. A133116.
%Y A000325 A160692. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               May 24 2009]
%Y A000325 Sequence in context: A078410 A096766 A111000 this_sequence A076878 A129983 
               A083378
%Y A000325 Adjacent sequences: A000322 A000323 A000324 this_sequence A000326 A000327 
               A000328
%K A000325 nonn
%O A000325 0,3
%A A000325 Rosario Salamone (Rosario.Salamone(AT)risc.uni-linz.ac.at)