Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #16 Sep 08 2022 08:45:13
%S 1,2,4,8,15,31,62,126,283,539,1177,2459,4969,10781,22297,45116,95759,
%T 201615,400755,830859,1741455,3505627,7099561,14607199,30112789,
%U 60176505,121626832,247652036,504389269,1010060135,2030792857,4102303316,8289676399,16659582365
%N a(n) = Sum_{k=1..n} min(k!, binomial(n,k)).
%C Upper bound on A088532(n).
%C 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.
%F a(n) ~ 2^n. - _Vaclav Kotesovec_, Aug 03 2015
%t Table[Sum[Min[k!, Binomial[n, k]], {k, 1, n}], {n, 1, 40}]
%o (PARI) a(n) = sum(k=1, n, min(k!, binomial(n, k))); \\ _Michel Marcus_, Nov 14 2019
%o (Magma) [&+[Min(Factorial(k),Binomial(n,k)):k in [1..n]]:n in [1..34]]; // _Marius A. Burtea_, Nov 14 2019
%Y Cf. A088532.
%K easy,nonn
%O 1,2
%A _Rob Pratt_, Apr 10 2004