login
Triangular array read by rows. T(n,k) is the number of ordered pairs of n-permutations with exactly k rise/falls or fall/rises, n >= 0, 0 <= k <= max{0,n-1}.
1

%I #20 May 03 2023 10:23:16

%S 1,1,2,2,10,16,10,88,200,200,88,1216,3536,4896,3536,1216,24176,85872,

%T 149152,149152,85872,24176,654424,2743728,5714472,7176352,5714472,

%U 2743728,654424,23136128,111842432,270769536,407103104,407103104,270769536,111842432,23136128

%N Triangular array read by rows. T(n,k) is the number of ordered pairs of n-permutations with exactly k rise/falls or fall/rises, n >= 0, 0 <= k <= max{0,n-1}.

%C Let ( (a_1,a_2,...,a_n), (b_1,b_2,...,b_n) be an ordered pair of n-permutations. Then the pairs (a_i,a_(i+1)) and (b_i,b_(i+1)) are both rises, both falls, a rise and a fall, or a fall and a rise. T(n,k) is the number of ordered pairs of n-permutations that have a total of k rise/falls and fall/rises.

%H Alois P. Heinz, <a href="/A362745/b362745.txt">Rows n = 0..70, flattened</a>

%H L. Carlitz, Richard Scoville, and Theresa Vaughan, <a href="http://projecteuclid.org/euclid.bams/1183535825">Enumeration of pairs of permutations and sequences</a>, Bull. Amer. Math. Soc. 80(5) (1974), 881-884.

%F Sum_{n>=0} Sum_{k=0..n-1} u^k*z^n/(n!)^2 = ((1 - u) A((1 - u) z))/(1 - u A((1 - u) z)) where A(z) = Sum_{n>=0} A060350*z^n/(n!)^2. Theorem 4 in Carlitz, Scoville, Vaughan link.

%e Triangle begins:

%e 1;

%e 1;

%e 2, 2;

%e 10, 16, 10;

%e 88, 200, 200, 88;

%e 1216, 3536, 4896, 3536, 1216;

%e ...

%e In the ordered pair of permutations ( (1,2,3,5,4), (4,2,1,3,5) ) we have a rise/fall, rise/fall, rise/rise, fall/rise. So this ordered pair is counted in T(5,3).

%p b:= proc(n, u, v) option remember; expand(`if`(n=0, 1,

%p add(add(b(n-1, u-j, v-i), i=1..v)+

%p add(b(n-1, u-j, v+i-1)*x, i=1..n-v), j=1..u)+

%p add(add(b(n-1, u+j-1, v-i)*x, i=1..v)+

%p add(b(n-1, u+j-1, v+i-1), i=1..n-v), j=1..n-u)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):

%p seq(T(n), n=0..10); # _Alois P. Heinz_, May 01 2023

%t nn = 8; A[z_] := Total[Select[Import["https://oeis.org/A060350/b060350.txt", "Table"],Length@# == 2 &][[All, 2]]*Table[z^n/n!^2, {n, 0, 250}]];B[n_] := n!^2; e[z_] := Sum[z^n/B[n], {n, 0, nn}]; Map[Select[#, # > 0 &] &,Table[B[n], {n, 0, nn}] CoefficientList[Series[((1 - u) A[(1 - u) z])/(1 - u A[(1 - u) z]), {z, 0, nn}], {z, u}]] // Flatten

%Y Cf. A060350 (column k=0), A001044 (row sums), A259465.

%K nonn,tabf

%O 0,3

%A _Geoffrey Critzer_, May 01 2023