|
| |
|
|
A090582
|
|
T(n, k) = Sum_{j=0..n-k} (-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..n-1) (-1)^k * binomial(n, k) * (n-k)^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 two-dimensional 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 n-permutations. Build a superset Q[n] of P[n] composed of n-permutations 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 <= n-1. Row sums are A000670. E.g.f. is y/(1+y-exp(y*x)). For example, T(3,1)=6 because there are four 3-permutations 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 m-permutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5-cell. The first three are well-known 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 Calabi-Yau 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 + (1-exp(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 f-polynomials for the permutohedra (see A019538).
G(x,t-1) = 1 + 1*x + (1 + t)*x^2/2! + (1 + 4*t + t^2)*x^3/3! + ... gives row polynomials for A008292, the h-polynomials 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(n-1, k) + Q(n-1, k-1)). - 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..n-k):
# 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+y-Exp[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 !! (n-1) !! (k-1)
a090582_row n = a090582_tabl !! (n-1)
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^(m-1)*binomial(k-1, i-1))} \\ David A. Corneth, Feb 17 2014
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
