|
|
A092603
|
|
a(n) = Sum_{k=1..n} min(k!, binomial(n,k)).
|
|
1
|
|
|
1, 2, 4, 8, 15, 31, 62, 126, 283, 539, 1177, 2459, 4969, 10781, 22297, 45116, 95759, 201615, 400755, 830859, 1741455, 3505627, 7099561, 14607199, 30112789, 60176505, 121626832, 247652036, 504389269, 1010060135, 2030792857, 4102303316, 8289676399, 16659582365
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The number of patterns of length k in a permutation of length n is bounded above by k! and binomial(n,k). The total number of patterns in a permutation of length n is therefore bounded above by the sum of the smaller of these two upper bounds.
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
Table[Sum[Min[k!, Binomial[n, k]], {k, 1, n}], {n, 1, 40}]
|
|
PROG
|
(PARI) a(n) = sum(k=1, n, min(k!, binomial(n, k))); \\ Michel Marcus, Nov 14 2019
(Magma) [&+[Min(Factorial(k), Binomial(n, k)):k in [1..n]]:n in [1..34]]; // Marius A. Burtea, Nov 14 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|