|
%I #12 Oct 01 2015 17:49:04
%S 90,630,2940,11508,40950,137610,445896,1410552,4390386,13514046,
%T 41278068,125405532,379557198,1145747538,3452182656,10388002848,
%U 31230066186,93828607686,281775226860,845929656900,2539047258150,7619759016090,22864712861880,68605412870088
%N Number of doubly-surjective functions f:[n]->[3].
%C Third column of A200091.
%C Also, a(n) is (i) the number of length-n words on the alphabet A, B, and C with each letter occurring at least twice; (ii) the number of ways to distribute n different toys to 3 different children so that each child gets at least 2 toys; (iii) the number of ways to put n numbered balls into 3 labeled boxes so that each box gets at least 2 balls; (iv) the number of n-digit positive integers consisting only of the digits 1, 2, and 3 with each of these digits appearing at least twice. A doubly-surjective function f has size at least 2 for each pre-image set, that is, |f^-1(y)|>=2 for each element y of the codomain.[Note that a surjective function has |f^-1(y)|>=1.] The triangle A200091 provides the number of doubly-surjective functions f:[n]->[k]. Column 3 of triangle A200091 is a(n).
%C Sequence A052515 is the number of doubly-surjective functions f:[n]->[2] with exponential generating function (exp(x)-x-1)^2. In general, the number of doubly-surjective functions f:[n]->[k] has exponential generating function (exp(x)-x-1)^k.
%H Dennis Walsh, <a href="http://capone.mtsu.edu/dwalsh/DOUBSURJ.pdf">Notes on doubly-surjective finite functions</a>
%F a(n) = 3^n-3*2^n-3*n*2^(n-1)+3+3*n+3*n^2.
%F E.g.f.: (exp(x)-x-1)^3.
%F From _Alois P. Heinz_, Apr 10 2013: (Start)
%F a(n) = 6*A000478(n).
%F G.f.: -6*(12*x^3-40*x^2+45*x-15)*x^6 / ((3*x-1)*(2*x-1)^2*(x-1)^3).
%F (End)
%e For n=6 we have a(6)=90 since there are 90 six-digit positive integers using only digits 1, 2, and 3 with each of those digits appearing at least twice. The first 30 of the ninety, namely those with initial digit 1, are given below:
%e 112233, 112323, 112332, 113223, 113232, 113322,
%e 121233, 121323, 121332, 122133, 122313, 122331,
%e 123123, 123132, 123213, 123231, 123312, 123321,
%e 131223, 131232, 131322, 132123, 132132, 132213,
%e 132231, 132312, 132321, 133122, 133212, 133221.
%p seq(3^n-3*2^n-3*n*2^(n-1)+3+3*n+3*n^2, n=6..40);
%t With[{nn=40},Drop[CoefficientList[Series[(Exp[x]-x-1)^3,{x,0,nn}],x] Range[0,nn]!,6]] (* _Harvey P. Dale_, Oct 01 2015 *)
%o (PARI) x='x+O('x^66); Vec(serlaplace((exp(x)-x-1)^3)) \\ _Joerg Arndt_, Apr 10 2013
%Y Cf. A052515, the number of doubly-surjective functions f:[n]->[2].
%K nonn,easy
%O 6,1
%A _Dennis P. Walsh_, Apr 09 2013
|
