A225540 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, 1, 4, 21, 6, 148, 84, 24, 1305, 1160, 540, 120, 13806, 17610, 10560, 3960, 720, 170401, 296772, 214410, 104160, 32760, 5040, 2403640, 5536440, 4692576, 2686320, 1115520, 302400, 40320, 38143377, 113680800, 111488328, 72080064, 35637840

Offset

0,3

Comments

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.

Links

Chad Brewbaker, Table of n, a(n) for n = 0..46

Example

Triangle begins:
       1;
       1;
       4;
      21,      6;
     148,     84,     24;
    1305,   1160,    540,    120;
   13806,  17610,  10560,   3960,   720;
  170401, 296772, 214410, 104160, 32760, 5040;
  ...

Mathematica

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 *)

Prog

(Ruby) # needs version 1.9+
counting_numbers = Enumerator.new do |yielder|
  (0..1.0/0).each do |number|
    yielder.yield number
  end
end
def trans_mult(transa, transb)
  trans_ret = Array.new
  0.upto(transa.length-1) do |index|
    trans_ret.push(transa[transb[index]])
  end
  return trans_ret
end
def lolipop(trans)
  trans_hash ={}
  trans_hash[trans.clone] =0
  index = 1
  trans_current = trans_mult(trans, trans)
  while  trans_hash[trans_current] == nil
    trans_hash[trans_current.clone] = index
    index = index +1
    trans_current = trans_mult(trans_current, trans)
  end
  cycle_length =trans_hash.size - trans_hash[trans_current]
  return [trans_hash.size, cycle_length]
end
1.upto(10) do |index|
  tran_size =index
  histo_hash = {}
  counting_numbers.take(tran_size).repeated_permutation(tran_size).each { |x|
    size, cycle_length = lolipop(x)
    #tail_length = size-cycle_length
    if (histo_hash[size-cycle_length] == nil)
      histo_hash[size-cycle_length] =1
    else
      histo_hash[size-cycle_length] = histo_hash[size-cycle_length]+1
    end
  }
  puts "#{tran_size}|" + histo_hash.inspect
end

Crossrefs

The first column is A006153.

Row sums give A000312.

Cf. A216242.

Sequence in context: A272969 A327085 A083192 * A128452 A333433 A202450

Adjacent sequences: A225537 A225538 A225539 * A225541 A225542 A225543

Keyword

nonn,tabf

Author

Chad Brewbaker, May 14 2013

Status

approved