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,6

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

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.

Example

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

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<m, i, [][])}), i=s)))(nops(s))
          end; (p->
      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

Crossrefs

Row sums are A000142.

See A360288, A360289 for similar triangles.

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

Sequence in context: A068845 A324910 A257100 * A360288 A263756 A204984

Adjacent sequences: A152881 A152882 A152883 * A152885 A152886 A152887

Keyword

nonn,look,tabf

Author

Emeric Deutsch, Jan 13 2009

Extensions

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

Status

approved