login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle. 5
0, 0, 1, 9, 93, 1155, 17025, 292383, 5752131, 127790505, 3167896005, 86756071545, 2602658092419, 84917405260779, 2994675198208785, 113538315994418175, 4606094297461892895, 199122610252964803857, 9139190793845641425261, 443881600924216704982425 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

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.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..387

FORMULA

a(n) ~ (2*exp(3/2)-exp(1)) * n^(n-1). - Vaclav Kotesovec, Aug 20 2014

EXAMPLE

Any transposition (or disjoint combination) is one element to be counted.

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

f:{1,2,3}->{2,1,1} gives fof:{1,2,3}->{1,2,2} and fofof=f (cycle 2),

(the others are similar), thus giving a(3)=9.

MAPLE

with(combinat):

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*

      b(n-i*j, i-1), j=0..n/i)))

    end:

A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):

a:= n-> A(n, 2) -A(n, 1):

seq(a(n), n=0..25);  # Alois P. Heinz, Aug 19 2014

MATHEMATICA

multinomial[n_, k_List] := n!/Times @@ (k!);

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}]]];

A[n_, k_] :=  Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}];

a[0] = 0; a[n_] := A[n, 2] - A[n, 1];

Table[a[n], {n, 0, 25}] (* Jean-Fran├žois Alcover, Jun 05 2018, after Alois P. Heinz *)

CROSSREFS

Cf. A163947, A163952, A163859.

Column k=2 of A222029 and of A241981.

Sequence in context: A061635 A261688 A246212 * A231658 A034992 A048359

Adjacent sequences:  A163948 A163949 A163950 * A163952 A163953 A163954

KEYWORD

nonn

AUTHOR

Carlos Alves, Aug 06 2009

EXTENSIONS

a(0), a(8)-a(19) added and A246212 merged into this sequence by Alois P. Heinz, Aug 14 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 17 12:57 EDT 2019. Contains 327131 sequences. (Running on oeis4.)