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.
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
Examples
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
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.
Crossrefs
Programs
-
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}]
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).
Comments