login
Triangle of functions in a size n set for which the sequence of composition powers starts with a length k stem (index) before entering a cycle (period).
1

%I #62 Feb 15 2022 20:29:27

%S 1,1,4,21,6,148,84,24,1305,1160,540,120,13806,17610,10560,3960,720,

%T 170401,296772,214410,104160,32760,5040,2403640,5536440,4692576,

%U 2686320,1115520,302400,40320,38143377,113680800,111488328,72080064,35637840

%N Triangle of functions in a size n set for which the sequence of composition powers starts with a length k stem (index) before entering a cycle (period).

%C Given a transformation t from the transformation semigroup Tn and a positive integer i, the largest whole number s such that there does not exist an i such that t^s = t^(s+i) under transformation composition with t is the stem length. Terms in t^(s+i) form a cycle under repeated composition with t and do not return to transformations contained in the stem. Permutations by definition have stem length 0.

%H Chad Brewbaker, <a href="/A225540/b225540.txt">Table of n, a(n) for n = 0..46</a>

%e Triangle begins:

%e 1;

%e 1;

%e 4;

%e 21, 6;

%e 148, 84, 24;

%e 1305, 1160, 540, 120;

%e 13806, 17610, 10560, 3960, 720;

%e 170401, 296772, 214410, 104160, 32760, 5040;

%e ...

%t nn = 10; Map[Select[#, # > 0 &] &,Table[Range[0, nn]! CoefficientList[ Series[Prepend[Exp[Log[1/(1 - NestList[x Exp[#] &, x Exp[x], nn])]],0][[k + 1]] - Prepend[Exp[Log[1/(1 - NestList[x Exp[#] &, x Exp[x], nn])]], 0][[k]], {x, 0, nn}], x], {k, 1, nn - 1}] // Transpose] // Grid (* _Geoffrey Critzer_, Feb 13 2022 *)

%o (Ruby) # needs version 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 trans_mult(transa, transb)

%o trans_ret = Array.new

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

%o trans_ret.push(transa[transb[index]])

%o end

%o return trans_ret

%o end

%o def lolipop(trans)

%o trans_hash ={}

%o trans_hash[trans.clone] =0

%o index = 1

%o trans_current = trans_mult(trans, trans)

%o while trans_hash[trans_current] == nil

%o trans_hash[trans_current.clone] = index

%o index = index +1

%o trans_current = trans_mult(trans_current, trans)

%o end

%o cycle_length =trans_hash.size - trans_hash[trans_current]

%o return [trans_hash.size, cycle_length]

%o end

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

%o tran_size =index

%o histo_hash = {}

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

%o size, cycle_length = lolipop(x)

%o #tail_length = size-cycle_length

%o if (histo_hash[size-cycle_length] == nil)

%o histo_hash[size-cycle_length] =1

%o else

%o histo_hash[size-cycle_length] = histo_hash[size-cycle_length]+1

%o end

%o }

%o puts "#{tran_size}|" + histo_hash.inspect

%o end

%Y The first column is A006153.

%Y Row sums give A000312.

%Y Cf. A216242.

%K nonn,tabf

%O 0,3

%A _Chad Brewbaker_, May 14 2013