A285268 Triangle read by rows: T(m,n) = Sum_{i=1..n} P(m,i) where P(m,n) = m!/(m-n)! is the number of permutations of m items taken n at a time, for 1 <= n <= m.

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, 10, 100, 820, 5860, 36100, 187300, 792100, 2606500, 6235300, 9864100

Offset: 1

Author

Rick Nungester, Apr 15 2017

Keywords

• nonn
• tabl

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

Examples

			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;
  ...
		

Links

• Rick Nungester, Table of n, a(n) for n = 1..20100

Crossrefs

Mirror of triangle A121662.

Row sums give A030297.

Diagonals (1..4): A007526 (less the initial 0), A038156 (less the initial 0, 0), A224869 (less the initial -1, 0), A079750 (less the initial 0).

Columns (1..3): A000027, A000290 (less the initial 0, 1), A053698 (less the initial 1, 4).

Programs

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 *)

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.
apply( A285268_row(m)=vector(m,n,A285268(m,n)), [1..9]) \\ M. F. Hasler, Oct 10 2019

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

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