login
A264751
Triangle read by rows: T(n,k) is the number of sequences of k <= n throws of an n-sided die (with faces numbered 1, 2, ..., n) in which the sum of the throws first reaches or exceeds n on the k-th throw.
0
1, 1, 2, 1, 5, 3, 1, 9, 11, 4, 1, 14, 26, 19, 5, 1, 20, 50, 55, 29, 6, 1, 27, 85, 125, 99, 41, 7, 1, 35, 133, 245, 259, 161, 55, 8, 1, 44, 196, 434, 574, 476, 244, 71, 9, 1, 54, 276, 714, 1134, 1176, 804, 351, 89, 10, 1, 65, 375, 1110, 2058, 2562, 2190, 1275, 485, 109, 11
OFFSET
1,3
COMMENTS
By empirical observation: Sum of rows is A002064.
LINKS
Cyann Donnot, Antoine Genitrini, Yassine Herida, Unranking Combinations Lexicographically: an efficient new strategy compared with others, hal-02462764 [cs] / [cs.DS] / [math] / [math.CO], 2020.
Antoine Genitrini and Martin Pépin, Lexicographic unranking of combinations revisited, hal-03040740v2 [cs.DM] [cs.DS] [math.CO], 2020.
FORMULA
Sum_{k = 1..n} T(n,k)*k/n^k = ((n+1)/n)^(n-1) = expected value of k.
Lim_{n->infinity} (expected value of k) = e = 2.71828182845... - Jon E. Schoenfield, Nov 26 2015
T(n,k) = Sum_{i=k..n} i*binomial(i-2,k-2). - Danny Rorabaugh, Mar 04 2016
T(n,n-1) = 2*T(n-1,n-1) + T(n-1,n-2).
By empirical observation, g.f. for column k: (x-k)/(x-1)^(k+1).
EXAMPLE
Triangle begins:
1
1 2
1 5 3
1 9 11 4
1 14 26 19 5
1 20 50 55 29 6
1 27 85 125 99 41 7
1 35 133 245 259 161 55 8
1 44 196 434 574 476 244 71 9
1 54 276 714 1134 1176 804 351 89 10
1 65 375 1110 2058 2562 2190 1275 485 109 11
MATHEMATICA
T[n_, k_] := Module[
{i, total = 0, part, perm},
part = IntegerPartitions[n, {k}];
perm = Flatten[Table[Permutations[part[[i]]], {i, 1, Length[part]}], 1];
For[i = 1, i <= Length[perm], i++, total += n + 1 - perm[[i, k]] ];
Return[total]; ]
(* The rows are obtained by: *)
g[n_] := Table[T[n, k], {k, 1, n}]
(* And the triangle is obtained by: *)
Table[g[n], {n, 1, number_of_rows_wanted}]
CROSSREFS
Columns are: A000012 (k=1), A000096 (k=2), A051925 (k=3), A215862 (k=4), A264750 (k=5).
Cf. A007318 (binomial(n-1,k-1) = number of sequences of k throws of an n-sided die in which the sum of the throws equals n).
See also A002064.
Sequence in context: A339494 A104731 A240192 * A209130 A330381 A210792
KEYWORD
nonn,tabl
AUTHOR
Louis Rogliano, Nov 26 2015
STATUS
approved