|
%I M2801 N1127 #58 Feb 23 2023 18:06:37
%S 0,1,3,9,25,75,231,763,2619,9495,35695,140151,568503,2390479,10349535,
%T 46206735,211799311,997313823,4809701439,23758664095,119952692895,
%U 618884638911,3257843882623,17492190577599,95680443760575,532985208200575,3020676745975551
%N Number of degree-n permutations of order exactly 2.
%C Number of set partitions of [n] into blocks of size 2 and 1 with at least one block of size 2. - _Olivier Gérard_, Oct 29 2007
%C For n>=2, number of standard Young tableaux with height <= n - 1. That is, all tableaux (A000085) but the one with just one column. - _Joerg Arndt_, Oct 24 2012
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A001189/b001189.txt">Table of n, a(n) for n = 1..800</a>
%H N. Chheda, M. K. Gupta, <a href="http://arxiv.org/abs/1403.5477">RNA as a Permutation</a>, arXiv:1403.5477 [q-bio.BM], 2014.
%H R. B. Herrera, <a href="http://www.jstor.org/stable/2308456">The number of elements of given period in finite symmetric group</a>, Amer. Math. Monthly 64, 1957, 488-490.
%H L. Moser and M. Wyman, <a href="http://dx.doi.org/10.4153/CJM-1955-020-0">On solutions of x^d = 1 in symmetric groups</a>, Canad. J. Math., 7 (1955), 159-168.
%H J. Rangel-Mondragon, <a href="http://www.jstor.org/stable/2308456">Selected Themes in Computational Non-Euclidean Geometry: Part 1</a>, The Mathematica Journal 15 (2013); http://www.mathematica-journal.com/data/uploads/2013/07/Rangel-Mondragon_Selected-1.pdf
%H Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, <a href="https://arxiv.org/abs/2302.04606">On Discovering Interesting Combinatorial Integer Sequences</a>, arXiv:2302.04606 [cs.LO], 2023, p. 17.
%H Thotsaporn Thanatipanonda, <a href="http://www.jstor.org/stable/3219103">Inversions and major index for permutations</a>, Math. Mag., April 2004.
%F E.g.f.: exp(x + x^2/2) - exp(x).
%F a(n) = A000085(n) - 1.
%F a(n) = b(n, 2), where b(n, d)=Sum_{k=1..n} (n-1)!/(n-k)! * Sum_{l:lcm{k, l}=d} b(n-k, l), b(0, 1)=1 is the number of degree-n permutations of order exactly d.
%F From _Henry Bottomley_, May 03 2001: (Start)
%F a(n) = a(n-1) + (1 + a(n-2))*(n-1).
%F a(n) = Sum_{j=1..floor(n/2)} n!/(j!*(n-2*j)!*(2^j)). (End)
%p a:= proc(n) option remember; `if`(n<3, [0$2, 1][n+1],
%p a(n-1) +(n-1) *(1+a(n-2)))
%p end:
%p seq(a(n), n=1..30); # _Alois P. Heinz_, Oct 24 2012
%p # alternative:
%p A001189 := proc(n)
%p local a,prs,p,k ;
%p a := 0 ;
%p for prs from 1 to n/2 do
%p p := product(binomial(n-2*k,2),k=0..prs-1) ;
%p a := a+p/prs!;
%p end do:
%p a;
%p end proc:
%p seq(A001189(n),n=1..13) ; # _R. J. Mathar_, Jan 04 2017
%t RecurrenceTable[{a[1]==0,a[2]==1,a[n]==a[n-1]+(1+a[n-2])(n-1)},a[n],{n,25}] (* _Harvey P. Dale_, Jul 27 2011 *)
%o (PARI) {a(n) = sum(j=1,floor(n/2), n!/(j!*(n-2*j)!*2^j))}; \\ _G. C. Greubel_, May 14 2019
%o (Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( Exp(x + x^2/2) -Exp(x) )); [0] cat [Factorial(n+1)*b[n]: n in [1..m-2]]; // _G. C. Greubel_, May 14 2019
%o (Sage) m = 30; T = taylor(exp(x +x^2/2) - exp(x), x, 0, m); a=[factorial(n)*T.coefficient(x, n) for n in (0..m)]; a[1:] # _G. C. Greubel_, May 14 2019
%Y Cf. A001470-A001473, A052501, A053496-A053504, A061121-A061128.
%Y Column k=1 of A143911, column k=2 of A080510, A182222. - _Alois P. Heinz_, Oct 24 2012
%Y Column k=2 of A057731. - _Alois P. Heinz_, Feb 14 2013
%K nonn,nice,easy
%O 1,3
%A _N. J. A. Sloane_
|
