OFFSET
0,3
COMMENTS
Related to sequence A000085 since it can be shown that sequence A000085 represents the number of permutations (on n letters) that have only cycles of length 2 or less. Letting b(i) denote the i-th term of the sequence A000085, we obtain a(n)=sum(binomial(n,3*j)*(3*j)!*(1/3)^j*b(n-3*j)/j!,j=0..floor(n/3))
REFERENCES
Dennis P. Walsh, The number of permutations with only small cycles, preprint.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..300
P. L. Krapivsky and J. M. Luck, Coverage fluctuations in theater models, arXiv:1902.04365 [cond-mat.stat-mech], 2019.
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637, 2013 and J. Int. Seq. 17 (2014) #14.1.1
R. Petuchovas, Asymptotic analysis of the cyclic structure of permutations, arXiv:1611.02934 [math.CO], p. 6, 2016.
Dennis P. Walsh, Derivation of the sequence
FORMULA
a(n) = sum(binomial((n, 3 * j) * (3 * j)! * (1/3)^j/j! * sum(binomial(n-3 * j, 2 * k) * (2 * k)! * (1/2)^k/k!, k=0..floor((n-3 * j)/2)), j=0..floor(n/3)))
E.g.f.: exp( x + (x^2)/2 + (x^3)/3 ). Replacing 3 by "length k or less" in the definition of the sequence the E.g.f. is exp( x + (x^2)/2 + ... + (x^k)/k ). - Sharon Sela (sharonsela(AT)hotmail.com), May 16 2002
a(n) = a(n-1)+(n-1)*a(n-2)+(n-1)(n-2)*a(n-3). Generally, for n-permutations that have only cycles of length k or less the recurrence is: a(n)=Sum_i=0...k-1;P(n-1,i)*a(n-i-1) where P(x,i) is the falling factorial. - Geoffrey Critzer, May 23 2009
a(n) ~ n^(2*n/3)*exp(-2*n/3-5/18+5/6*n^(1/3)+1/2*n^(2/3))/sqrt(3) * (1 + 31/(324*n^(1/3)) + 302669/(1049760*n^(2/3))). - Vaclav Kotesovec, Aug 15 2013
From Peter Bala, Jul 30 2026: (Start)
For n >= 0, k >= 1, a(n+k) == a(n)*a(k) (mod k).
For k >= 1, a(k*n) == a(n)^k (mod n).
The 2-adic value v_2(a(n)) = 1 + floor((n-2)/4).
Conjectural 3-adic values (each one checked up to n = 1000):
v_3(a(6*n)) = v_3(a(6*n+2)) = n + floor((n+1)/3);
v_3(a(6*n+3)) = v_3(a(6*n+5)) = n + floor(n/3) + 1;
v_3(a(6*n+1)) >= n + floor((n+1)/3);
v_3(a(6*n+4)) >= n + floor(n/3) + 1.
If true, then it follows that for a positive integer N of the form 2^i * 3^j there exists n_0 such that N divides a(n) for all n >= n_0.
For a positive integer k, reducing the sequence modulo k produces an eventually periodic sequence. For example, modulo 7 the sequence becomes [1, 1, 2, 6, 4, 3, 3, 1, 1, 2, 6, 4, 3, 3, ...], with a period of 7 starting at n = 0. (End)
EXAMPLE
For example, a(4)=18 since there are 6 permutations with cycles of length 4 to exclude from the 24 permutations on 4 letters, namely (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3) and (1 4 3 2).
MAPLE
a:= proc(n) option remember; `if`(n<3, n!,
a(n-1) +(n-1)*a(n-2) +(n-1)*(n-2)*a(n-3))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Jun 06 2013
MATHEMATICA
nn=20; Range[0, nn]!CoefficientList[Series[Exp[ x + x^2/2 + x^3/3], {x, 0, nn}], x] (* Geoffrey Critzer, Oct 28 2012 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Dennis P. Walsh, Oct 20 2000
STATUS
approved
