OFFSET
2,4
COMMENTS
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
REFERENCES
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, page 100-109.
LINKS
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
FORMULA
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
EXAMPLE
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.
MAPLE
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
MATHEMATICA
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 *)
PROG
(GAP) 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
CROSSREFS
KEYWORD
nonn,easy,tabf
AUTHOR
Peter Bala, Dec 04 2011
STATUS
approved