|
| |
|
|
A000325
|
|
a(n) = 2^n - n.
|
|
93
|
|
|
|
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
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: A290292 A292799 A111000 * 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
|
| |
|
|
