OFFSET
5,1
LINKS
Colin Barker, Table of n, a(n) for n = 5..999
Ronald Becerra et al., How many numbers of 10 digits have at least 5 different digits?, Mathematics Stack Exchange, Feb 02 2016
Index entries for linear recurrences with constant coefficients, signature (20,-135,400,-524,240).
FORMULA
a(n) = Sum_{q=5..10} binomial(10,q)*Stirling2(n, q)*q! - Sum_{q=5..10} binomial(9,q-1)*Stirling2(n-1, q-1)*(q-1)! - Sum_{q=5..10} binomial(9,q-1)*Stirling2(n-1, q)*q!.
From Colin Barker, Feb 03 2016: (Start)
a(n) = 9*(560 - 945*2^n - 105*2^(1+2*n) + 80*3^(2+n) + 10^n)/10.
a(n) = 20*a(n-1) - 135*a(n-2) + 400*a(n-3) - 524*a(n-4) + 240*a(n-5) for n > 9.
G.f.: 27216*x^5 / ((1-x)*(1-2*x)*(1-3*x)*(1-4*x)*(1-10*x)).
(End)
These three formulas are correct because the closed form is equivalent to that given in the Becerra et al. link, namely, 9*10^(n-1) - 189*4^n + 648*3^n - 1701*2^(n-1) + 504. - Colin Barker, Feb 11 2016
MAPLE
Q :=
proc(n)
add(binomial(10, q)*stirling2(n, q)*q!, q=5..10)
- add(binomial(9, q-1)*stirling2(n-1, q-1)*(q-1)!, q=5..10)
- add(binomial(9, q-1)*stirling2(n-1, q)*q!, q=5..10);
end;
MATHEMATICA
Table[Sum[Binomial[10, i] StirlingS2[n, i] i!, {i, 5, 10}] - Sum[Binomial[9, i - 1] StirlingS2[n - 1, i - 1] (i - 1)!, {i, 5, 10}] - Sum[Binomial[9, i - 1] StirlingS2[n - 1, i] i!, {i, 5, 10}], {n, 5, 20}] (* Michael De Vlieger, Feb 03 2016 *)
CoefficientList[Series[27216 x^5/((1 - x) (1 - 2 x) (1 - 3 x) (1 - 4 x) (1 - 10 x)), {x, 0, 20}], x] (* Michael De Vlieger, Feb 03 2016 *)
LinearRecurrence[{20, -135, 400, -524, 240}, {27216, 544320, 7212240, 81648000, 862774416}, 20] (* Harvey P. Dale, Aug 02 2018 *)
PROG
(PARI) a(n) = sum(q=5, 10, binomial(10, q)*stirling(n, q, 2)*q!) - sum(q=5, 10, binomial(9, q-1)*stirling(n-1, q-1, 2)*(q-1)!) - sum(q=5, 10, binomial(9, q-1)*stirling(n-1, q, 2)*q!) \\ Colin Barker, Feb 03 2016
(PARI) Vec(27216*x^5/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)*(1-10*x)) + O(x^100)) \\ Colin Barker, Feb 11 2016
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Marko Riedel, Feb 02 2016
STATUS
approved