cp's OEIS Frontend

A225753 Triangle of transformations with k monotonic runs.

%I A225753 #43 Dec 05 2023 12:05:38
%S A225753 1,3,1,10,16,1,35,155,65,1,126,1246,1506,246,1,462,9142,24017,12117,
%T A225753 917,1,1716,63792,315918,349840,88852,3424,1,6435,432399,3707559,
%U A225753 7635987,4362297,619677,12861,1,24310,2881450,40455910,140543458,149803270,49462810,4200670,48610,1
%N A225753 Triangle of transformations with k monotonic runs.
%C A225753 Analogous to the Eulerian triangle for permutations A173018.
%C A225753 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 A225753 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 A225753 Alois P. Heinz, <a href="/A225753/b225753.txt">Rows n = 1..100, flattened</a>
%e A225753 T(1,1) = #{[0]} = 1.
%e A225753 T(2,1) = #{[0,0], [0,1], [1,1]} = 3.
%e A225753 T(2,2) = #{[1,0]} = 1.
%e A225753 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 A225753 Triangle T(n,k) begins:
%e A225753      1;
%e A225753      3,     1;
%e A225753     10,    16,      1;
%e A225753     35,   155,     65,      1;
%e A225753    126,  1246,   1506,    246,     1;
%e A225753    462,  9142,  24017,  12117,   917,    1;
%e A225753   1716, 63792, 315918, 349840, 88852, 3424,  1;
%e A225753   ...
%p A225753 b:= proc(n, l, k) option remember; local j;
%p A225753       if n=0 then [1] else []; for j to k do zip((x, y)->x+y,
%p A225753        %, [`if`(j<l, 0, [][]), b(n-1, j, k)[]], 0) od; % fi
%p A225753     end:
%p A225753 T:= n-> b(n, 0, n)[]:
%p A225753 seq(T(n), n=1..10);  # _Alois P. Heinz_, Jun 26 2013
%t A225753 Table[Distribution[Map[Length,Map[Split[#,LessEqual[#1,#2]&]&,Tuples[Range[1,n],n]]]],{n,1,7}]//Grid (* _Geoffrey Critzer_, Jun 25 2013 *)
%t A225753 zip[f_, x_, y_, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];
%t A225753 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 A225753 T[n_] := b[n, 0, n];
%t A225753 Table[T[n], {n, 1, 10}] // Flatten (* _Jean-François Alcover_, Dec 05 2023, after _Alois P. Heinz_ *)
%o A225753 (Ruby 1.9+)
%o A225753 counting_numbers = Enumerator.new do |yielder|
%o A225753   (0..1.0/0).each do |number|
%o A225753     yielder.yield number
%o A225753   end
%o A225753 end
%o A225753 def mono_runs(trans)
%o A225753   count =1
%o A225753   1.upto(trans.length-1) do |index|
%o A225753     if (trans[index-1]>trans[index])
%o A225753       count = count +1
%o A225753     end
%o A225753   end
%o A225753   count
%o A225753 end
%o A225753 1.upto(10) do |index|
%o A225753   tran_size =index
%o A225753   counts = []
%o A225753   0.upto(index) do
%o A225753     counts.push(0)
%o A225753   end
%o A225753   counting_numbers.take(tran_size).repeated_permutation(tran_size).each { |x|
%o A225753     runs = mono_runs(x)
%o A225753     counts[runs] = counts[runs]+1
%o A225753   }
%o A225753   puts index.inspect + "|" + counts.inspect # + "|" + counts.inject(:+).inspect
%o A225753 end
%Y A225753 First column is A001700(n-1).
%Y A225753 Row sums give: A000312.
%Y A225753 Cf. A008292, A062023, A190295, A226998, A333829.
%K A225753 nonn,tabl
%O A225753 1,2
%A A225753 _Chad Brewbaker_, May 14 2013