A268358 Number of n-digit numbers in base ten having at least five different digits with no leading zeros allowed.

27216, 544320, 7212240, 81648000, 862774416, 8839212480, 89320326480, 897169996800, 8988342579216, 89952351128640, 899806333018320, 8999216089718400, 89996836576073616, 899987262844420800, 8999948800775111760, 89999794450846828800, 899999175545734649616

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

Sequence in context: A228562 A224466 A127411 * A157814 A216943 A250852

Adjacent sequences: A268355 A268356 A268357 * A268359 A268360 A268361

Keyword

nonn,base,easy

Author

Marko Riedel, Feb 02 2016

Status

approved