|
| |
|
|
A187251
|
|
Number of permutations of [n] having no cycle with 3 or more alternating runs (it is assumed that the smallest element of a cycle is in the first position).
|
|
3
|
|
|
|
1, 1, 2, 6, 22, 94, 460, 2532, 15420, 102620, 739512, 5729192, 47429896, 417429800, 3888426512, 38192416048, 394239339792, 4264424937488, 48212317486112, 568395755184224, 6973300915138656, 88860103591344864, 1174131206436335296, 16061756166912244800
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
a(n) = A187250(n,0).
It appears that a(n) = A216964(n,1), for n>0. - Michel Marcus, May 17 2013.
The above comment is correct. Let b(n) be the n-th element of the the first column of the triangle in A216964 . By definition, b(n) is the number of permutations of [n] with no cyclic valleys. Recall that alternating runs of permutations are monotonically increasing or decreasing subsequences. In other words, b(n) is the number of permutations of [n] with the restriction that every cycle has at most two alternating runs, so b(n) = A187251(n) = a(n). - Shi-Mei Ma, May 18 2013.
|
|
|
LINKS
|
Table of n, a(n) for n=0..23.
|
|
|
FORMULA
|
E.g.f.: exp( (2*z-1+exp(2*z))/4 ).
For n>=1: a(n)=n!*sum(k=1..n, 2^(n-2*k)*sum(j=0..k, binomial(k,j)*stirling2(n-k+j,j)*j!/(n-k+j)!)/k!); [From Vladimir Kruchinin, Apr 25 2011]
G.f.: 1/Q(0) where Q(k) = 1 - x*k - x/(1 - x*(k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 07 2013
|
|
|
EXAMPLE
|
a(4)=22 because only the permutations 3421=(1324) and 4312=(1423) have cycles with more than 2 alternating runs.
|
|
|
MAPLE
|
g := exp((2*z-1+exp(2*z))*1/4): gser := series(g, z = 0, 28): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 23);
|
|
|
PROG
|
(Maxima)
a(n):=n!*sum(2^(n-2*k)*sum(binomial(k, j)*stirling2(n-k+j, j)*j!/(n-k+j)!, j, 0, k)/k!, k, 1, n); [From Vladimir Kruchinin, Apr 25 2011]
(Pari) x='x+O('x^66); /* that many terms */
Vec(serlaplace(exp( (2*x-1+exp(2*x))/4 ))) /* Joerg Arndt, Apr 26 2011 */
(PARI) lista(m) = {P = x*y; for (n=1, m, M = subst(P, x, 1); M = subst(M, y, 1); print1(polcoeff(M, 0, q), ", "); P = (n*q+x*y)*P + 2*q*(1-q)*deriv(P, q)+ 2*x*(1-q)*deriv(P, x)+ (1-2*y+q*y)*deriv(P, y); ); } \\ (adapted from PARI prog in A216964) \\ Michel Marcus, May 17 2013
|
|
|
CROSSREFS
|
Cf. A187245, A187248, A187250, A216964.
Sequence in context: A030453 A001861 A049526 * A193763 A093793 A087959
Adjacent sequences: A187248 A187249 A187250 * A187252 A187253 A187254
|
|
|
KEYWORD
|
nonn,changed
|
|
|
AUTHOR
|
Emeric Deutsch, Mar 08 2011
|
|
|
STATUS
|
approved
|
| |
|
|
