A225753 Triangle of transformations with k monotonic runs.

1, 3, 1, 10, 16, 1, 35, 155, 65, 1, 126, 1246, 1506, 246, 1, 462, 9142, 24017, 12117, 917, 1, 1716, 63792, 315918, 349840, 88852, 3424, 1, 6435, 432399, 3707559, 7635987, 4362297, 619677, 12861, 1, 24310, 2881450, 40455910, 140543458, 149803270, 49462810, 4200670, 48610, 1

Offset

1,2

Comments

Analogous to the Eulerian triangle for permutations A173018.

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]

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

Links

Alois P. Heinz, Rows n = 1..100, flattened

Example

T(1,1) = #{[0]} = 1.
T(2,1) = #{[0,0], [0,1], [1,1]} = 3.
T(2,2) = #{[1,0]} = 1.
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.
Triangle T(n,k) begins:
     1;
     3,     1;
    10,    16,      1;
    35,   155,     65,      1;
   126,  1246,   1506,    246,     1;
   462,  9142,  24017,  12117,   917,    1;
  1716, 63792, 315918, 349840, 88852, 3424,  1;
  ...

Maple

b:= proc(n, l, k) option remember; local j;
      if n=0 then [1] else []; for j to k do zip((x, y)->x+y,
       %, [`if`(j<l, 0, [][]), b(n-1, j, k)[]], 0) od; % fi
    end:
T:= n-> b(n, 0, n)[]:
seq(T(n), n=1..10);  # Alois P. Heinz, Jun 26 2013

Mathematica

Table[Distribution[Map[Length, Map[Split[#, LessEqual[#1, #2]&]&, Tuples[Range[1, n], n]]]], {n, 1, 7}]//Grid (* Geoffrey Critzer, Jun 25 2013 *)
zip[f_, x_, y_, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];
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[n_] := b[n, 0, n];
Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Dec 05 2023, after Alois P. Heinz *)

Prog

(Ruby 1.9+)
counting_numbers = Enumerator.new do |yielder|
  (0..1.0/0).each do |number|
    yielder.yield number
  end
end
def mono_runs(trans)
  count =1
  1.upto(trans.length-1) do |index|
    if (trans[index-1]>trans[index])
      count = count +1
    end
  end
  count
end
1.upto(10) do |index|
  tran_size =index
  counts = []
  0.upto(index) do
    counts.push(0)
  end
  counting_numbers.take(tran_size).repeated_permutation(tran_size).each { |x|
    runs = mono_runs(x)
    counts[runs] = counts[runs]+1
  }
  puts index.inspect + "|" + counts.inspect # + "|" + counts.inject(:+).inspect
end

Crossrefs

First column is A001700(n-1).

Row sums give: A000312.

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

Sequence in context: A212930 A225725 A095327 * A210725 A048953 A358987

Adjacent sequences: A225750 A225751 A225752 * A225754 A225755 A225756

Keyword

nonn,tabl

Author

Chad Brewbaker, May 14 2013

Status

approved