|
| |
|
|
A161126
|
|
Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} having k descents (n>=1; 0<=k<n).
|
|
1
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 6, 12, 6, 1, 1, 9, 28, 28, 9, 1, 1, 12, 57, 92, 57, 12, 1, 1, 16, 105, 260, 260, 105, 16, 1, 1, 20, 179, 630, 960, 630, 179, 20, 1, 1, 25, 289, 1397, 3036, 3036, 1397, 289, 25, 1, 1, 30, 444, 2836, 8471, 12132, 8471, 2836, 444, 30, 1, 1, 36
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
Sum of entries in row n = A000085(n).
Sum(k*T(n,k),k=0..n-1)=A161125(n).
|
|
|
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.
|
|
|
LINKS
|
Table of n, a(n) for n=1..68.
|
|
|
FORMULA
|
Generating polynomial of row n is P(n,t)=(1-t)^{n+1}*Sum(t^r*Sum(binom(r(r+1)/2+k-1,k)*binom(r+n-2k,n-2k),k=0..floor(n/2), r=0..infinity) (see Eq. (2.5) in the Guo-Zeng paper; see first Maple program).
Rec. rel. for n>=3, k>=0: n*T(n,k)=(k+1)*T(n-1,k)+(n-k)*T(n-1,k-1)+[(k+1)^2 + n-2]*T(n-2,k) + [2k(n-k-1)-n+3]T(n-2,k-1]+[(n-k)^2 +n-2]*T(n-2,k-2) (see Eq. (2.4) in the Guo-Zeng paper; see 2nd Maple program).
|
|
|
EXAMPLE
|
T(4,2)=4 because we have 1432, 2143, 4231, and 3214.
Triangle starts:
1;
1,1;
1,2,1;
1,4,4,1;
1,6,12,6,1;
1,9,28,28,9,1;
|
|
|
MAPLE
|
P := proc (n) options operator, arrow: sort(simplify((1-t)^(n+1)*(sum(t^r*(sum(binomial((1/2)*r*(r+1)+k-1, k)*binomial(r+n-2*k, n-2*k), k = 0 .. floor((1/2)*n))), r = 0 .. infinity)))) end proc: for n to 12 do seq(coeff(P(n), t, j), j = 0 .. n-1) end do; # yields sequence in triangular form
T := proc (n, k) if k < 0 then 0 elif n <= k then 0 elif n = 1 and k = 0 then 1 elif n = 2 and k = 0 then 1 elif n = 2 and k = 1 then 1 else ((k+1)*T(n-1, k)+(n-k)*T(n-1, k-1)+((k+1)^2+n-2)*T(n-2, k)+(2*k*(n-k-1)-n+3)*T(n-2, k-1)+((n-k)^2+n-2)*T(n-2, k-2))/n end if end proc: for n to 12 do seq(T(n, k), k = 0 .. n-1) end do; # yields sequence in triangular form
|
|
|
CROSSREFS
|
A000085, A161125.
Sequence in context: A203906 A096806 A116672 * A128562 A034368 A113582
Adjacent sequences: A161123 A161124 A161125 * A161127 A161128 A161129
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Emeric Deutsch, Jun 09 2009
|
|
|
STATUS
|
approved
|
| |
|
|
