login
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.
4

%I #23 Feb 03 2023 20:14:24

%S 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,

%T 1,5,14,19,14,5,10,35,40,19,26,61,40,26,35,10,10,35,26,40,61,26,19,40,

%U 35,10,5,14,19,14,5,1,1,6,20,34,34,20,6,15,64,99

%N 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.

%C Row lengths are A011782(n).

%C 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.

%H Alois P. Heinz, <a href="/A335845/b335845.txt">Rows n = 0..15, flattened</a>

%e 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).

%e Triangle T(n,k) begins:

%e 1;

%e 1;

%e 1, 1;

%e 1, 2, 2, 1;

%e 1, 3, 5, 3, 3, 5, 3, 1;

%e 1, 4, 9, 9, 4, 6, 16, 11, 11, 16, 6, 4, 9, 9, 4, 1;

%e ...

%p T:= proc(n) option remember; local b, i, l; l:=

%p map(x-> add(2^(i-1), i=x), [seq(combinat[choose](

%p [$1..n-1], i)[], i=0..n-1)]); h(0):=0;

%p for i to nops(l) do h(l[i]):= (i-1) od: b:=

%p proc(u, o, t) option remember; `if`(u+o=0, x^h(t),

%p add(b(u-j, o+j-1, t), j=1..u)+

%p add(b(u+j-1, o-j, t+2^(u+o-1)), j=1..o))

%p end; (p->

%p seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2))

%p end:

%p seq(T(n), n=0..7); # _Alois P. Heinz_, Feb 03 2023

%t f[list_] := (-1)^(Length[list] + 1) Apply[Multinomial, list];

%t 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

%Y Row sums give A000142.

%Y Cf. A011782, A060350, A060351, A082185.

%K nonn,tabf

%O 0,6

%A _Geoffrey Critzer_, Jun 26 2020

%E T(0,0)=1 prepended by _Alois P. Heinz_, Sep 08 2020