cp's OEIS Frontend

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.

%I A129535 #14 Jul 26 2022 13:58:37
%S A129535 2,6,22,106,630,4394,35078,315258,3149494,34620010,415222566,
%T A129535 5395737242,75516784982,1132471183626,18115911832390,307919970965434,
%U A129535 5541804787940598,105282261866132138,2105441434230129254,44210612765653749210,972564180363044943766
%N 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.
%C A129535 Column 1 of A129534. a(n) = n! - A002464(n).
%C A129535 Column k=2 of A322481.
%D A129535 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.
%H A129535 Alois P. Heinz, <a href="/A129535/b129535.txt">Table of n, a(n) for n = 2..450</a>
%F A129535 G.f.: E(x) - E(x(1-x)/(1+x)), where E(x) = Sum_{n>=0} n!*x^n.
%F A129535 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
%F A129535 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
%e A129535 a(4)=22 because 3142 and 2413 are the only permutations of 1,2,3,4 with no adjacent consecutive entries.
%p A129535 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);
%Y A129535 Cf. A002464, A129534, A322481.
%K A129535 nonn
%O A129535 2,1
%A A129535 _Emeric Deutsch_, May 05 2007