|
| |
|
|
A161125
|
|
Number of descents in all involutions of {1,2,...,n}.
|
|
1
| |
|
|
0, 0, 1, 4, 15, 52, 190, 696, 2674, 10480, 42732, 178480, 770836, 3411024, 15538120, 72446752, 346550520, 1694394496, 8477167504, 43287312960, 225707308912, 1199526928960, 6498288708576, 35836282708864, 201160191642400
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| a(n)=(n-1)*A000085(n)/2.
a(n)=Sum(k*A161126(n,k), k=0..n-1).
|
|
|
REFERENCES
| J. Desarmenien and D. Foata, Fonctions symetriques et series hypergeometriques basiques multivariees, Bull. Soc. Math. France, 113, 1985, 3-22.
I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 1993, 189-215.
V. J. W. Guo and J. Zeng, The Eulerian distribution on involutions is indeed unimodal, J. Combin. Theory, Ser. A, 113, 2006, 1061-1071.
|
|
|
FORMULA
| Rec. rel.: a(n)/(n-1) = a(n-1)/(n-2) + (n-1)a(n-2)/(n-3) for n>=4 (see 1st Maple program).
Egf: g(z)=(1/2)[1 - (1 - z - z^2)*exp(z + z^2/2)] (see 2nd Maple program).
|
|
|
EXAMPLE
| a(3)=4 because in the involutions 123, 132, 213, and 321 we have 0 + 1 + 1 + 2 descents.
|
|
|
MAPLE
| a[0] := 0: a[1] := 0: a[2] := 1: a[3] := 4: for n from 4 to 27 do a[n] := (n-1)*(a[n-1]/(n-2)+(n-1)*a[n-2]/(n-3)) end do: seq(a[n], n = 0 .. 27); # end of program
g := (1-(1-z-z^2)*exp(z+(1/2)*z^2))*1/2: gser := series(g, z = 0, 30): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 27); # end of program
|
|
|
CROSSREFS
| Cf. A000085, A161126.
Sequence in context: A132894 A117917 A192431 * A027295 A057332 A162978
Adjacent sequences: A161122 A161123 A161124 * A161126 A161127 A161128
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 09 2009
|
| |
|
|
