login
Triangle of transformations with k monotonic runs.
2

%I #43 Dec 05 2023 12:05:38

%S 1,3,1,10,16,1,35,155,65,1,126,1246,1506,246,1,462,9142,24017,12117,

%T 917,1,1716,63792,315918,349840,88852,3424,1,6435,432399,3707559,

%U 7635987,4362297,619677,12861,1,24310,2881450,40455910,140543458,149803270,49462810,4200670,48610,1

%N Triangle of transformations with k monotonic runs.

%C Analogous to the Eulerian triangle for permutations A173018.

%C T(n,k) is the number of words of length n over the alphabet {0,1,...,n-1} that have k-1 descents, see example. [_Joerg Arndt_, Jun 25 2013]

%C The expected number of descents is (Sum_{k=1..n} (k-1)*T(n,k)) / (Sum_{k=1..n} T(n,k)) = (n + 1/n -2)/2. - _Geoffrey Critzer_, Jun 26 2013

%H Alois P. Heinz, <a href="/A225753/b225753.txt">Rows n = 1..100, flattened</a>

%e T(1,1) = #{[0]} = 1.

%e T(2,1) = #{[0,0], [0,1], [1,1]} = 3.

%e T(2,2) = #{[1,0]} = 1.

%e T(3,1) = #{[0,0,0], [0,0,1], [0,0,2], [0,1,1], [0,1,2], [0,2,2], [1,1,1], [1,1,2], [1,2,2], [2,2,2]} = 10.

%e Triangle T(n,k) begins:

%e 1;

%e 3, 1;

%e 10, 16, 1;

%e 35, 155, 65, 1;

%e 126, 1246, 1506, 246, 1;

%e 462, 9142, 24017, 12117, 917, 1;

%e 1716, 63792, 315918, 349840, 88852, 3424, 1;

%e ...

%p b:= proc(n, l, k) option remember; local j;

%p if n=0 then [1] else []; for j to k do zip((x, y)->x+y,

%p %, [`if`(j<l, 0, [][]), b(n-1, j, k)[]], 0) od; % fi

%p end:

%p T:= n-> b(n, 0, n)[]:

%p seq(T(n), n=1..10); # _Alois P. Heinz_, Jun 26 2013

%t Table[Distribution[Map[Length,Map[Split[#,LessEqual[#1,#2]&]&,Tuples[Range[1,n],n]]]],{n,1,7}]//Grid (* _Geoffrey Critzer_, Jun 25 2013 *)

%t zip[f_, x_, y_, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];

%t b[n_, l_, k_] := b[n, l, k] = Module[{j, pc}, If[n == 0, {1}, pc = {}; For[j = 1, j <= k, j++, pc = zip[Plus, pc, Join[If[j<l, {0}, {}], b[n-1, j, k]], 0]]; pc]];

%t T[n_] := b[n, 0, n];

%t Table[T[n], {n, 1, 10}] // Flatten (* _Jean-François Alcover_, Dec 05 2023, after _Alois P. Heinz_ *)

%o (Ruby 1.9+)

%o counting_numbers = Enumerator.new do |yielder|

%o (0..1.0/0).each do |number|

%o yielder.yield number

%o end

%o end

%o def mono_runs(trans)

%o count =1

%o 1.upto(trans.length-1) do |index|

%o if (trans[index-1]>trans[index])

%o count = count +1

%o end

%o end

%o count

%o end

%o 1.upto(10) do |index|

%o tran_size =index

%o counts = []

%o 0.upto(index) do

%o counts.push(0)

%o end

%o counting_numbers.take(tran_size).repeated_permutation(tran_size).each { |x|

%o runs = mono_runs(x)

%o counts[runs] = counts[runs]+1

%o }

%o puts index.inspect + "|" + counts.inspect # + "|" + counts.inject(:+).inspect

%o end

%Y First column is A001700(n-1).

%Y Row sums give: A000312.

%Y Cf. A008292, A062023, A190295, A226998, A333829.

%K nonn,tabl

%O 1,2

%A _Chad Brewbaker_, May 14 2013