A264751 - OEIS

%I #75 Mar 26 2021 19:26:40

%S 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,

%T 7,1,35,133,245,259,161,55,8,1,44,196,434,574,476,244,71,9,1,54,276,

%U 714,1134,1176,804,351,89,10,1,65,375,1110,2058,2562,2190,1275,485,109,11

%N 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.

%C By empirical observation: Sum of rows is A002064.

%H Cyann Donnot, Antoine Genitrini, Yassine Herida, <a href="https://hal.sorbonne-universite.fr/hal-02462764">Unranking Combinations Lexicographically: an efficient new strategy compared with others</a>, hal-02462764 [cs] / [cs.DS] / [math] / [math.CO], 2020.

%H Antoine Genitrini and Martin Pépin, <a href="https://hal.sorbonne-universite.fr/hal-03040740v2">Lexicographic unranking of combinations revisited</a>, hal-03040740v2 [cs.DM] [cs.DS] [math.CO], 2020.

%F Sum_{k = 1..n} T(n,k)*k/n^k = ((n+1)/n)^(n-1) = expected value of k.

%F Lim_{n->infinity} (expected value of k) = e = 2.71828182845... - _Jon E. Schoenfield_, Nov 26 2015

%F T(n,k) = Sum_{i=k..n} i*binomial(i-2,k-2). - _Danny Rorabaugh_, Mar 04 2016

%F T(n,n-1) = 2*T(n-1,n-1) + T(n-1,n-2).

%F By empirical observation, g.f. for column k: (x-k)/(x-1)^(k+1).

%e Triangle begins:

%e   1

%e   1    2

%e   1    5    3

%e   1    9   11    4

%e   1   14   26   19    5

%e   1   20   50   55   29    6

%e   1   27   85  125   99   41    7

%e   1   35  133  245  259  161   55    8

%e   1   44  196  434  574  476  244   71    9

%e   1   54  276  714 1134 1176  804  351   89   10

%e   1   65  375 1110 2058 2562 2190 1275  485  109   11

%t T[n_, k_] := Module[

%t {i, total = 0, part, perm},

%t part = IntegerPartitions[n, {k}];

%t perm = Flatten[Table[Permutations[part[[i]]], {i, 1, Length[part]}],      1];

%t For[i = 1, i <= Length[perm], i++,    total += n + 1 - perm[[i, k]]    ];

%t Return[total];   ]

%t (* The rows are obtained by: *)

%t g[n_] := Table[T[n,k], {k,1,n}]

%t (* And the triangle is obtained by: *)

%t Table[g[n],{n,1,number_of_rows_wanted}]

%Y Columns are: A000012 (k=1), A000096 (k=2), A051925 (k=3), A215862 (k=4), A264750 (k=5).

%Y 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).

%Y See also A002064.

%K nonn,tabl

%O 1,3

%A _Louis Rogliano_, Nov 26 2015