OFFSET
1,2
COMMENTS
T(m, n) is the total number of ordered sets of size 1 to n that can be created from m distinct items. For example, for 4 items taken 1 to 3 at a time, there are P(4, 1) + P(4, 2) + P(4, 3) = 4 + 12 + 24 = 40 total sets: 1, 12, 123, 124, 13, 132, 134, 14, 142, 143, 2, 21, 213, 214, 23, 231, 234, 24, 241, 243, 3, 31, 312, 314, 32, 321, 324, 34, 341, 342, 4, 41, 412, 413, 42, 421, 423, 43, 431, 432.
T(m, n) is the total number of tests in a software program that generates all P(m, n) possible solutions to a problem, allowing early-termination testing on each partial permutation, and not doing any such early termination. For example, from a deck of 52 cards, evaluate all possible 5-card deals as each card is dealt. T(52, 5) = 318507904 total evaluations.
T(m, n) counts the numbers with <= n distinct nonzero digits in base m+1. - M. F. Hasler, Oct 10 2019
LINKS
Rick Nungester, Table of n, a(n) for n = 1..20100
FORMULA
T(m, n) = Sum_{k=1..n} m!/(m-k)! = m*(1 + (m-1)*(1 + (m-2)*(1 + ... + m-n+1)...)), cf. PARI code. - M. F. Hasler, Oct 10 2019
T(n, k) = exp(1)*(Gamma(n+1, 1) - Gamma(n-k, 1)*(n-k)*n!/(n-k)!) - 1. - Peter Luschny, Oct 10 2019
Sum-free and Gamma-free formula: T(m, n) = b(m) - m!*b(m-n)/(m-n)! where b(0)=0, b(j)=floor(j!*e-1) for j>0. - Manfred Boergens, Jun 22 2022
EXAMPLE
Triangle begins:
1;
2, 4;
3, 9, 15;
4, 16, 40, 64;
5, 25, 85, 205, 325;
6, 36, 156, 516, 1236, 1956;
7, 49, 259, 1099, 3619, 8659, 13699;
8, 64, 400, 2080, 8800, 28960, 69280, 109600;
9, 81, 585, 3609, 18729, 79209, 260649, 623529, 986409;
...
MAPLE
SumPermuteTriangle := proc(M)
local m;
for m from 1 to M do print(seq(add(m!/(m-k)!, k=1..n), n=1..m)) od;
end:
SumPermuteTriangle(10);
# second Maple program:
T:= proc(n, k) option remember;
`if`(k<1, 0, T(n-1, k-1)*n+n)
end:
seq(seq(T(n, k), k=1..n), n=1..10); # Alois P. Heinz, Jun 26 2022
MATHEMATICA
Table[Sum[m!/(m - i)!, {i, n}], {m, 9}, {n, m}] // Flatten (* Michael De Vlieger, Apr 22 2017 *)
(* Sum-free code *)
b[j_] = If[j==0, 0, Floor[j! E - 1]]; T[m_, n_] = b[m] - m! b[m-n]/(m-n)!; Table[T[m, n], {m, 24}, {n, m}]//Flatten
(* Manfred Boergens, Jun 22 2022 *)
PROG
(PARI) A285268(m, n, s=m-n+1)={for(k=m-n+2, m, s=(s+1)*k); s} \\ Much faster than sum(k=1, n, m!\(m-k)!), e.g., factor 6 for m=1..99, factor 57 for m=1..199.
(PARI) T(n, k) = {exp(1)*(incgam(n+1, 1) - incgam(n-k, 1)*(n-k)*n!/(n-k)!) - 1; }
apply(Trow(n) = vector(n, k, round(T(n, k))), [1..10]) \\ Adjust the realprecision if needed. Peter Luschny, Oct 10 2019
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Rick Nungester, Apr 15 2017
STATUS
approved