cp's OEIS Frontend

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).

%I A161126 #46 May 09 2025 05:18:52
%S A161126 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,
%T A161126 105,260,260,105,16,1,1,20,179,630,960,630,179,20,1,1,25,289,1397,
%U A161126 3036,3036,1397,289,25,1,1,30,444,2836,8471,12132,8471,2836,444,30,1,1,36
%N 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).
%C A161126 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
%C A161126 See the Brualdi/Ma reference for the connection to A138177. - _Joerg Arndt_, Nov 02 2014
%H A161126 Alois P. Heinz, <a href="/A161126/b161126.txt">Rows n = 1..141, flattened</a>
%H A161126 Richard A. Brualdi and Shi-Mei Ma, <a href="https://doi.org/10.1016/j.ejc.2014.08.026">Enumeration of involutions by descents and symmetric matrices</a>, European Journal of Combinatorics, vol. 43, pp. 220-228, (January 2015).
%H A161126 J. Désarménien and D. Foata, <a href="http://www.numdam.org/item?id=BSMF_1985__113__3_0">Fonctions symétriques et séries hypergéometriques basiques multivariées</a>, Bull. Soc. Math. France, 113, 1985, 3-22.
%H A161126 Samantha Dahlberg, <a href="http://arxiv.org/abs/1410.7356">Combinatorial Proofs of Identities Involving Symmetric Matrices</a>, arXiv:1410.7356 [math.CO], 2014-2017.
%H A161126 I. M. Gessel and C. Reutenauer, <a href="http://dx.doi.org/10.1016/0097-3165(93)90095-P">Counting permutations with given cycle structure and descent set</a>, J. Combin. Theory, Ser. A, 64, 1993, 189-215.
%H A161126 V. J. W. Guo and J. Zeng, <a href="http://dx.doi.org/10.1016/j.jcta.2005.10.002">The Eulerian distribution on involutions is indeed unimodal</a>, J. Combin. Theory, Ser. A, 113, 2006, 1061-1071.
%F A161126 Sum_{k=1..n} T(n,k) = A000085(n) (row sums).
%F A161126 Sum_{k=0..n-1} k*T(n,k) = A161125(n).
%F A161126 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).
%F A161126 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) + (2*k*(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).
%e A161126 T(4,2)=4 because we have 1432, 2143, 4231, and 3214.
%e A161126 Triangle starts:
%e A161126   01: 1
%e A161126   02: 1,  1
%e A161126   03: 1,  2,   1
%e A161126   04: 1,  4,   4,    1
%e A161126   05: 1,  6,  12,    6,     1
%e A161126   06: 1,  9,  28,   28,     9,      1
%e A161126   07: 1, 12,  57,   92,    57,     12,      1
%e A161126   08: 1, 16, 105,  260,   260,    105,     16,      1
%e A161126   09: 1, 20, 179,  630,   960,    630,    179,     20,     1
%e A161126   10: 1, 25, 289, 1397,  3036,   3036,   1397,    289,    25,    1
%e A161126   11: 1, 30, 444, 2836,  8471,  12132,   8471,   2836,   444,   30,   1
%e A161126   12: 1, 36, 659, 5434, 21529,  42417,  42417,  21529,  5434,  659,  36,  1
%e A161126   13: 1, 42, 945, 9828, 50423, 132146, 181734, 132146, 50423, 9828, 945, 42, 1
%e A161126   ...
%p A161126 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
%p A161126 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
%t A161126 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 *)
%Y A161126 Cf. A000085, A161125, A138177.
%K A161126 nonn,tabl
%O A161126 1,5
%A A161126 _Emeric Deutsch_, Jun 09 2009