A224541 Number of doubly-surjective functions f:[n]->[3].

90, 630, 2940, 11508, 40950, 137610, 445896, 1410552, 4390386, 13514046, 41278068, 125405532, 379557198, 1145747538, 3452182656, 10388002848, 31230066186, 93828607686, 281775226860, 845929656900, 2539047258150, 7619759016090, 22864712861880, 68605412870088

Offset: 6

Author

Dennis P. Walsh, Apr 09 2013

Keywords

• nonn
• easy

Comments

Third column of A200091.

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

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.

Examples

			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:
112233, 112323, 112332, 113223, 113232, 113322,
121233, 121323, 121332, 122133, 122313, 122331,
123123, 123132, 123213, 123231, 123312, 123321,
131223, 131232, 131322, 132123, 132132, 132213,
132231, 132312, 132321, 133122, 133212, 133221.
		

Links

• Dennis Walsh, Notes on doubly-surjective finite functions

Crossrefs

Cf. A052515, the number of doubly-surjective functions f:[n]->[2].

Programs

Maple

seq(3^n-3*2^n-3*n*2^(n-1)+3+3*n+3*n^2, n=6..40);

Mathematica

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

PARI

x='x+O('x^66); Vec(serlaplace((exp(x)-x-1)^3)) \\ Joerg Arndt, Apr 10 2013

Formula

a(n) = 3^n-3*2^n-3*n*2^(n-1)+3+3*n+3*n^2.

E.g.f.: (exp(x)-x-1)^3.

From Alois P. Heinz, Apr 10 2013: (Start)

a(n) = 6*A000478(n).

G.f.: -6*(12*x^3-40*x^2+45*x-15)*x^6 / ((3*x-1)*(2*x-1)^2*(x-1)^3).

(End)