A360289 -id:A360289 - cp's OEIS frontend

A152884 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} with excedance set equal to the k-th subset of {1,2,...,n-1} (n>=0, 0<=k<=ceiling(2^(n-1))-1). The subsets of {1,2,...,n-1} are ordered according to size, while the subsets of the same size follow the lexicographic order.

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

Offset: 0

Emeric Deutsch, Jan 13 2009

For example, the eight subsets of {1,2,3} are ordered as empty,1,2,3,12,13,23,123. The excedance set of a permutation p of {1,2,...,n} is the set of indices i such that p(i)>i; it is a subset of {1,2,...,n-1}.
Row n contains ceiling(2^(n-1)) entries.
Sum of entries in row n is n! (A000142).
The given Maple program yields the term of the sequence corresponding to a specified permutation size n and a specified excedance set A.
All terms are odd. - Alois P. Heinz, Jan 31 2023

			T(5,3) = 3 because the 3rd subset of {1,2,3,4} is {3} and the permutations of {1,2,3,4,5} with excedance set {3} are 12435, 12534 and 12543.
T(5,4) = 1: 12354 (4th subset of {1,2,3,4} is {4}).
Triangle starts:
      k=0   1  2  3  4   5   6  7  8 ...
  n=0:  1;
  n=1:  1;
  n=2:  1,  1;
  n=3:  1,  3, 1, 1;
  n=4:  1,  7, 3, 1, 7,  3,  1, 1;
  n=5:  1, 15, 7, 3, 1, 31, 17, 7, 7, 3, 1, 15, 7, 3, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..15, flattened
R. Ehrenborg and E. Steingrimsson, The excedance set of a permutation, Advances in Appl. Math., 24, 284-299, 2000.

Row sums are A000142.
See A360288, A360289 for similar triangles.
Cf. A000225, A011782, A082185, A136126, A193360, A329369 (another version).

n := 7: A := {1, 2, 4}: with(combinat): P := permute(n): EX := proc (p) local S, i: S := {}: for i to n-1 do if i < p[i] then S := `union`(S, {i}) else end if end do: S end proc: ct := 0: for j to factorial(n) do if EX(P[j]) = A then ct := ct+1 else end if end do: ct;
# second Maple program:
T:= proc(n) option remember; uses combinat; local b, i, l;
      l:= map(x-> {x[]}, [seq(choose([$1..n-1], i)[], i=0..n-1)]):
      for i to nops(l) do h(l[i]):=i od:
      b:= proc(s, l) option remember; (m->
           `if`(m=0, x^h(l), add(b(s minus {i}, {l[],
           `if`(i
      seq(coeff(p, x, i), i=1..degree(p)))(b({$1..n}, {}))
    end: T(0):=1:
seq(T(n), n=0..8);  # Alois P. Heinz, Jan 29 2023

T(n,k) = A000225(n-k) = 2^(n-k) - 1 for n>k>0. - Alexander R. Povolotsky, May 14 2025

T(0,0)=1 prepended and indexing adapted by Alois P. Heinz, Jan 29 2023

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.

Original entry on oeis.org

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.

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions