A130905 -id:A130905 - cp's OEIS frontend

A000266 Expansion of e.g.f. exp(-x^2/2) / (1-x).

1, 1, 1, 3, 15, 75, 435, 3045, 24465, 220185, 2200905, 24209955, 290529855, 3776888115, 52876298475, 793144477125, 12690313661025, 215735332237425, 3883235945814225, 73781482970470275, 1475629660064134575, 30988222861346826075, 681740902935880863075

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of permutations in the symmetric group S_n whose cycle decomposition contains no transposition.

			a(3) = 3 because the permutations in S_3 that contain no transpositions are the trivial permutation and the two 3-cycles.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 85.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, page 93, problem 7.

Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 101 terms from T. D. Noe)
Larry Carter and Stan Wagon, The Mensa Correctional Institute, The American Mathematical Monthly 125.4 (2018): 306-319.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 104
Simon Plouffe, Exact formulas for integer sequences, March 1993.

A288950 Number of relaxed compacted binary trees of right height at most one with empty initial and final sequence on level 0.

Original entry on oeis.org

1, 0, 1, 2, 15, 140, 1575, 20790, 315315, 5405400, 103378275, 2182430250, 50414138775, 1264936572900, 34258698849375, 996137551158750, 30951416768146875, 1023460181133390000, 35885072600989486875, 1329858572860198631250, 51938365373373313209375

Offset: 0

Michael Wallner, Jun 20 2017

nonn

A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. The number of unbounded relaxed compacted binary trees of size n is A082161(n). The number of relaxed compacted binary trees of right height at most one of size n is A001147(n). See the Genitrini et al. and Wallner link. - Michael Wallner, Apr 20 2017

a(n) is the number of plane increasing trees with n+1 nodes where node 3 is at depth 1 on the right of node 2 and where the node n+1 has a left sibling. See the Wallner link. - Michael Wallner, Apr 20 2017

			Denote by L the leaf and by o nodes. Every node has exactly two out-going edges or pointers. Internal edges are denoted by - or |. Pointers are omitted and may point to any node further right. The root is at level 0 at the very left.
The general structure is
  L-o-o-o-o-o-o-o-o-o
    |       |     | |
    o   o-o-o   o-o o.
For n=0 the a(0)=1 solution is L.
For n=1 we have a(1)=0 because we need nodes on level 0 and level 1.
For n=2 the a(2)=1 solution is
     L-o
       |
       o
and the pointers of the node on level 1 both point to the leaf.
For n=3 the a(3)=2 solutions have the structure
     L-o
       |
     o-o
where the pointers of the last node have to point to the leaf, but the pointer of the next node has 2 choices: the leaf of the previous node.

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.

Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A000032, A000246, A001879, A051577, A177145, A213527, A288950, A288952, A288953, A288954 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).
Cf. A001879.

terms = 21; (z + (1 - z)/3*(2 - z + (1 - 2z)^(-1/2)) + O[z]^terms // CoefficientList[#, z] &) Range[0, terms-1]! (* Jean-François Alcover, Dec 04 2018 *)

E.g.f.: z + (1-z)/3 * (2-z + (1-2*z)^(-1/2)).
From Seiichi Manyama, Apr 26 2025: (Start)
a(n) = (n-1)*(2*n-3)/(n-2) * a(n-1) for n > 3.
a(n) = A001879(n-2)/3 for n > 2. (End)

A130906 Expansion of e.g.f. exp(x^3/3!)/(1-x).

Original entry on oeis.org

1, 1, 2, 7, 28, 140, 850, 5950, 47600, 428680, 4286800, 47154800, 565873000, 7356349000, 102988886000, 1544834691400, 24717355062400, 420195036060800, 7563510839684800, 143706705954011200, 2874134119080224000, 60356816536896880000, 1327849963811731360000

Offset: 0

Karol A. Penson, Jun 08 2007

nonn

Cf. A000522, A130905.

With[{nn=20},CoefficientList[Series[Exp[x^3/6]/(1-x),{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, May 10 2018 *)

a(n) ~ n! * exp(1/6). - Vaclav Kotesovec, Aug 04 2014

a(n) = n! * Sum_{k=0..floor(n/3)} 1/(6^k * k!). - Seiichi Manyama, Feb 27 2024

More terms from Harvey P. Dale, May 10 2018

A288952 Number of relaxed compacted binary trees of right height at most one with empty sequences between branch nodes on level 0.

Original entry on oeis.org

1, 0, 1, 2, 15, 92, 835, 8322, 99169, 1325960, 19966329, 332259290, 6070777999, 120694673748, 2594992240555, 59986047422378, 1483663965460545, 39095051587497488, 1093394763005554801, 32347902448449172530, 1009325655965539561231, 33125674098690460236620

Offset: 0

Michael Wallner, Jun 20 2017

nonn

A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. A branch node is a node with a left and right edge (no pointer). See the Genitrini et al. link. - Michael Wallner, Apr 20 2017

a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels a maximal young leaf has to be followed by a non-maximal young leaf. A young leaf is a leaf with no left sibling. A maximal young leaf is a young leaf with maximal label. See the Wallner link. - Michael Wallner, Apr 20 2017

			See A288950 and A288953.

Muniru A Asiru, Table of n, a(n) for n = 0..100
Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.

Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A000032, A000246, A001879, A051577, A177145, A213527, A288950, A288953, A288954 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).

a := [1,0];; for n in [3..10^2] do a[n] := (n-2)*a[n-1] + (n-2)^2*a[n-2]; od; a; # Muniru A Asiru, Jan 26 2018

a:=proc(n) option remember: if n=0 then 1 elif n=1 then 0 elif n>=2 then (n-1)*procname(n-1)-(n-1)^2*procname(n-2) fi; end:
seq(a(n),n=0..100); # Muniru A Asiru, Jan 26 2018

Fold[Append[#1, (#2 - 1) Last[#1] + #1[[#2 - 1]] (#2 - 1)^2] &, {1, 0}, Range[2, 21]] (* Michael De Vlieger, Jan 28 2018 *)

E.g.f.: exp( -Sum_{n>=1} Fibonacci(n-1)*x^n/n ), where Fibonacci(n) = A000045(n).
E.g.f.: exp( -1/sqrt(5)*arctanh(sqrt(5)*z/(2-z)) )/sqrt(1-z-z^2).
a(0) = 1, a(1) = 0, a(n) = (n-1)*a(n-1) + (n-1)^2*a(n-2). - Daniel Suteu, Jan 25 2018

A288953 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except after the last branch node on level 0.

Original entry on oeis.org

1, 1, 3, 10, 51, 280, 1995, 15120, 138075, 1330560, 14812875, 172972800, 2271359475, 31135104000, 471038042475, 7410154752000, 126906349444875, 2252687044608000, 43078308695296875, 851515702861824000, 17984171447178811875, 391697223316439040000

Offset: 0

Michael Wallner, Jun 20 2017

nonn

A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. A branch node is a node with a left and right edge (no pointer). See the Genitrini et al. link. - Michael Wallner, Apr 20 2017

a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels maximal young leaves and non-maximal young leaves alternate except for a sequence of maximal young leaves at the beginning. A young leaf is a leaf with no left sibling. A maximal young leaf is a young leaf with maximal label. See the Wallner link. - Michael Wallner, Apr 20 2017

			Denote by L the leaf and by o nodes. Every node has exactly two out-going edges or pointers. Internal edges are denoted by - or |. Pointers are omitted and may point to any node further right. The root is at level 0 at the very left.
The general structure is
  L-o-o-o-o-o-o-o-o
          | | | | |
          o o o o o.
For n=0 the a(0)=1 solution is L.
For n=1 the a(1)=1 solution is L-o.
For n=2 the a(2)=3 solutions are
L-o-o     L-o
            |
            o
  2    +   1    solutions of this shape with pointers.

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017

Cf. A288954 (variation with additional initial sequence).
Cf. A177145 (variation without final sequence).
Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A000032, A000246, A001879, A051577, A213527, A288950, A288952, A288954 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).

E.g.f.: (2-z)/(3*(1-z)^2) + 1/(3*sqrt(1-z^2)).

A193229 A double factorial triangle.

Original entry on oeis.org

1, 1, 1, 3, 3, 2, 15, 15, 12, 6, 105, 105, 90, 60, 24, 945, 945, 840, 630, 360, 120, 10395, 10395, 9450, 7560, 5040, 2520, 720, 135135, 135135, 124740, 103950, 75600, 45360, 20160, 5040, 2027025, 2027025, 1891890, 1621620, 1247400, 831600, 453600, 181440, 40320

Offset: 0

Gary W. Adamson, Jul 18 2011

The double factorial triangle coefficients are T(n,k), n >= 0 and 0 <= k <= n.
The T(n,0) equal the double factorial numbers A001147(n) = (2*n-1)!!.
The T(n,n) equal the factorial numbers A000142(n) = n!.
The row sums equal the double factorial numbers A000165(n) = (2*n)!!.
The Kn21(n) sums, see A180662 for the definition of these and other triangle sums, equal A130905(n) while the Kn2p(n) sums equal A130905(n+2*p-2) - (n+2*p-2)!*A010844(p-2)/A000165(p-2), p >= 2. - Johannes W. Meijer, Jul 21 2011

			The first few rows of matrix M[i,j] are:
  1, 1, 0, 0, 0, 0, ...
  2, 2, 2, 0, 0, 0, ...
  3, 3, 3, 3, 0, 0, ...
  4, 4, 4, 4, 4, 0, ...
  5, 5, 5, 5, 5, 5, ...
The first few rows of triangle T(n,k) are:
       1;
       1,      1;
       3,      3,      2;
      15,     15,     12,      6;
     105,    105,     90,     60,    24;
     945,    945,    840,    630,   360,   120;
   10395,  10395,   9450,   7560,  5040,  2520,   720;
  135135, 135135, 124740, 103950, 75600, 45360, 20160, 5040;

Seiichi Manyama, Rows n = 0..139, flattened

Cf. A000142, A000165, A001147, A102625.
Cf. A180662, A130905, A010844.
T(2*n,n) gives A166334.

nmax:=7: M := Matrix(1..nmax+1,1..nmax+1): for i from 1 to nmax do for j from 1 to i+1 do M[i,j] := i od: od: for n from 0 to nmax do B := M^n: for k from 0 to n do T(n,k) := B[1,k+1] od: od: for n from 0 to nmax do seq(T(n,k),k=0..n) od: seq(seq(T(n,k),k=0..n),n=0..nmax); # Johannes W. Meijer, Jul 21 2011

row(n)=(matrix(n,n,i,j,(i>j-2)*i)^(n-1))[1,]  \\ M. F. Hasler, Jul 24 2011

T(n,k) = the (k+1)-th term in the top row of M^n, where M is an infinite square production matrix; M[i,j] = i, i >= 1 and 1 <= j <= i+1, and M[i,j] = 0, i >= 1 and j >= i+2, see the examples.

It appears that T(n,k) = (2*n-k)!/(2^(n-k)*(n-k)!) with conjectural e.g.f. 1/(x*(1-2*z) + (1-x)*sqrt(1-2*z)) = 1 + (1+x)*z + (3+3*x+2*x^2)*z^2/2! + .... Cf. A102625. - Peter Bala, Jul 09 2012

Corrected, edited and extended by Johannes W. Meijer, Jul 21 2011

More terms from Seiichi Manyama, Apr 06 2019

A288954 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.

Original entry on oeis.org

1, 1, 3, 13, 79, 555, 4605, 42315, 436275, 4894155, 60125625, 794437875, 11325612375, 172141044075, 2793834368325, 48009995908875, 874143494098875, 16757439016192875, 338309837281040625, 7157757510792763875, 158706419654857449375, 3673441093896736036875

Offset: 2

Michael Wallner, Jun 20 2017

nonn

A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. A branch node is a node with a left and right edge (no pointer). See the Genitrini et al. link. - Michael Wallner, Apr 20 2017

a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels a maximal young leaves and non-maximal young leaves alternate except for a sequence of maximal young leaves at the begininning and at the end. A young leaf is a leaf with no left sibling. A maximal young leaf is a young leaf with maximal label. See the Wallner link. - Michael Wallner, Apr 20 2017

			See A288950 and A288953.

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.

Cf. A288953 (variation without initial sequence).
Cf. A177145 (variation without initial and final sequence).
Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A000032, A000246, A001879, A051577, A213527, A288950, A288952 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).

terms = 22; egf = 1/(3(1-z))(1/Sqrt[1-z^2] + (3z^3 - z^2 - 2z + 2)/((1-z)(1-z^2))) + O[z]^terms;
CoefficientList[egf, z] Range[0, terms-1]! (* Jean-François Alcover, Dec 13 2018 *)

E.g.f.: 1/(3*(1-z))*( 1/sqrt(1-z^2) + (3*z^3-z^2-2*z+2)/((1-z)*(1-z^2)) ).

A130907 E.g.f.: exp(x+x^2/2)/(1-x).

Original entry on oeis.org

1, 2, 6, 22, 98, 516, 3172, 22436, 180252, 1624888, 16258376, 178877832, 2146674136, 27907332272, 390705042288, 5860585983856, 93769421948432, 1594080384922656, 28693447925921632, 545175515402212448, 10903510331802913056, 228973717087813867072

Offset: 0

Karol A. Penson, Jun 08 2007

nonn

A jeweler creates collections of necklaces using exactly n different colored beads (to make the entire collection) then chooses some (or none or all) of the necklaces to sell. - Geoffrey Critzer, Apr 20 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A130905.

CoefficientList[Series[Exp[x + x^2/2 - Log[1 - x]], {x, 0, 21}], x]* Table[n!, {n, 0, 21}] (* Geoffrey Critzer, Apr 20 2009 *)

x='x+O('x^66);
egf=exp(x+x^2/2)/(1-x);
Vec(serlaplace(egf)) /* Joerg Arndt, Jul 11 2011 */

a(n) = n! + n!*Sum_{m=0..n} Sum_{k=1..m} binomial(k,m-k)*2^(k-m)/k!. - Vladimir Kruchinin, Jul 02 2011
From Vaclav Kotesovec, Oct 20 2012: (Start)
D-finite with recurrence a(n) = (n+1)*a(n-1) - (n-2)*(n-1)*a(n-3).
a(n) ~ n!*exp(3/2). (End)

I deleted the initial 1. - Geoffrey Critzer, Apr 19 2009

A193385 Expansion of e.g.f. cosh( x^2/2 )/ (1-x).

Original entry on oeis.org

1, 1, 2, 6, 27, 135, 810, 5670, 45465, 409185, 4091850, 45010350, 540134595, 7021749735, 98304496290, 1474567444350, 23593081136625, 401082379322625, 7219482827807250, 137170173728337750, 2743403475221484075

Offset: 0

Michael Somos, Jul 24 2011

nonn

G. C. Greubel, Table of n, a(n) for n = 0..449

Cf. A000266, A130905.

m:=30; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!(Cosh(x^2/2)/(1-x))); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Aug 13 2018

a:=series(cosh(x^2/2)/(1-x),x=0,21): seq(n!*coeff(a,x,n),n=0..20); # Paolo P. Lava, Mar 27 2019

With[{nn=30},CoefficientList[Series[Cosh[x^2/2]/(1-x),{x,0,nn}], x] Range[0,nn]!] (* Harvey P. Dale, May 01 2012 *)

{a(n) = if( n<0, 0, n! * polcoeff( cosh( x^2 / 2 + x * O(x^n)) / (1 - x), n))}

a(n) ~ cosh( 1/2 ) * n!.

a(n) = (A000266(n) + A130905(n)) / 2.

A319364 Expansion of e.g.f. exp(x^3/3)/(1 - x).

Original entry on oeis.org

1, 1, 2, 8, 32, 160, 1000, 7000, 56000, 506240, 5062400, 55686400, 668483200, 8690281600, 121663942400, 1825003980800, 29200063692800, 496401082777600, 8935231687782400, 169769402067865600, 3395388041357312000, 71303153503662080000, 1568669377080565760000, 36079395672853012480000

Offset: 0

Ilya Gutkovskiy, Sep 17 2018

nonn

Robert Israel, Table of n, a(n) for n = 0..449

Cf. A000090, A000522, A030977, A052502, A130905, A319365.

seq(n!*coeff(series(exp(x^3/3)/(1 - x),x=0,24),x,n),n=0..23); # Paolo P. Lava, Jan 09 2019

nmax = 23; CoefficientList[Series[Exp[x^3/3]/(1 - x), {x, 0, nmax}], x] Range[0, nmax]!

my(x='x+O('x^30)); Vec(serlaplace(exp(x^3/3)/(1 - x))) \\ Michel Marcus, Dec 17 2020

a(n) ~ n!*exp(1/3).

D-finite with recurrence: n*a(n) - n^2*a(n-1) - n*(n-1)*(n-2)*a(n-3) + n*(n-1)*(n-2)*(n-3)*a(n-4) = 0. - Robert Israel, Dec 17 2020

cp's OEIS Frontend

A000266 Expansion of e.g.f. exp(-x^2/2) / (1-x).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A288950 Number of relaxed compacted binary trees of right height at most one with empty initial and final sequence on level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A130906 Expansion of e.g.f. exp(x^3/3!)/(1-x).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

Extensions

A288952 Number of relaxed compacted binary trees of right height at most one with empty sequences between branch nodes on level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

Formula

A288953 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except after the last branch node on level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A193229 A double factorial triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A288954 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs