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,3

Comments

By empirical observation: Sum of rows is A002064.

Links

Table of n, a(n) for n=1..66.

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

Adjacent sequences: A264748 A264749 A264750 * A264752 A264753 A264754

Keyword

nonn,tabl

Author

Louis Rogliano, Nov 26 2015

Status

approved