|
|
A049376
|
|
Row sums of triangle A046089.
|
|
6
|
|
|
1, 1, 4, 22, 154, 1306, 12976, 147484, 1883932, 26680924, 414468496, 7001104936, 127677078904, 2498712779512, 52209534323584, 1159559538626896, 27269218041047056, 676732851527182864, 17669429275516846912, 484087943980439097184, 13882791112964223876256
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is the number of n-permutations where each cycle has two (not necessarily distinct) roots. Here a root means a designated element in a cycle. Cf. A000262 which gives the number of n-permutations with a single root in each cycle. Note that the order of designating the elements is not important. Cf. (A bijection from endofunctions to "doubly" rooted trees where the order of designating the roots is important) Miklos Bona, A Walk Through Combinatorics, World Scientific Publishing, 2006, page 216. - Geoffrey Critzer, May 17 2012.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: exp(p(x)) with p(x) := x*(2-x)/(2*(1-x)^2) (E.g.f. first column of A046089).
a(n+3) - (3*n+7)*a(n+2) + 3*(n+1)*(n+2)*a(n+1) - n*(n+1)*(n+2)* a(n) = 0. - Emanuele Munarini, Sep 08 2017
a(n) ~ n^(n-1/6) / sqrt(3) * exp(-1/3 + n^(1/3)/2 + 3*n^(2/3)/2 - n). - Vaclav Kotesovec, Oct 23 2017
E.g.f.: Sum_{n>=0} ( Integral 1/(1-x)^3 dx )^n / n!, where the constant of integration is taken to be zero. - Paul D. Hanna, Apr 27 2019
|
|
EXAMPLE
|
a(2) = 4 because we have: (1'')(2'');(1''2);(12'');(1'2') where the permutations are given in cycle notation and the two roots in each cycle are designated by a '.
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n=0, 1, add(
binomial(n-1, j-1)*(j+1)!/2*a(n-j), j=1..n))
end:
a := proc(n) option remember; `if`(n < 3, [1, 1, 4][n + 1],
a(n-1)*(3*n-2) - a(n-2)*3*(n-1)*(n-2) + a(n-3)*(n-1)*(n-2)*(n-3)) end:
|
|
MATHEMATICA
|
nn = 15; Drop[Range[0, nn]! CoefficientList[Series[Exp[x/(1 - x) + x^2/2/(1 - x)^2], {x, 0, nn}], x], 1] (* Geoffrey Critzer, May 17 2012 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|