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