|
|
A001189
|
|
Number of degree-n permutations of order exactly 2.
(Formerly M2801 N1127)
|
|
39
|
|
|
0, 1, 3, 9, 25, 75, 231, 763, 2619, 9495, 35695, 140151, 568503, 2390479, 10349535, 46206735, 211799311, 997313823, 4809701439, 23758664095, 119952692895, 618884638911, 3257843882623, 17492190577599, 95680443760575, 532985208200575, 3020676745975551
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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
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
|
|
REFERENCES
|
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: exp(x + x^2/2) - exp(x).
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.
a(n) = a(n-1) + (1 + a(n-2))*(n-1).
a(n) = Sum_{j=1..floor(n/2)} n!/(j!*(n-2*j)!*(2^j)). (End)
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<3, [0$2, 1][n+1],
a(n-1) +(n-1) *(1+a(n-2)))
end:
# alternative:
local a, prs, p, k ;
a := 0 ;
for prs from 1 to n/2 do
p := product(binomial(n-2*k, 2), k=0..prs-1) ;
a := a+p/prs!;
end do:
a;
end proc:
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(PARI) {a(n) = sum(j=1, floor(n/2), n!/(j!*(n-2*j)!*2^j))}; \\ G. C. Greubel, May 14 2019
(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
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|