

A000325


a(n) = 2^n  n.


118



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)unibayreuth.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 1342avoiding 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
if b(0) = x and b(n) = b(n1) + b(n1)^2*x^(n2) 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 orderpreserving and orderdecreasing partial isometries (of an nchain).  Abdullahi Umar, Jan 13 2011
A040001(n) = p(1) where p(x) is the unique degreen 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 degreen 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
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(n1) is the maximum number of ways to connect two points with nonintersecting chords.  Anton Zakharov, Dec 31 2016
Also the number of cliques in the (n1)triangular honeycomb rook graph.  Eric W. Weisstein, Jul 14 2017
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 Fequivalence classes of Łukasiewicz paths. Łukasiewicz paths are Fequivalent iff the positions of pattern F are identical in these paths.  Sergey Kirgizov, Apr 08 2018
Also the number of connected partitions of an ncycle. 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 nset without the singleelement subsets.  Yuchun Ji, Jul 16 2019
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


REFERENCES

Michael Doob, The Canadian Mathematical Olympiad & L'Olympiade Mathématique du Canada 19691993, Canadian Mathematical Society & Société Mathématique du Canada, Problem 4, 1983, page 158, 1993.


LINKS

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^(nd) must be summed over all d=1,...,n and duplicate partitions must be removed.)
The IMO Compendium, Problem 4, 15th Canadian Mathematical Olympiad 1983.
Eric Weisstein's World of Mathematics, Clique


FORMULA

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 / (1  x / (1  x / ( 1  x / (1 + x / (1  2*x))))).  Michael Somos, May 12 2012
a(n) = [x^n](B(x)^nB(x)^(n1)), n>0, a(0)=1, where B(x) = (1+2*x+sqrt(1+4*x^2))/2.  Vladimir Kruchinin, Mar 07 2014
a(n)^2  4*a(n1)^2 = (n2)*(a(n)+2*a(n1)).  Yuchun Ji, Jul 13 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(n1)+n1; fi; end;
g:=1/(12*z): gser:=series(g, z=0, 43): seq(coeff(gser, z, n)n, n=0..31); # Zerinvary Lajos, Jan 09 2009


MATHEMATICA

LinearRecurrence[{4, 5, 2}, {1, 2, 5}, {0, 20}] (* Eric W. Weisstein, Jul 14 2017 *)


PROG

(Haskell)
a000325 n = 2 ^ n  n
a000325_list = zipWith () a000079_list [0..]
(Python)


CROSSREFS



KEYWORD

nonn,easy


AUTHOR

Rosario Salamone (Rosario.Salamone(AT)risc.unilinz.ac.at)


STATUS

approved



