cp's OEIS Frontend

A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.

%I A163951 #22 Jun 05 2018 07:25:32
%S A163951 0,0,1,9,93,1155,17025,292383,5752131,127790505,3167896005,
%T A163951 86756071545,2602658092419,84917405260779,2994675198208785,
%U A163951 113538315994418175,4606094297461892895,199122610252964803857,9139190793845641425261,443881600924216704982425
%N A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.
%C A163951 The number of functions in a finite set {1,..,n} for which the sequence of composition powers ends in a fixed point gave terms of the sequence A000272(n-1)=(n+1)^(n-1).
%C A163951 This is to be seen as a conjecture, and the sequence ending with a length 2 cycle does not seem to have such an easy expression.
%H A163951 Alois P. Heinz, <a href="/A163951/b163951.txt">Table of n, a(n) for n = 0..387</a>
%F A163951 a(n) ~ (2*exp(3/2)-exp(1)) * n^(n-1). - _Vaclav Kotesovec_, Aug 20 2014
%e A163951 Any transposition (or disjoint combination) is one element to be counted.
%e A163951 When n=2, there is only one, and a(2)=1. When n=3, there are only 3 transpositions, but there are other 6 elements, for instance
%e A163951 f:{1,2,3}->{2,1,1} gives fof:{1,2,3}->{1,2,2} and fofof=f (cycle 2),
%e A163951 (the others are similar), thus giving a(3)=9.
%p A163951 with(combinat):
%p A163951 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A163951       add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
%p A163951       b(n-i*j, i-1), j=0..n/i)))
%p A163951     end:
%p A163951 A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
%p A163951 a:= n-> A(n, 2) -A(n, 1):
%p A163951 seq(a(n), n=0..25);  # _Alois P. Heinz_, Aug 19 2014
%t A163951 multinomial[n_, k_List] := n!/Times @@ (k!);
%t A163951 b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[(i - 1)!^j*multinomial[ n, Join[{n - i*j}, Table[i, j]]]/j!*b[n - i*j, i - 1], {j, 0, n/i}]]];
%t A163951 A[n_, k_] :=  Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}];
%t A163951 a[0] = 0; a[n_] := A[n, 2] - A[n, 1];
%t A163951 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Jun 05 2018, after _Alois P. Heinz_ *)
%Y A163951 Cf. A163947, A163952, A163859.
%Y A163951 Column k=2 of A222029 and of A241981.
%K A163951 nonn
%O A163951 0,4
%A A163951 _Carlos Alves_, Aug 06 2009
%E A163951 a(0), a(8)-a(19) added and A246212 merged into this sequence by _Alois P. Heinz_, Aug 14 2017