

A090582


T(n, k) = Sum_{j=0..nk} (1)^j*binomial(n  k + 1, j)*(n  k + 1  j)^n. Triangle read by rows, T(n, k) for 1 <= k <= n.


20



1, 2, 1, 6, 6, 1, 24, 36, 14, 1, 120, 240, 150, 30, 1, 720, 1800, 1560, 540, 62, 1, 5040, 15120, 16800, 8400, 1806, 126, 1, 40320, 141120, 191520, 126000, 40824, 5796, 254, 1, 362880, 1451520, 2328480, 1905120, 834120, 186480, 18150, 510, 1, 3628800, 16329600, 30240000, 29635200, 16435440, 5103000, 818520, 55980, 1022, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Let Q(m, n) = Sum_(k=0..n1) (1)^k * binomial(n, k) * (nk)^m. Then Q(m,n) is the numerator of the probability P(m,n) = Q(m,n)/n^m of seeing each card at least once if m >= n cards are drawn with replacement from a deck of n cards, written in a twodimensional array read by antidiagonals with Q(m,m) as first row and Q(m,1) as first column.
The sequence is given as a matrix with the first row containing the cases #draws = size_of_deck. The second row contains #draws = 1 + size_of_deck. If "mn" indicates m cards drawn from a deck with n cards then the locations in the matrix are:
11 22 33 44 55 66 77 ...
21 32 43 54 65 76 87 ...
31 42 53 64 75 86 97 ...
41 52 63 74 85 .. .. ...
read by antidiagonals >:
11, 22, 21, 33, 32, 31, 44, 43, 42, 41, 55, 54, 53, 52, ....
The probabilities are given by Q(m,n)/n^m:
.(m,n):.....11..22..21..33..32..31..44..43..42..41...55...54..53..52..51
.....Q:......1...2...1...6...6...1..24..36..14...1..120..240.150..30...1
...n^m:......1...4...1..27...8...1.256..81..16...1.3125.1024.243..32...1
%.Success:.100..50.100..22..75.100...9..44..88.100....4...23..62..94.100
P(n,n) = n!/n^n which can be approximated by sqrt(Pi*(2n+1/3))/e^n (Gosper's approximation to n!).
Let P[n] be the set of all npermutations. Build a superset Q[n] of P[n] composed of npermutations in which some (possibly all or none) ascents have been designated. An ascent in a permutation s[1]s[2]...s[n] is a pair of consecutive elements s[i],s[i+1] such that s[i] < s[i+1]. As a triangular array read by rows T(n,k) is the number of elements in Q[n] that have exactly k distinguished ascents, n >= 1, 0 <= k <= n1. Row sums are A000670. E.g.f. is y/(1+yexp(y*x)). For example, T(3,1)=6 because there are four 3permutations with one ascent, with these we would also count 1>2 3, and 1 2>3 where exactly one ascent is designated by ">". (After Flajolet and Sedgewick.)  Geoffrey Critzer, Nov 13 2012
Sum_(k=1..n) Q(n, k)*binomial(x, k) = x^n such that Sum_{k=1..n} Q(n, i)*binomial(x+1,i+1) = Sum_{k=1..x} k^n.  David A. Corneth, Feb 17 2014
See A074909 and above g.f.s below for associations among this array and the Bernoulli polynomials and their umbral compositional inverses.  Tom Copeland, Nov 14 2014
For connections to toric varieties and Eulerian polynomials (in addition to those noted below), see the Dolgachev and Lunts and the Stembridge links in A019538.  Tom Copeland, Dec 31 2015
See A008279 for a relation between the e.g.f.s enumerating the faces of permutahedra (this entry) and stellahedra.  Tom Copeland, Nov 14 2016
From the Hasan and Franco and Hasan papers: The mpermutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5cell. The first three are wellknown from the study of elliptic models, brane tilings and brane brick models. The m+1 torus can be tiled by a single (m+2)permutohedron. Relations to toric CalabiYau Kahler manifolds are also discussed.  Tom Copeland, May 14 2020


LINKS



FORMULA

T(n, k) = (n  k + 1)!*Stirling2(n, n  k + 1), generated by Stirling numbers of the second kind multiplied by a factorial.  Victor Adamchik, Oct 05 2005
Triangle T(n,k), 1 <= k <= n, read by rows given by [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] DELTA [[0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, ...] where DELTA is the operator defined in A084938.  Philippe Deléham, Nov 10 2006
G(x,t) = 1/ (1 + (1exp(x*t))/t) = 1 + 1*x + (2 + t)*x^2/2! + (6 + 6*t + t^2)*x^3/3! + ... gives row polynomials of A090582, the fpolynomials for the permutohedra (see A019538).
G(x,t1) = 1 + 1*x + (1 + t)*x^2/2! + (1 + 4*t + t^2)*x^3/3! + ... gives row polynomials for A008292, the hpolynomials of permutohedra.
G[(t+1)x,1/(t+1)] = 1 + (1 + t)*x + (1 + 3*t + 2*t^2)*x^2/2! + ... gives row polynomials of A028246. (End)
With e.g.f. A(x,t) = G(x,t)  1, the compositional inverse in x is
B(x,t) = log((t+1)t/(1+x))/t. Let h(x,t) = 1/(dB/dx) = (1+x)*(1+(1+t)x), then the row polynomial P(n,t) is given by (1/n!)*(h(x,t)*d/dx)^n x, evaluated at x=0, A=exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t). (End)
k <= 0 or k > n yields Q(n, k) = 0; Q(1,1) = 1; Q(n, k) = k * (Q(n1, k) + Q(n1, k1)).  David A. Corneth, Feb 17 2014
With all offsets 0 for this entry, let A_n(x;y) = (y + E.(x))^n, an Appell sequence in y where E.(x)^k = E_k(x) are the Eulerian polynomials of A123125 with offsets 1 so that the array becomes A008292; i.e., we ignore the first row and first column of A123125. Then the row polynomials of this entry, A090582, are given by A_n(1 + x;0). Other specializations of A_n(x;y) give A028246, A046802, A119879, A130850, and A248727.  Tom Copeland, Jan 24 2020


EXAMPLE

For m = 4, n = 2, we draw 4 times from a deck of two cards. Call the cards "a" and "b"  of the 16 possible combinations of draws (each of which is equally likely to occur), only two do not contain both a and b: a, a, a, a and b, b, b, b. So the probability of seeing both a and b is 14/16. Therefore Q(m, n) = 14.
Table starts:
[1] 1;
[2] 2, 1;
[3] 6, 6, 1;
[4] 24, 36, 14, 1;
[5] 120, 240, 150, 30, 1;
[6] 720, 1800, 1560, 540, 62, 1;
[7] 5040, 15120, 16800, 8400, 1806, 126, 1;
[8] 40320, 141120, 191520, 126000, 40824, 5796, 254, 1;
[9] 362880, 1451520, 2328480, 1905120, 834120, 186480, 18150, 510, 1.


MAPLE

T := (n, k) > add((1)^j*binomial(n  k + 1, j)*(n  k + 1  j)^n, j = 0..nk):
# Or:
T := (n, k) > (n  k + 1)!*Stirling2(n, n  k + 1):
for n from 1 to 9 do seq( T(n, k), k = 1..n) od; # Peter Luschny, May 21 2021


MATHEMATICA

In[1]:= Table[Table[k! StirlingS2[n, k], {k, n, 1, 1}], {n, 1, 6}] (* Victor Adamchik, Oct 05 2005 *)
nn=6; a=y/(1+yExp[y x]); Range[0, nn]! CoefficientList[Series[a, {x, 0, nn}], {x, y}]//Grid (* Geoffrey Critzer, Nov 10 2012 *)


PROG

FORTRAN program given at Pfoertner link.
(Haskell)
a090582 n k = a090582_tabl !! (n1) !! (k1)
a090582_row n = a090582_tabl !! (n1)
a090582_tabl = map reverse a019538_tabl
(PARI) a(n)={m=ceil((1+sqrt(1+8*n))/2); k=m+1+binomial(m, 2)n; k*sum(i=1, k, (1)^(i+k)*i^(m1)*binomial(k1, i1))} \\ David A. Corneth, Feb 17 2014


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



