login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A177253 Number of permutations of [n] having no adjacent 4-cycles, i.e., no cycles of the form (i, i+1, i+2, i+3). 7
1, 1, 2, 6, 23, 118, 714, 5016, 40201, 362163, 3623772, 39876540, 478639079, 6223394516, 87138394540, 1307195547720, 20916564680761, 355600269756485, 6401066270800350, 121624180731849810, 2432546364331038479, 51084540451761077514, 1123879093137556106358 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
a(n) = A177252(n,0).
lim_{n->inf} a(n)/n! = 1.
LINKS
R. A. Brualdi and E. Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.
FORMULA
a(n) = Sum_{j=0..floor(n/4)} (-1)^j*(n-3*j)!/j!.
a(n) - n*a(n-1) = 3a(n-4) + 4*(-1)^{n/4} if 4|n; a(n) - n*a(n-1) = 3a(n-4) otherwise.
The o.g.f. g(z) satisfies z^2*(1+z^4)*g'(z) - (1+z^4)(1-z-3z^4)g(z) + 1 - 3z^4 = 0; g(0)=1.
D-finite with recurrence a(n) -n*a(n-1) -2*a(n-4) +(-n+4)*a(n-5) -3*a(n-8)=0. - R. J. Mathar, Jul 26 2022
G.f.: Sum_{k>=0} k! * x^k / (1+x^4)^(k+1). - Seiichi Manyama, Feb 20 2024
EXAMPLE
a(5)=118 because the only permutations of {1,2,3,4,5} having adjacent 4-cycles are (1234)(5) and (1)(2345).
MAPLE
a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-3*j)/factorial(j), j = 0 .. floor((1/4)*n)) end proc: seq(a(n), n = 0 .. 22);
MATHEMATICA
a[n_] := Sum[(-1)^j*(n - 3*j)!/j!, {j, 0, n/4}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 20 2017 *)
CROSSREFS
Sequence in context: A370670 A059513 A132647 * A358609 A364791 A020122
KEYWORD
nonn
AUTHOR
Emeric Deutsch, May 07 2010
EXTENSIONS
Crossreferences corrected by Emeric Deutsch, May 09 2010
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 07:33 EDT 2024. Contains 371235 sequences. (Running on oeis4.)