A114320 Triangle T(n,k) = number of permutations of n elements with k 2-cycles.

1, 1, 1, 1, 3, 3, 15, 6, 3, 75, 30, 15, 435, 225, 45, 15, 3045, 1575, 315, 105, 24465, 12180, 3150, 420, 105, 220185, 109620, 28350, 3780, 945, 2200905, 1100925, 274050, 47250, 4725, 945, 24209955, 12110175, 3014550, 519750, 51975, 10395, 290529855

Offset: 0

Author

Vladeta Jovovic, Feb 05 2006

Keywords

• easy
• nonn
• tabf

Comments

Row n has 1+floor(n/2) terms. Row sums yield the factorials (A000142). Sum(k*T(n,k),k>0)=n!/2 for n>=2. - Emeric Deutsch, Feb 17 2006

Examples

			T(3,1) = 3 because we have (1)(23), (12)(3) and (13)(2).
Triangle begins:
    1;
    1;
    1,   1;
    3,   3;
   15,   6,   3;
   75,  30,  15;
  435, 225,  45,  15;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened

Crossrefs

Cf. A008290, A000266, A000090, A088436, A000138, A060725, A060726, A086659, A105422, A105114.

Programs

Maple

G:= exp((y-1)*x^2/2)/(1-x): Gser:= simplify(series(G,x=0,15)): P[0]:=1: for n from 1 to 12 do P[n]:= n!*coeff(Gser,x^n) od: for n from 0 to 12 do seq(coeff(y*P[n], y^j), j=1..1+floor(n/2)) od;  # yields sequence in triangular form - Emeric Deutsch, Feb 17 2006

Mathematica

d = Exp[-x^2/2!]/(1 - x);f[list_] := Select[list, # > 0 &]; Flatten[Map[f, Transpose[Table[Range[0, 10]!CoefficientList[Series[x^(2 k)/(2^k k!) d, {x, 0, 10}], x], {k, 0, 5}]]]]  (* Geoffrey Critzer, Nov 29 2011 *)

Formula

E.g.f.: exp((y-1)*x^2/2)/(1-x). More generally, e.g.f. for number of permutations of n elements with k m-cycles is exp((y-1)*x^m/m)/(1-x).

T(n,k) = n!/(2^k*k!) * Sum_{j=0..floor(n/2)-k} (-1/2)^j/j!. - Alois P. Heinz, Nov 30 2011

Extensions

More terms from Emeric Deutsch, Feb 17 2006