A200092 -id:A200092 - cp's OEIS frontend

A102233 Number of preferential arrangements of n labeled elements when at least k=3 elements per rank are required.

1, 0, 0, 1, 1, 1, 21, 71, 183, 2101, 13513, 64285, 629949, 5762615, 41992107, 427215283, 4789958371, 47283346849, 540921904725, 6980052633257, 85901272312905, 1129338979629643, 16398293425501375, 238339738265039119, 3588600147767147775, 58124879519314730741

Offset: 0

Thomas Wieder, Jan 01 2005

nonn

The labeled case for at least k=2 elements per rank is given by A032032 = Partition n labeled elements into sets of sizes of at least 2 and order the sets. The unlabeled case for at least k=3 elements per rank is given by A000930 = A Lamé sequence of higher order. The unlabeled case for at least k=2 elements per rank is given by A000045 = Fibonacci numbers.
With m = floor(n/3), a(n) is the number of ways to distribute n different toys to m numbered children such that each child receiving a toy gets at least three toys and, if child k gets no toys, then each child numbered higher than k also gets no toys. Furthermore, a(n)= row sums of triangle A200092 for n>=3. - Dennis P. Walsh, Apr 15 2013
Row sums of triangle A200092. - Dennis P. Walsh, Apr 15 2013

			Let 1,2,3,4,5,6 denote six labeled elements. Let | denote a separation between two ranks. E.g., if elements 1,2 and 3 are on rank (also called level) one and elements 3,4 and 5 are on rank two, then we have the ranking 123|456.
For n=9 we have a(9)=2101 rankings. The order within a rank does not count. Six examples are: 123|456|789; 123456789; 12345|6789; 129|345678; 1235|46789; 789|123456.

Alois P. Heinz, Table of n, a(n) for n = 0..400
Vladimir Kruchinin, D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and J. Int. Seq. 17 (2014) #14.1.1.

Cf. A000640, A102232, A032032, A232475.

Cf. column k=3 of A245732.

seq (n! *coeff (series (1- (z^2-2*exp(z)+2+2*z) /(4-2*exp(z)+2*z+z^2), z=0, n+1), z, n), n=0..30);
with(combstruct): SeqSetL := [S, {S=Sequence(U), U=Set(Z, card >= 3)}, labeled]: seq(count(SeqSetL, size=j), j=0..23); # Zerinvary Lajos, Oct 19 2006
# third Maple program:
b:= proc(n) b(n):= `if`(n=0, 1, add(b(n-j)/j!, j=3..n)) end:
a:= n-> n!*b(n):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 29 2014

CoefficientList[Series[1-(x^2-2*E^x+2+2*x)/(4-2*E^x+2*x+x^2), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Sep 29 2013 *)
b[n_] := b[n] = If[n==0, 1, Sum[b[n-j]/j!, {j, 3, n}]]; a[n_] := n!*b[n]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)

z='z+O('z^66); Vec(serlaplace( 1-(z^2-2*exp(z)+2+2*z) / (4-2*exp(z)+2*z+z^2) ) ) \\ Joerg Arndt, Apr 16 2013

E.g.f.: 1-(z^2-2*exp(z)+2+2*z)/(4-2*exp(z)+2*z+z^2).
a(n) = n! * sum(m=1..n, sum(k=0..m, k!*(-1)^(m-k) *binomial(m,k) *sum(i=0..n-m, stirling2(i+k,k) *binomial(m-k,n-m-i) *2^(-n+m+i) /(i+k)!))); a(0)=1. - Vladimir Kruchinin, Feb 01 2011
a(n) ~ 2*n!/((2+r^2)*r^(n+1)), where r = 1.56811999239... is the root of the equation 4+2*r+r^2 = 2*exp(r). - Vaclav Kotesovec, Sep 29 2013
a(0) = 1; a(n) = Sum_{k=3..n} binomial(n,k) * a(n-k). - Ilya Gutkovskiy, Feb 09 2020
E.g.f.: 1/(2 + x + x^2/2 - exp(x)). - Christian Sievers, Oct 27 2024

a(0) changed to 1 at the suggestion of Zerinvary Lajos, Oct 26 2006

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

Original entry on oeis.org

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

cp's OEIS Frontend

A102233 Number of preferential arrangements of n labeled elements when at least k=3 elements per rank are required.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions