login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 3
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
Also number of ballot sequences of length n with k ascents; also number of standard Young tableaux with n cells such that there are k pairs of cells (v,v+1) with v+1 lying in a row below v. - Joerg Arndt, Feb 21 2014
See the Brualdi/Ma reference for the connection to A138177. - Joerg Arndt, Nov 02 2014
LINKS
Richard A. Brualdi, Shi-Mei Ma, Enumeration of involutions by descents and symmetric matrices, European Journal of Combinatorics, vol. 43, pp. 220-228, (January 2015).
J. Désarménien and D. Foata, Fonctions symétriques et séries hypergéometriques basiques multivariées, Bull. Soc. Math. France, 113, 1985, 3-22.
Samantha Dahlberg, Combinatorial Proofs of Identities Involving Symmetric Matrices, arXiv:1410.7356 [math.CO], 2014-2017.
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
Sum_{k=1..n} T(n,k) = A000085(n) (row sums).
Sum_{k=0..n-1} k*T(n,k) = A161125(n).
Generating polynomial of row n is P(n,t) = (1-t)^(n+1) * Sum_{r>=0} t^r*Sum_{k=0..floor(n/2)} C(r(r+1)/2+k-1,k)*C(r+n-2k,n-2k) (see Eq. (2.5) in the Guo-Zeng paper; see first Maple program).
Recursive relation 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:
01: 1
02: 1, 1
03: 1, 2, 1
04: 1, 4, 4, 1
05: 1, 6, 12, 6, 1
06: 1, 9, 28, 28, 9, 1
07: 1, 12, 57, 92, 57, 12, 1
08: 1, 16, 105, 260, 260, 105, 16, 1
09: 1, 20, 179, 630, 960, 630, 179, 20, 1
10: 1, 25, 289, 1397, 3036, 3036, 1397, 289, 25, 1
11: 1, 30, 444, 2836, 8471, 12132, 8471, 2836, 444, 30, 1
12: 1, 36, 659, 5434, 21529, 42417, 42417, 21529, 5434, 659, 36, 1
13: 1, 42, 945, 9828, 50423, 132146, 181734, 132146, 50423, 9828, 945, 42, 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) option remember; 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
MATHEMATICA
P[n_, t_] := (1-t)^(n+1)*Sum[t^r*Binomial[n+r, n]*HypergeometricPFQ[{(1 - n)/2, -n/2, r(r+1)/2}, {(-n-r)/2, (1-n-r)/2}, 1], {r, 0, n}]; row[n_] := CoefficientList[P[n, t] + O[t]^n, t]; Table[row[n], {n, 1, 13}] // Flatten (* Jean-François Alcover, Dec 20 2016 *)
CROSSREFS
Sequence in context: A274310 A096806 A116672 * A128562 A034368 A361745
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 09 2009
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:34 EDT 2024. Contains 370952 sequences. (Running on oeis4.)