cp's OEIS Frontend

A216971 Triangle read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k nonrecurrent elements mapped to some (one or more) recurrent element. n >= 1, 0 <= k <= n-1.

%I A216971 #43 Aug 09 2022 07:04:23
%S A216971 1,2,2,6,18,3,24,156,72,4,120,1520,1260,220,5,720,17310,21000,7020,
%T A216971 600,6,5040,232932,363720,187320,32970,1554,7,40320,3698744,6794256,
%U A216971 4746840,1351840,141288,3920,8,362880,68680656,139241088,121105152,48822480,8625456,573048,9720,9,3628800,1471193370
%N A216971 Triangle read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k nonrecurrent elements mapped to some (one or more) recurrent element. n >= 1, 0 <= k <= n-1.
%C A216971 x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph.
%C A216971 Row sums = n^n.
%C A216971 First column (k = 0) counts the n! bijective functions.
%C A216971 T(n,n-1) counts the n constant functions.
%C A216971 Conjecture: every entry in row n is divisible by n. - _Jon Perry_, Sep 21 2012
%H A216971 Joerg Arndt, <a href="/A216971/b216971.txt">Table of n, a(n) for n = 1..528</a>
%F A216971 E.g.f.: 1/(1-x*exp(y*T(x))) - 1 where T(x) is the e.g.f. for A000169.
%F A216971 Sum_{k=1..n-1} k * T(n,k) = A001864(n). - _Geoffrey Critzer_, Jan 01 2013
%e A216971 Triangle starts:
%e A216971      1,
%e A216971      2,      2,
%e A216971      6,     18,      3,
%e A216971     24,    156,     72,      4,
%e A216971    120,   1520,   1260,    220,      5,
%e A216971    720,  17310,  21000,   7020,    600,      6,
%e A216971   5040, 232932, 363720, 187320,  32970,   1554,      7,
%e A216971   ...
%t A216971 nn=7;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];f[list_]:=Select[list,#>0&];Drop[Map[f,Range[0,nn]! CoefficientList[Series[1/(1-x Exp[y t]),{x,0,nn}],{x,y}]],1]//Grid
%o A216971 (PARI)
%o A216971 N=15; x='x+O('x^N);
%o A216971 T=serreverse(x*exp(-x));
%o A216971 egf=1/(1-x*exp('y*T)) - 1;
%o A216971 v=Vec(serlaplace(egf));
%o A216971 { for (n=1, N-1, /* print triangle: */
%o A216971     row = Pol( v[n], 'y );
%o A216971     row = polrecip( row );
%o A216971     print( Vec(row) );
%o A216971 ); }
%o A216971 /* _Joerg Arndt_, Sep 21 2012 */
%Y A216971 Cf. A001864.
%K A216971 nonn,nice,tabl
%O A216971 1,2
%A A216971 _Geoffrey Critzer_, Sep 21 2012