A335845 Irregular triangular array T(n,k) read by rows. Row n gives the number of permutations of {1,2,...,n} whose descent set is S for each subset S of {1,2,...,n-1} ordered lexicographically within the rows.

1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 3, 3, 5, 3, 1, 1, 4, 9, 9, 4, 6, 16, 11, 11, 16, 6, 4, 9, 9, 4, 1, 1, 5, 14, 19, 14, 5, 10, 35, 40, 19, 26, 61, 40, 26, 35, 10, 10, 35, 26, 40, 61, 26, 19, 40, 35, 10, 5, 14, 19, 14, 5, 1, 1, 6, 20, 34, 34, 20, 6, 15, 64, 99

Offset: 0

Author

Geoffrey Critzer, Jun 26 2020

Keywords

• nonn
• tabf

Comments

Row lengths are A011782(n).

Every row begins and ends with a 1 because there is exactly 1 n-permutation whose descent set is the empty set and there is exactly 1 n-permutation whose descent set is {1,2,...,n-1}, namely the identity permutation and its reverse.

Examples

			T(5,5) = 6 because there are 6 permutations of [5] whose descent set is {1,2}: (3,2,1,4,5), (4,2,1,3,5), (4,3,1,2,5), (5,2,1,3,4), (5,3,1,2,4), (5,4,1,2,3).
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2, 2, 1;
  1, 3, 5, 3, 3, 5,  3,  1;
  1, 4, 9, 9, 4, 6, 16, 11, 11, 16, 6, 4, 9, 9, 4, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..15, flattened

Crossrefs

Row sums give A000142.

Cf. A011782, A060350, A060351, A082185.

Programs

Maple

T:= proc(n) option remember; local b, i, l; l:=
      map(x-> add(2^(i-1), i=x), [seq(combinat[choose](
              [$1..n-1], i)[], i=0..n-1)]); h(0):=0;
      for i to nops(l) do h(l[i]):= (i-1) od: b:=
      proc(u, o, t) option remember; `if`(u+o=0, x^h(t),
        add(b(u-j, o+j-1, t), j=1..u)+
        add(b(u+j-1, o-j, t+2^(u+o-1)), j=1..o))
      end; (p->
      seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2))
    end:
seq(T(n), n=0..7);  # Alois P. Heinz, Feb 03 2023

Mathematica

f[list_] := (-1)^(Length[list] + 1) Apply[Multinomial, list];
Table[g[S_] :=Abs[Total[Map[f, Map[Differences,Map[Prepend[#, 0] &, Map[Append[#, n] &, Subsets[S]]]]]]];Map[g, Subsets[Range[n - 1]]], {n, 1, 5}] // Grid

Extensions

T(0,0)=1 prepended by Alois P. Heinz, Sep 08 2020