A263756 -id:A263756 - cp's OEIS frontend

A360288 Number T(n,k) of permutations of [n] whose excedance set is the k-th finite subset of positive integers in standard order; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.

1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 3, 7, 1, 3, 1, 1, 1, 15, 7, 31, 3, 17, 7, 15, 1, 7, 3, 7, 1, 3, 1, 1, 1, 31, 15, 115, 7, 69, 31, 115, 3, 37, 17, 69, 7, 37, 15, 31, 1, 15, 7, 31, 3, 17, 7, 15, 1, 7, 3, 7, 1, 3, 1, 1, 1, 63, 31, 391, 15, 245, 115, 675, 7, 145, 69

Offset: 0

Alois P. Heinz, Feb 01 2023

The list of finite subsets of positive integers in standard statistical (or Yates) order begins: {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, ... cf. A048793, A048794.
The excedance set of permutation p of [n] is the set of indices i with p(i)>i, a subset of [n-1].
All terms are odd.

			T(5,4) = 3: there are 3 permutations of [5] with excedance set {3} (the 4th subset in standard order): 12435, 12534, 12543.
Triangle T(n,k) begins:
  1;
  1;
  1,  1;
  1,  3, 1,  1;
  1,  7, 3,  7, 1,  3, 1,  1;
  1, 15, 7, 31, 3, 17, 7, 15, 1, 7, 3, 7, 1, 3, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..15, flattened
Wikipedia, Permutation
Wikipedia, Yates Order

Columns k=0-1 give: A000012, A000225(n-1) for n>=1.
Row sums give A000142.
Row lengths are A011782.
See A152884, A360289 for similar triangles.
Cf. A000027, A029767, A048793, A048794, A263756, A329369.

b:= proc(s, t) option remember; (m->
      `if`(m=0, x^(t/2), add(b(s minus {i}, t+
      `if`(i (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n}, 0)):
seq(T(n), n=0..7);

b[s_, t_] := b[s, t] = Function [m, If[m == 0, x^(t/2), Sum[b[s ~Complement~ {i}, t + If[i < m, 2^i, 0]], {i, s}]]][Length[s]];
T[n_] := CoefficientList[b[Range[n], 0], x];
Table[T[n], {n, 0, 7}]  // Flatten (* Jean-François Alcover, Feb 13 2023, after Alois P. Heinz *)

Sum_{k=0..2^(n-1)-1} (k+1) * T(n,k) = A029767(n) for n>=1.

Sum_{k=0..2^(n-1)-1} (2^n-1-k) * T(n,k) = A355258(n+1) for n>=1.

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.

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

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 3, 0, 1, 1, 0, 1, 3, 7, 1, 3, 7, 0, 1, 1, 0, 1, 3, 7, 16, 3, 14, 17, 32, 3, 7, 15, 0, 1, 1, 0, 1, 3, 7, 16, 34, 14, 32, 69, 72, 129, 32, 68, 70, 118, 7, 15, 31, 0, 1, 1, 0, 1, 3, 7, 16, 34, 77, 32, 100, 149, 274, 292, 496, 220, 388, 536

Offset: 0

Christian Stump, Oct 19 2015

Row sums give A000142.

Row lengths are given by A000217 for n>=1. - Omar E. Pol, Oct 25 2015

			Triangle begins:
  1;
  1;
  1,0,1;
  1,0,1,3,0,1;
  1,0,1,3,7,1,3,7,0,1;
  1,0,1,3,7,16,3,14,17,32,3,7,15,0,1;
  1,0,1,3,7,16,34,14,32,69,72,129,32,68,70,118,7,15,31,0,1;
  ...

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

Cf. A000142, A263756.

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^n, 1], {j, s}]]]];
T[n_] := With[{p = b[Range[n]]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
Table[T[n], {n, 0, 9}] // Flatten (* Jean-François Alcover, Apr 23 2025, after Alois P. Heinz *)

One term prepended and one term corrected by Alois P. Heinz, Oct 25 2015

A360289 Number T(n,k) of permutations of [n] whose excedance set is the k-th finite subset of positive integers in Gray order; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 7, 3, 1, 1, 3, 1, 1, 15, 31, 7, 7, 15, 17, 3, 1, 3, 1, 1, 3, 7, 7, 1, 1, 31, 115, 15, 31, 115, 69, 7, 7, 37, 31, 15, 17, 69, 37, 3, 1, 7, 7, 3, 1, 1, 3, 1, 3, 17, 15, 7, 7, 31, 15, 1, 1, 63, 391, 31, 115, 675, 245, 15, 31, 261, 391

Offset: 0

Alois P. Heinz, Feb 01 2023

The list of finite subsets of the positive integers in Gray order begins: {}, {1}, {1,2}, {2}, {2,3}, {1,2,3}, {1,3}, {3}, ... cf. A003188, A227738, A360287.
The excedance set of permutation p of [n] is the set of indices i with p(i)>i, a subset of [n-1].
All terms are odd.

			T(5,4) = 7: there are 7 permutations of [5] with excedance set {2,3} (the 4th subset in Gray order): 13425, 13524, 13542, 14523, 14532, 15423, 15432.
Triangle T(n,k) begins:
  1;
  1;
  1,  1;
  1,  3,  1, 1;
  1,  7,  7, 3, 1,  1,  3, 1;
  1, 15, 31, 7, 7, 15, 17, 3, 1, 3, 1, 1, 3, 7, 7, 1;
  ...

Alois P. Heinz, Rows n = 0..15, flattened
Wikipedia, Gray code
Wikipedia, Permutation

Columns k=0-1 give: A000012, A000225(n-1) for n>=1.
Row sums give A000142.
Row lengths are A011782.
See A152884, A360288 for similar triangles.
Cf. A000027, A003188, A006068, A227738, A263756, A360287.

a:= n-> `if`(n<2, n, Bits[Xor](n, a(iquo(n, 2)))):
b:= proc(s, t) option remember; (m->
      `if`(m=0, x^a(t/2), add(b(s minus {i}, t+
      `if`(i (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n}, 0)):
seq(T(n), n=0..7);

a[n_] := If[n < 2, n, BitXor[n, a[Quotient[n, 2]]]];
b[s_, t_] := b[s, t] = With[{m = Length[s]}, If[m == 0, x^a[t/2], Sum[b[s  ~Complement~ {i}, t + If[i < m, 2^i, 0]], {i, s}]]];
T[n_] := CoefficientList[b[Range[n], 0], x];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Dec 09 2023, after Alois P. Heinz *)

cp's OEIS Frontend

A360288 Number T(n,k) of permutations of [n] whose excedance set is the k-th finite subset of positive integers in standard order; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A360289 Number T(n,k) of permutations of [n] whose excedance set is the k-th finite subset of positive integers in Gray order; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica