A027616 -id:A027616 - 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.

See also A000138 and A000090.

Cf. A027616, A130905, A193385.

G:=exp(-z^2/2)/(1-z): Gser:=series(G,z=0,26): for n from 0 to 25 do a(n):=n!*coeff(Gser,z,n): end do: seq(a(n), n=0..20); # Paul Weisenhorn, May 29 2010
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*(j-1)!*binomial(n-1, j-1), j=[1, $3..n]))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 12 2016

a=Log[1/(1-x)]-x^2/2; Range[0,20]! CoefficientList[Series[Exp[a], {x,0,20}], x] (* Geoffrey Critzer, Nov 29 2011 *)

{a(n) = if( n<0, 0, n! * polcoeff( exp(-(x^2/2)+x*O(x^n)) / (1 - x), n))} /* Michael Somos, Jul 28 2009 */

E.g.f.: exp( x + Sum_{k>2} x^k / k ). - Michael Somos, Jul 25 2011
a(n) = n! * Sum_{i=0..floor(n/2)} (-1)^i /(i! * 2^i); a(n)/n! ~ Sum_{i>=0} (-1)^i /(i! * 2^i) = e^(-1/2); a(n) ~ e^(-1/2) * n!; a(n) ~ e^(-1/2) * (n/e)^n * sqrt(2*Pi*n). - Avi Peretz (njk(AT)netvision.net.il), Apr 21 2001
A027616(n) + a(n) = n!. - Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 09 2003
a(n) = n!*floor((floor(n/2)! * 2^floor(n/2) / exp(1/2) + 1/2)) / (floor(n/2)! * 2^floor(n/2)), n >= 0. - Simon Plouffe from old notes, 1993
E.g.f.: 1/(1-x)*exp(-(x^2)/2) = 1/((1-x)*G(0)); G(k) = 1+(x^2)/(2*(2*k+1)-2*(x^2)*(2*k+1)/((x^2)+4*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 24 2011
E.g.f.: 1/Q(0), where Q(k) = 1 - x/(1 - x/(x - (2*k+2)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 15 2013
D-finite with recurrence: a(n) - n*a(n-1) + (n-1)*a(n-2) - (n-1)*(n-2)*a(n-3) = 0. - R. J. Mathar, Feb 16 2020

More terms from Christian G. Bower
Entry improved by comments from Michael Somos, Jul 28 2009
Minor editing by Johannes W. Meijer, Jul 25 2011

A293211 Triangle T(n,k) is the number of permutations on n elements with at least one k-cycle for 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 3, 2, 15, 9, 8, 6, 76, 45, 40, 30, 24, 455, 285, 200, 180, 144, 120, 3186, 1995, 1400, 1260, 1008, 840, 720, 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040, 229384, 142695, 103040, 79380, 72576, 60480, 51840, 45360, 40320, 2293839, 1427895, 1030400, 793800, 653184, 604800, 518400, 453600, 403200, 362880

Offset: 1

Dennis P. Walsh, Oct 02 2017

T(n,k) is equivalent to n! minus the number of permutations on n elements with zero k-cycles (sequence A122974).

			T(n,k) (the first 8 rows):
:     1;
:     1,     1;
:     4,     3,     2;
:    15,     9,     8,    6;
:    76,    45,    40,   30,   24;
:   455,   285,   200,  180,  144,  120;
:  3186,  1995,  1400, 1260, 1008,  840,  720;
: 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040;
  ...
T(4,3)=8 since there are exactly 8 permutations on {1,2,3,4} with at least one 3-cycle: (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), and (4)(132).

Dennis P. Walsh, The number of permutations with no k-cycles

Columns k=1-10 give: A002467, A027616, A027617, A029571, A029572, A029573, A029574, A029575, A029576, A029577.
Row sums give A132961.
T(n,n) gives A000142(n-1) for n>0.
T(2n,n) gives A052145.
Cf. A122974, A126074.

T:=(n,k)->n!*sum((-1)^(j+1)*(1/k)^j/j!,j=1..floor(n/k)); seq(seq(T(n,k),k=1..n),n=1..10);

Table[n!*Sum[(-1)^(j + 1)*(1/k)^j/j!, {j, Floor[n/k]}], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, Oct 02 2017 *)

T(n,k) = n! * Sum_{j=1..floor(n/k)} (-1)^(j+1)*(1/k)^j/j!.
T(n,k) = n! - A122974(n,k).
E.g.f. of column k: (1-exp(-x^k/k))/(1-x). - Alois P. Heinz, Oct 11 2017

A088436 Number of permutations in the symmetric group S_n that have exactly one transposition in their cycle decomposition.

Original entry on oeis.org

0, 1, 3, 6, 30, 225, 1575, 12180, 109620, 1100925, 12110175, 145259730, 1888376490, 26438216805, 396573252075, 6345155817000, 107867648889000, 1941617990136825, 36890741812599675, 737814829704702750

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 09 2003

nonn

			From _Bernard Schott_, Feb 19 2019: (Start)
For S_4, the six permutations that have exactly one transposition in their cycle decomposition are (12)(3)(4), (13)(2)(4), (14)(2)(3), (23)(1)(4), (24)(1)(3), (34)(1)(2).
For S_5, there are exactly 10 transpositions: (12), (13), (14), (15), (23), (24), (25), (34), (35), (45), and for each transposition, there are 3 permutations that have exactly this transposition and no other transposition in their cycle decomposition; for example, for transposition (12), these three permutations: (12)(3)(4)(5), (12)(345), (12)(354), so a(5) = 10 * 3 = 30. (End)

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 189, Exercise 19 for k=1. With (-1)^k omitted.

Muniru A Asiru, Table of n, a(n) for n = 1..440

Cf. A000266, A027616, A000240.

m:=32; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( x^2*Exp(-x^2/2)/(2*(1-x)) )); [0] cat [Factorial(n+1)*b[n]: n in [1..m-2]]; // G. C. Greubel, Feb 19 2019

G=(exp(-z^2/2)*z^2*k)/((1-z)*2^k*k!): Gser=series(G,z=0,21):
for n from 2*k to 20 do a(n)=n!*coeff(Gser,z,n): end do: # Paul Weisenhorn, Jun 02 2010

d=Exp[-x^2/2]/(1-x); Range[0,20]! CoefficientList[Series[(x^2/2! )d, {x,0,20}], x] (* Geoffrey Critzer, Nov 29 2011 *)

my(x='x+O('x^30)); concat([0], Vec(serlaplace( x^2*exp(-x^2/2)/(2*(1-x)) ))) \\ G. C. Greubel, Feb 19 2019

m = 30; T = taylor(x^2*exp(-x^2/2)/(2*(1-x)), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (1..m)] # G. C. Greubel, Feb 19 2019

a(n) = (n!/2)*Sum_{j=0..floor(n/2)-1} (-1)^j/(j!*2^j), n >= 1.
E.g.f.: x^2/(1-x)/2*exp(-x^2/2). - Vladeta Jovovic, Nov 09 2003
From Paul Weisenhorn, Jun 02 2010: (Start)
In general, for k cycles of length 2,
a(n) = n!*Sum_{j=k..floor(n/2)} (-1)^j/((j-k)!*2^j*k!).
G.f.: (exp(-z^2/2)*z^2*k)/((1-z)*2^k*k!). (End)
a(n) ~ exp(-1/2)/2 * n!. - Vaclav Kotesovec, Mar 18 2014

More terms from Wolfdieter Lang, Feb 22 2008

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

A293211 Triangle T(n,k) is the number of permutations on n elements with at least one k-cycle for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A088436 Number of permutations in the symmetric group S_n that have exactly one transposition in their cycle decomposition.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions