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

Author

Emeric Deutsch, Jan 13 2009

Keywords

• nonn
• look
• tabf

Comments

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

Examples

			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;
  ...
		

Links

• 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.

Crossrefs

Row sums are A000142.

See A360288, A360289 for similar triangles.

Cf. A000225, A011782, A082185, A136126, A193360, A329369 (another version).

Programs

Maple

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

Formula

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

Extensions

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