A000266 -id:A000266 - cp's OEIS frontend

A027616 Number of permutations of n elements containing a 2-cycle.

0, 0, 1, 3, 9, 45, 285, 1995, 15855, 142695, 1427895, 15706845, 188471745, 2450132685, 34301992725, 514529890875, 8232476226975, 139952095858575, 2519137759913775, 47863617438361725, 957272348112505425, 20102719310362613925, 442259824841726816925, 10171975971359716789275

Offset: 0

Joe Keane (jgk(AT)jgk.org)

nonn

Robert Israel, Table of n, a(n) for n = 0..449
Larry Carter and Stan Wagon, The Mensa Correctional Institute, The American Mathematical Monthly 125.4 (2018): 306-319.

Cf. A000266, A088436, A114320.

Column k=2 of A293211.

A027616:= func< n | Factorial(n)*(1- (&+[(-1/2)^j/Factorial(j): j in [0..Floor(n/2)]]) ) >;
[A027616(n): n in [0..30]]; // G. C. Greubel, Aug 05 2022

S:= series((1-exp(-x^2/2))/(1-x), x, 101):
seq(coeff(S,x,j)*j!,j=0..100); # Robert Israel, May 12 2016

nn=30; Table[n!,{n,0,nn}]-Range[0,nn]!CoefficientList[Series[Exp[-x^2/2]/(1-x),{x,0,nn}],x]  (* Geoffrey Critzer, Oct 20 2012 *)

a(n) = n! * (1 - sum(k=0,floor(n/2), (-1)^k / (2^k * k!) ) );
/* Joerg Arndt, Oct 20 2012 */

N=33; x='x+O('x^N);
v=Vec( 'a0 + serlaplace( (1-exp(-x^2/2))/(1-x) ) );
v[1]-='a0;  v
/* Joerg Arndt, Oct 20 2012 */

def A027616(n): return factorial(n)*(1-sum((-1/2)^k/factorial(k) for k in (0..(n//2))))
[A027616(n) for n in (0..30)] # G. C. Greubel, Aug 05 2022

E.g.f.: (1 - exp(-x^2/2)) / (1-x).
a(n) = n! * ( 1 - Sum_{k=0..floor(n/2)} (-1)^k / (2^k * k!) ).
a(n) + A000266(n) = n!. - Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 09 2003
Limit_{n -> oo} a(n)/n! = 1 - e^(-1/2) = 1 - A092605. - Michel Marcus, Aug 08 2013

Added more terms, Geoffrey Critzer, Oct 20 2012

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

A122974 Triangle T(n,k), the number of permutations on n elements that have no cycles of length k.

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 9, 15, 16, 18, 44, 75, 80, 90, 96, 265, 435, 520, 540, 576, 600, 1854, 3045, 3640, 3780, 4032, 4200, 4320, 14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280, 133496, 220185, 259840, 283500, 290304, 302400, 311040, 317520, 322560

Offset: 1

Dennis P. Walsh, Oct 27 2006

Read as sequence, a(n) is the number of permutations on j elements with no cycles of length i where j=round((2*n)^.5) and i=n-C(j,2).

T(n,k) generalizes several sequences already in the On-Line Encyclopedia, such as A000166, the number of permutations on n elements with no fixed points and A000266, the number of permutations on n elements with no transpositions (i.e., no 2-cycles). See the cross references for further examples.

			T(3,2)=3 since there are exactly 3 permutations of 1,2,3 that have no cycles of length 2, namely, (1)(2)(3),(1 2 3) and (2 1 3).
Triangle T(n,k) begins:
      0;
      1,     1;
      2,     3,     4;
      9,    15,    16,    18;
     44,    75,    80,    90,    96;
    265,   435,   520,   540,   576,   600;
   1854,  3045,  3640,  3780,  4032,  4200,  4320;
  14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280;
  ...

Alois P. Heinz, Rows for n = 1..141, flattened
Dennis P. Walsh, The Number of Permutations with No k-Cycles.

Cf. T(n, 1)=A000166 for n=>1 T(n, 2)=A000266 for n=>2 T(n, 3)=A000090 for n=>3 T(n, 4)=A000138 for n=>4 T(n, 5)=A060725 for n=>5 T(n, 6)=A060726 for n=>6 T(n, 7)=A060727 for n=>7.

T(n,n) gives A094304(n+1).

seq((round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5),2)))^r/r!,r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5),2)))),n=1..66);
# second Maple program:
T:= proc(n, k) option remember; `if`(n=0, 1, add(`if`(j=k, 0,
      T(n-j, k)*binomial(n-1, j-1)*(j-1)!), j=1..n))
    end:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Nov 24 2019

T[n_, k_] := T[n, k] = If[n==0, 1, Sum[If[j==k, 0, T[n - j, k] Binomial[n - 1, j - 1] (j - 1)!], {j, 1, n}]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 08 2019, after Alois P. Heinz *)

T(n,k)=n!*sum r=0..floor(n/k)((-1/k)^r/r!) E.G.F: exp(-x^k/k)/(1-x) a(n)=(round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5),2)))^r/r!,r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5),2)))).

T(n,k) = n! - A293211(n,k). - Alois P. Heinz, Nov 24 2019

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.

A178669 The number of permutations of [n] with 2 cycles of length 2.

Original entry on oeis.org

0, 3, 15, 45, 315, 3150, 28350, 274050, 3014550, 36330525, 472296825, 6609317715, 99139765725, 1586293008300, 26966981141100, 485404420000500, 9222683980009500, 184453709062998375

Offset: 3

Paul Weisenhorn, Jun 02 2010

nonn

			a(4)=3 counts the 3 permutations (2143), (3412), (4321) with 2 cycles
of length 2

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

Cf. A088436 (k=1 cycle), A000266 (k=0 cycle).

A178669 := proc(n) local k ; k :=2 ; n!*add( (-1)^j/(j-k)!/2^j/k!,j=k..n/2) ; end proc:
seq(A178669(n),n=3..20) ;

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

a(n)=n!*sum_{j=k.. [n/2]} (-1)^j/((j-k)!*2^j*k!). E.g.f. = exp(-z^2/2)*z^(2*k) / ((1-z)*2^k*k!), where k is the number of cycles of length 2.

a(n) ~ n! * exp(-1/2)/8. - Vaclav Kotesovec, Mar 20 2014

Typo in a(18) corrected by Vincenzo Librandi, Mar 21 2014

A337060 E.g.f.: 1 / (1 + x^2/2 + log(1 - x)).

Original entry on oeis.org

1, 1, 2, 8, 46, 324, 2708, 26424, 295272, 3714600, 51929472, 798610416, 13399081584, 243556758912, 4767863027328, 100004300847744, 2237419620187776, 53187370914349440, 1338737435337261312, 35568441673932566016, 994744655047298951424, 29211127285363209561600

Offset: 0

Ilya Gutkovskiy, Aug 13 2020

nonn

Cf. A000266, A007840, A226226, A337061.

nmax = 21; CoefficientList[Series[1/(1 + x^2/2 + Log[1 - x]), {x, 0, nmax}], x] Range[0, nmax]!
a[0] = 1; a[n_] := a[n] = n a[n - 1] + Sum[Binomial[n, k] (k - 1)! a[n - k], {k, 3, n}]; Table[a[n], {n, 0, 21}]

a(0) = 1; a(n) = n * a(n-1) + Sum_{k=3..n} binomial(n,k) * (k-1)! * a(n-k).

A346372 a(0) = 1; a(n) = n * a(n-1) + (1/n) * Sum_{k=3..n} (binomial(n,k) * k!)^2 * a(n-k) / k.

Original entry on oeis.org

1, 1, 2, 10, 124, 2396, 64856, 2452472, 124483360, 8146185504, 668645524032, 67374446014272, 8183368905811584, 1179807474740449920, 199266648878034317568, 38984601149045449948416, 8748103140554862876727296, 2232274640259371687436982272, 642805438643602793466093711360

Offset: 0

Ilya Gutkovskiy, Jul 14 2021

nonn

Cf. A000266, A074707, A346291.

a[0] = 1; a[n_] := a[n] = n a[n - 1] + (1/n) Sum[(Binomial[n, k] k!)^2 a[n - k]/k, {k, 3, n}]; Table[a[n], {n, 0, 18}]
nmax = 18; CoefficientList[Series[Exp[PolyLog[2, x] - x^2/4], {x, 0, nmax}], x] Range[0, nmax]!^2

Sum_{n>=0} a(n) * x^n / (n!)^2 = exp( polylog(2,x) - x^2 / 4 ).

Sum_{n>=0} a(n) * x^n / (n!)^2 = exp( x + Sum_{n>=3} x^n / n^2 ).

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

Original entry on oeis.org

1, 1, 2, 5, 20, 100, 610, 4270, 34160, 307160, 3071600, 33787600, 405466600, 5271065800, 73794921200, 1106922416600, 17710758665600, 301082897315200, 5419492342264000, 102970354503016000, 2059407090060320000, 43247548855054544000, 951446074811199968000

Offset: 0

Seiichi Manyama, Feb 27 2024

Cf. A000166, A000266.

my(N=30, x='x+O('x^N)); Vec(serlaplace(exp(-x^3/6)/(1-x)))

a(n) = n!*sum(k=0, n\3, (-1)^k/(6^k*k!));

a(n) = n! * Sum_{k=0..floor(n/3)} (-1)^k/(6^k * k!).

cp's OEIS Frontend

A027616 Number of permutations of n elements containing a 2-cycle.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

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

A122974 Triangle T(n,k), the number of permutations on n elements that have no cycles of length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A178669 The number of permutations of [n] with 2 cycles of length 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A337060 E.g.f.: 1 / (1 + x^2/2 + log(1 - x)).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A346372 a(0) = 1; a(n) = n * a(n-1) + (1/n) * Sum_{k=3..n} (binomial(n,k) * k!)^2 * a(n-k) / k.

Views

Author

Keywords