A362745 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, 1, 2, 2, 10, 16, 10, 88, 200, 200, 88, 1216, 3536, 4896, 3536, 1216, 24176, 85872, 149152, 149152, 85872, 24176, 654424, 2743728, 5714472, 7176352, 5714472, 2743728, 654424, 23136128, 111842432, 270769536, 407103104, 407103104, 270769536, 111842432, 23136128

Offset

0,3

Comments

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.

Links

Alois P. Heinz, Rows n = 0..70, flattened

L. Carlitz, Richard Scoville, and Theresa Vaughan, Enumeration of pairs of permutations and sequences, Bull. Amer. Math. Soc. 80(5) (1974), 881-884.

Formula

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.

Example

Triangle begins:
    1;
    1;
    2,    2;
   10,   16,   10;
   88,  200,  200,   88;
 1216, 3536, 4896, 3536, 1216;
 ...
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).

Maple

b:= proc(n, u, v) option remember; expand(`if`(n=0, 1,
      add(add(b(n-1, u-j, v-i), i=1..v)+
          add(b(n-1, u-j, v+i-1)*x, i=1..n-v), j=1..u)+
      add(add(b(n-1, u+j-1, v-i)*x, i=1..v)+
          add(b(n-1, u+j-1, v+i-1), i=1..n-v), j=1..n-u)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 01 2023

Mathematica

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

Crossrefs

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

Sequence in context: A307538 A316200 A360636 * A179789 A334396 A265199

Adjacent sequences: A362742 A362743 A362744 * A362746 A362747 A362748

Keyword

nonn,tabf

Author

Geoffrey Critzer, May 01 2023

Status

approved