|
| |
|
|
A224541
|
|
Number of doubly-surjective functions f:[n]->[3].
|
|
2
|
|
|
|
90, 630, 2940, 11508, 40950, 137610, 445896, 1410552, 4390386, 13514046, 41278068, 125405532, 379557198, 1145747538, 3452182656, 10388002848, 31230066186, 93828607686, 281775226860, 845929656900, 2539047258150, 7619759016090, 22864712861880, 68605412870088
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
6,1
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
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.
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)
|
|
|
EXAMPLE
|
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.
|
|
|
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 *)
|
|
|
PROG
|
(PARI) x='x+O('x^66); Vec(serlaplace((exp(x)-x-1)^3)) \\ Joerg Arndt, Apr 10 2013
|
|
|
CROSSREFS
|
Cf. A052515, the number of doubly-surjective functions f:[n]->[2].
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
