|
%I #42 Oct 09 2020 09:08:30
%S 0,1,0,1,1,0,1,2,1,0,1,2,2,1,0,1,2,3,4,1,0,1,2,3,5,4,1,0,1,2,3,6,8,8,
%T 1,0,1,2,3,6,9,13,8,1,0,1,2,3,6,10,18,21,16,1,0,1,2,3,6,10,19,27,34,
%U 16,1,0,1,2,3,6,10,20,33,54,55,32,1,0,1,2,3,6,10,20,34,61,81,89,32,1
%N Array T read by antidiagonals: T(n,k) is the number of involutions avoiding 132 and 12...k.
%C Also, number of paths along a corridor with width k, starting from one side (from H. Bottomley's comment in A061551).
%C Rows converge to binomial(n,floor(n/2)) (A001405).
%C Note that the rows and columns start at 1, which for example obscures the fact that the first row refers to A000007 and not to A000004. A better choice is the indexing 0 <= k and 0 <= n. The Maple program below uses this indexing and builds only on the roots of -1. - _Peter Luschny_, Sep 17 2020
%H Shaun V. Ault and Charles Kicey, <a href="http://dx.doi.org/10.1016/j.disc.2014.05.020">Counting paths in corridors using circular Pascal arrays</a>, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.
%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson</a>, arXiv:2006.06516 [math.CO], 2020.
%H Robert Dutton Fray and David Paul Roselle, <a href="https://projecteuclid.org/download/pdf_1/euclid.pjm/1102970745">Weighted lattice paths</a>, Pacific Journal of Mathematics, 37(1) (1971), 85-96.
%H O. Guibert and T. Mansour, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s48guimans.html">Restricted 132-involutions</a>, Séminaire Lotharingien de Combinatoire, B48a (2002), 23 pp.
%H T. Mansour, <a href="https://arxiv.org/abs/math/0302014">Restricted even permutations and Chebyshev polynomials</a>, arXiv:math/0302014 [math.CO], 2003.
%F G.f. for k-th row: 1/(x*U(k, 1/(2*x))) * Sum_{j=0..k-1} U(j, 1/(2*x)), with U(k, x) the Chebyshev polynomials of second kind. [Clarified by _Jean-François Alcover_, Nov 17 2018]
%F T(n, k) = (1/(n+1))*Sum_{j=1..n, j odd} (2 + [j, n]) * [j, n]^k where [j, n] := (-1)^(j/(n+1)) - (-1)^((n-j+1)/(n+1)). - _Peter Luschny_, Sep 17 2020
%e Array begins
%e 0 0 0 0 0 0 0 0 0 0 ...
%e 1 1 1 1 1 1 1 1 1 1 ...
%e 1 2 2 4 4 8 8 16 16 32 ...
%e 1 2 3 5 8 13 21 34 55 89 ...
%e 1 2 3 6 9 18 27 54 81 162 ...
%e 1 2 3 6 10 19 33 61 108 197 ...
%e 1 2 3 6 10 20 34 68 116 232 ...
%e 1 2 3 6 10 20 35 69 124 241 ...
%e 1 2 3 6 10 20 35 70 125 250 ...
%e 1 2 3 6 10 20 35 70 126 251 ...
%e ...
%p X := (j, n) -> (-1)^(j/(n+1)) - (-1)^((n-j+1)/(n+1)):
%p R := n -> select(k -> type(k, odd), [$(1..n)]):
%p T := (n, k) -> add((2 + X(j,n))*X(j,n)^k, j in R(n))/(n+1):
%p seq(lprint([n], seq(simplify(T(n, k)), k=0..10)), n=0..9); # _Peter Luschny_, Sep 17 2020
%t U = ChebyshevU;
%t m = maxExponent = 14;
%t row[1] = Array[0&, m];
%t row[k_] := 1/(x U[k, 1/(2x)])*Sum[U[j, 1/(2x)], {j, 0, k-1}] + O[x]^m // CoefficientList[#, x]& // Rest;
%t T = Table[row[n], {n, 1, m}];
%t Table[T[[n-k+1, k]], {n, 1, m-1}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Nov 17 2018 *)
%Y Rows 3-8 are A016116, A000045, A038754, A028495, A030436, A061551.
%Y Main diagonal is A014495, antidiagonal sums are in A094719.
%Y Cf. A080934 (permutations).
%K nonn,tabl
%O 1,8
%A _Ralf Stephan_, May 23 2004
|
