OFFSET
0,3
COMMENTS
If the e.g.f. of b(n) is E(x) and a(n) = Sum_{k=0..n} C(n,k)^2*(n-k)!*b(k), then the e.g.f. of a(n) is E(x/(1-x))/(1-x). - Vladeta Jovovic, Apr 16 2005
a(n) is the total number of elements in all partial permutations (injective partial functions) of {1,2,...,n} that are in a cycle. A fixed point is considered to be in a cycle. a(n) = Sum_{k=0..n} A206703(n,k)*k. - Geoffrey Critzer, Feb 11 2012
a(n) is the total number of elements in all partial permutations (injective partial functions) of {1,2,...,n} that are undefined, i.e., they do not have an image. - Geoffrey Critzer, Feb 09 2022
a(n) is the total length of all increasing subsequences over all n-permutations. Cf. A002720. - Geoffrey Critzer, Feb 09 2022
a(n) is the number of ways to sit n people on benches and choose one person from any bench (different from choosing one person from each bench, which is A082579). If only 1 bench is used the sequence is A001563. See Example. - Enrique Navarrete, Oct 09 2025
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..200
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132.
N. J. A. Sloane, Transforms
FORMULA
a(n) = Sum_{k=0..n} (n!/k!)*binomial(n-1, k-1)*k^2.
E.g.f.: x/(1-x)^2*exp(x/(1-x)).
Recurrence: (n-1)*a(n) - n*(2*n-1)*a(n-1) + n*(n-1)^2*a(n-2) = 0.
a(n) = n*A000262(n). - Vladeta Jovovic, Mar 20 2005
a(n) ~ n! * exp(-1/2 + 2*sqrt(n))*n^(1/4)/(2*sqrt(Pi)). - Vaclav Kotesovec, Aug 13 2013
a(n) = n!*hypergeom([2, 1-n], [1, 1], -1). - Peter Luschny, Mar 30 2015
a(n) = Sum_{k=1..n} k*(n-k)!*binomial(n,k)^2. - Ridouane Oudra, Jun 17 2025
EXAMPLE
From Enrique Navarrete, Oct 09 2025: (Start)
For n=5 we have (number of seatings on benches given by A000262, with "/" denoting division between benches):
1 bench: 12345 (120 such seatings), 600 ways;
2 benches: 1234/5 (120 such seatings), 600 ways;
2 benches: 123/45 (120 such seatings), 600 ways;
3 benches: 123/4/5 (60 such seatings), 300 ways;
3 benches: 12/34/5 (60 such seatings), 300 ways;
4 benches: 12/3/4/5 (20 such seatings), 100 ways;
5 benches: 1/2/3/4/5 (1 such seating), 5 ways.
The number of seatings is A000262(5)=501 and the number of ways is a(5)=2505. (End)
MAPLE
with(combstruct): SetSeqSetL := [T, {T=Set(S), S=Sequence(U, card >= 1), U=Set(Z, card=1)}, labeled]: seq(k*count(SetSeqSetL, size=k), k=0..18); # Zerinvary Lajos, Jun 06 2007
a := n -> n!*hypergeom([2, 1-n], [1, 1], -1):
seq(simplify(a(n)), n=0..20); # Peter Luschny, Mar 30 2015
MATHEMATICA
nn = 20; a = 1/(1 - x); ay = 1/(1 - y x); D[Range[0, nn]! CoefficientList[ Series[Exp[a x] ay, {x, 0, nn}], x], y] /. y -> 1 (* Geoffrey Critzer, Feb 11 2012 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Vladeta Jovovic, Mar 18 2005
STATUS
approved
