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

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.

Links

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

Example

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

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

Crossrefs

Row sums give A000142.

Cf. A011782, A060350, A060351, A082185.

Sequence in context: A292741 A356802 A060351 * A357611 A290252 A336706

Adjacent sequences: A335842 A335843 A335844 * A335846 A335847 A335848

Keyword

nonn,tabf

Author

Geoffrey Critzer, Jun 26 2020

Extensions

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

Status

approved