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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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.

LINKS

Table of n, a(n) for n=6..29.

Dennis Walsh, Notes on doubly-surjective finite functions

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)

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

Sequence in context: A203780 A295982 A065949 * A051695 A304165 A232588

Adjacent sequences:  A224538 A224539 A224540 * A224542 A224543 A224544

KEYWORD

nonn,easy

AUTHOR

Dennis P. Walsh, Apr 09 2013

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 May 21 14:57 EDT 2019. Contains 323443 sequences. (Running on oeis4.)