A224541 -id:A224541 - cp's OEIS frontend

A200091 The number of ways of putting n labeled items into k labeled boxes so that each box receives at least 2 objects.

1, 1, 1, 6, 1, 20, 1, 50, 90, 1, 112, 630, 1, 238, 2940, 2520, 1, 492, 11508, 30240, 1, 1002, 40950, 226800, 113400, 1, 2024, 137610, 1367520, 2079000, 1, 4070, 445896, 7271880, 22869000, 7484400, 1, 8164, 1410552, 35692800, 196396200, 194594400, 1, 16354

Offset: 2

Peter Bala, Dec 04 2011

Equivalently, the number of ordered set partitions of the set [n] into k blocks of size at least two. When the boxes are unlabeled or the set partitions unordered we obtain A008299.
The number of doubly-surjective functions f:[n]->[k], where a doubly-surjective function f has pre-image sets of size at least 2 for each element of the codomain. Also, the number of ways to distribute n different toys to k different children so that each child gets at least two toys. - Dennis P. Walsh, Apr 09 2013
T(n,k) is the number of chains 0 = x_0 < x_1 < ... < x_k = 1 in the Boolean lattice of rank n, such that x_i is not covered by x_(i+1) for all i. - Geoffrey Critzer, Jul 15 2018

			Table begins
  n |k=1   2     3     4
----+-------------------
  2 |  1
  3 |  1
  4 |  1   6
  5 |  1  20
  6 |  1  50    90
  7 |  1 112   630
  8 |  1 238  2940  2520
  9 |  1 492 11508 30240
  ...
T(4,2) = 6: The arrangements of 4 objects into 2 boxes { } and [ ] so that each box contains at least 2 items are {1,2}[3,4], {1,3}[2,4], {2,3}[1,4] and the 3 other possibilities where the contents of a pair of boxes are swapped.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, page 100-109.

Muniru A Asiru, Table of n, a(n) for n = 2..626
Marko R. Riedel, Count by PIE and symbolic combinatorics, Math Stackexchange, March 2022.
Dennis Walsh, Notes on doubly-surjective finite functions

T(n,2) = A052515(n), T(n,3) = A224541(n), T(n,4) = A224542(n).
Cf. A032032 (row sums).
Cf. A008299, A019538, A200092.

Flat(List([2..14],n->List([1..Int(n/2)],k->Sum([0..k],j->(-1)^j*Binomial(k,j)*(Sum([0..j],i->Binomial(j,i)*(Binomial(n,i)*Factorial(i)*(k-j)^(n-i)))))))); # Muniru A Asiru, Jul 17 2018

seq(seq(eval(diff((exp(x)-x-1)^k,x$n),x=0),k=1..floor(n/2)),n=2..20); # Dennis P. Walsh, Apr 09 2013
T := proc(n,k) local r; k!* add(binomial(n,r)*(-1)^r*Stirling2(n-r,k-r), r=0..min(n,k)); end; # Marko Riedel, Mar 25 2022

t[n_, k_] := k! * Sum[ (-1)^i*Binomial[n, i] * Sum[ (-1)^j*(k - i - j)^(n - i) / (j!*(k - i - j)!), {j, 0, k - i}], {i, 0, k}]; Table[ t[n, k], {n, 2, 14}, {k, 1, n/2}] // Flatten (* Jean-François Alcover, Apr 10 2013 *)

E.g.f. with additional 1: 1/(1-t*(exp(x)-1-x)) = 1 + t*x^2/2! + t*x^3/3! + (t+6*t^2)*x^4/4! + ....
E.g.f. (k fixed): (exp(x)-x-1)^k. - Dennis P. Walsh, Apr 09 2013
Recurrence relation: T(n+1,k) = k*(T(n,k) + n*T(n-1,k-1)). T(n,k) = k!*A008299(n,k).
T(n,k+j) = Sum_{i=0..n} C(n,i)*T(i,k)*T(n-i,j). - Dennis P. Walsh, Apr 09 2013
T(n,k) = Sum_{j=0..k} (-1)^j*C(k,j)*(Sum_{i=0..j} C(j,i)*C(n,i)*i!*(k-j)^(n-i)) for 1 <= k <= n/2 and n >= 2. - Dennis P. Walsh, Apr 10 2013
T(n,k) = k!*Sum_{r=0..min(n,k)} binomial(n,r)*(-1)^r*Stirling2(n-r, k-r). - Marko Riedel, Mar 25 2022

A224542 Number of doubly-surjective functions f:[n]->[4].

Original entry on oeis.org

2520, 30240, 226800, 1367520, 7271880, 35692800, 165957792, 742822080, 3234711480, 13803744864, 58021888080, 241116750624, 993313349544, 4064913201216, 16549636147968, 67112688842496, 271323921459096, 1094303232174240, 4405390451382960, 17709538489849440

Offset: 8

Dennis P. Walsh, Apr 09 2013

Fourth column of A200091: A200091(n,4)=a(n).
Also, a(n) is (i) the number of length-n words on the alphabet A, B, C, and D with each letter of the alphabet occurring at least twice; (ii) the number of ways to distribute n different toys to 4 children so that each child gets at least two toys; (iii) the number of ways to put n numbered balls into 4 labeled boxes so that each box gets at least two balls; (iv) the number of n-digit positive integers consisting of only digits 1,2,3, and 4 with each of these digits appearing at least twice.
A doubly-surjective function f:D->C is such that the pre-image set f^-1(y) has size at least 2 for each y in C.
Triangle A200091 provides the number of doubly-surjective functions f from a set of size n onto a set of size k. Hence a(n) is column 4 of A200091.

			a(9) = 30240 since there are 30240 ways to distribute 9 different toys to 4 children so that each child gets at least 2 toys. One child must get 3 toys and the other children get 2 toys each. There are 4 ways to pick the lucky kid. There are C(9,3) ways to choose the 3 toys for the lucky kid. There are 6!/(2!)^3 ways to distribute the remaining 6 toys among the 3 kids. We obtain 4*C(9,3)*6!/8=30240.

Dennis Walsh, Notes on doubly-surjective finite functions

Cf. A224541, A052515.

seq(eval(diff((exp(x)-x-1)^4,x$n),x=0),n=8..40);

nn=27; Drop[Range[0,nn]! CoefficientList[Series[(Exp[x]-x-1)^4, {x,0,nn}], x], 8] (* Geoffrey Critzer, Sep 28 2013 *)

my(x='x+O('x^66)); Vec(serlaplace((exp(x)-x-1)^4)) /* Joerg Arndt, Apr 10 2013 */

a(n) = 4^n-4*3^n-4*n*3^(n-1)+(9*n+3*n^2)*2^(n-1)+6*2^n-4-8*n-4*n^3;
a(n) = sum(n!/(i!*j!*k!*m!)) over  such that i,j,k, and m are all at least 2 and i+j+k+m=n.
E.g.f.: (exp(x)-x-1)^4.
a(n) = 24*A058844(n). - Alois P. Heinz, Apr 10 2013
G.f.: 24*x^8*(288*x^6-1560*x^5+3500*x^4-4130*x^3+2625*x^2-840*x+105) / ((x-1)^4*(2*x-1)^3*(3*x-1)^2*(4*x-1)). - Colin Barker, Jun 04 2013

cp's OEIS Frontend

A200091 The number of ways of putting n labeled items into k labeled boxes so that each box receives at least 2 objects.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

Formula