|
|
A129535
|
|
Number of permutations of 1,...,n with at least one pair of adjacent consecutive entries (i.e., of the form k(k+1) or (k+1)k), n >= 2.
|
|
3
|
|
|
2, 6, 22, 106, 630, 4394, 35078, 315258, 3149494, 34620010, 415222566, 5395737242, 75516784982, 1132471183626, 18115911832390, 307919970965434, 5541804787940598, 105282261866132138, 2105441434230129254, 44210612765653749210, 972564180363044943766
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
|
|
REFERENCES
|
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: E(x) - E(x(1-x)/(1+x)), where E(x) = Sum_{n>=0} n!*x^n.
a(n) = n! - Sum_{k=1..n} ((-1)^(n-k)*k!*Sum_{i=0..n-k} binomial(i+k-1, k-1)*binomial(k, n-i-k)), n > 0. - Vladimir Kruchinin, Sep 08 2010
D-finite with recurrence a(n) +2*(-n+1)*a(n-1) +(n^2-2*n-2)*a(n-2) +(-n^2+7*n-14)*a(n-3) -(n-3)*(n-5)*a(n-4) +(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Jul 26 2022
|
|
EXAMPLE
|
a(4)=22 because 3142 and 2413 are the only permutations of 1,2,3,4 with no adjacent consecutive entries.
|
|
MAPLE
|
E:=x->sum(n!*x^n, n=0..35): G:=E(x)-E(x*(1-x)/(1+x)): Gser:=series(G, x=0, 30): seq(coeff(Gser, x, n), n=2..23);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|