A263753 -id:A263753 - cp's OEIS frontend

A263756 Triangle read by rows: T(n,k) (n>=0, k>=0) is the number of permutations of n with sum of descent bottoms equal to k.

1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 3, 8, 3, 1, 1, 1, 15, 7, 34, 18, 14, 18, 8, 3, 1, 1, 1, 31, 15, 122, 72, 69, 147, 83, 71, 33, 45, 18, 8, 3, 1, 1, 1, 63, 31, 406, 252, 263, 822, 544, 554, 399, 613, 351, 307, 160, 102, 96, 45, 18, 8, 3, 1, 1, 1, 127, 63, 1298, 828

Offset: 0

Christian Stump, Oct 19 2015

Row sums give A000142.

			Triangle begins:
  1;
  1;
  1,1;
  1,3,1,1;
  1,7,3,8,3,1,1;
  1,15,7,34,18,14,18,8,3,1,1;
  1,31,15,122,72,69,147,83,71,33,45,18,8,3,1,1;
  ...

Alois P. Heinz, Rows n = 0..23, flattened
FindStat - Combinatorial Statistic Finder, The sum of the descent bottoms of a permutations.

Cf. A000142, A263753.

b:= proc(s) option remember; (n-> `if`(n=0, 1, expand(
      add(b(s minus {j})*`if`(j (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n})):
seq(T(n), n=0..9);  # Alois P. Heinz, Oct 25 2015, revised, Jan 31 2023

b[s_] := b[s] = With[{n = Length[s]}, If[n == 0, 1, Expand[       Sum[b[s~Complement~{j}]*If[j < n, x^j, 1], {j, s}]]]];
T[n_] := CoefficientList[b[Range[n]], x];
Table[T[n], {n, 0, 9}] // Flatten (* Jean-François Alcover, May 26 2023, after Alois P. Heinz *)

Two terms (for rows 0 and 1) prepended and more terms from Alois P. Heinz, Oct 25 2015

A369596 Number T(n,k) of permutations of [n] whose fixed points sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 2, 1, 1, 1, 0, 0, 1, 9, 2, 2, 3, 3, 2, 1, 1, 0, 0, 1, 44, 9, 9, 11, 11, 13, 5, 5, 4, 4, 2, 1, 1, 0, 0, 1, 265, 44, 44, 53, 53, 62, 64, 29, 22, 24, 16, 16, 8, 6, 5, 4, 2, 1, 1, 0, 0, 1, 1854, 265, 265, 309, 309, 353, 362, 406, 150, 159, 126, 126, 93, 86, 44, 36, 29, 19, 19, 9, 7, 5, 4, 2, 1, 1, 0, 0, 1

Offset: 0

Alois P. Heinz, Mar 02 2024

			T(3,0) = 2: 231, 312.
T(3,1) = 1: 132.
T(3,2) = 1: 321.
T(3,3) = 1: 213.
T(3,6) = 1: 123.
T(4,0) = 9: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
Triangle T(n,k) begins:
   1;
   0, 1;
   1, 0, 0,  1;
   2, 1, 1,  1,  0,  0, 1;
   9, 2, 2,  3,  3,  2, 1, 1, 0, 0, 1;
  44, 9, 9, 11, 11, 13, 5, 5, 4, 4, 2, 1, 1, 0, 0, 1;
  ...

Alois P. Heinz, Rows n = 0..50, flattened
Wikipedia, Permutation

Column k=0 gives A000166.
Column k=3 gives A000255(n-2) for n>=2.
Row sums give A000142.
Row lengths give A000124.
Reversed rows converge to A331518.
T(n,n) gives A369796.
Cf. A000217, A001710, A008289, A008290, A038720, A053632, A062869, A124327, A143946, A143947, A161680, A263753, A263756, A317527, A367955, A368338.

b:= proc(s) option remember; (n-> `if`(n=0, 1, add(expand(
      `if`(j=n, x^j, 1)*b(s minus {j})), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n})):
seq(T(n), n=0..7);
# second Maple program:
g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
T:= (n, k)-> b(k, min(n, k), n):
seq(seq(T(n, k), k=0..n*(n+1)/2), n=0..7);

g[n_] := g[n] = If[n == 0, 1, n*g[n - 1] + (-1)^n];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0,
   If[n == 0, g[m], b[n, i-1, m] + b[n-i, Min[n-i, i-1], m-1]]];
T[n_, k_] := b[k, Min[n, k], n];
Table[Table[T[n, k], {k, 0, n*(n + 1)/2}], {n, 0, 7}] // Flatten (* Jean-François Alcover, May 24 2024, after Alois P. Heinz *)

Sum_{k=0..A000217(n)} k * T(n,k) = A001710(n+1) for n >= 1.
Sum_{k=0..A000217(n)} (1+k) * T(n,k) = A038720(n) for n >= 1.
Sum_{k=0..A000217(n)} (n*(n+1)/2-k) * T(n,k) = A317527(n+1).
T(n,A161680(n)) = A331518(n).
T(n,A000217(n)) = 1.

cp's OEIS Frontend

A263756 Triangle read by rows: T(n,k) (n>=0, k>=0) is the number of permutations of n with sum of descent bottoms equal to k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions