A281912 Number of sequences of balls colored with at most n colors such that exactly one ball is of a color seen earlier in the sequence.

1, 8, 57, 424, 3425, 30336, 294553, 3123632, 36003969, 448816600, 6022033721, 86587079448, 1328753602657, 21683227579664, 375013198304025, 6853321766162656, 131976208783240193, 2671430511854158632, 56709161712552286009, 1259836187316759240200

Offset

1,2

Comments

Note that any such sequence has at least 2 balls, and at most n+1

Number of sequences of balls colored with at most n colors such that exactly two balls are the same color as some other ball in the sequence (necessarily each other). - Jeremy Dover, Sep 26 2017

Links

Jeremy Dover, Table of n, a(n) for n = 1..99

Formula

a(n) = n! * Sum_{k=2..n+1} binomial(k,2)/(n+1-k)!.

a(n) = n if n < 2, a(n) = n*((n+2)/(n-1)*a(n-1) - a(n-2)) for n >= 2. - Alois P. Heinz, Feb 02 2017

a(n)/n! ~ e*n^2/2. - Vaclav Kotesovec, Feb 03 2017

Example

n=1 => AA -> a(1) = 1.
n=2 => AA,BB,AAB,ABA,BAA,BBA,BAB,ABB -> a(2) = 8.

Maple

a:= proc(n) option remember;
      `if`(n<2, 1, a(n-1)*(n+2)/(n-1)-a(n-2))*n
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Feb 02 2017

Mathematica

Table[n!*Sum[Binomial[k, 2]/(n + 1 - k)!, {k, 2, n + 1}], {n, 20}] (* Michael De Vlieger, Feb 02 2017 *)

Crossrefs

Cf. A093964.

Row sums of triangle A281881. - Jeremy Dover, Sep 26 2017

Sequence in context: A015453 A181246 A281355 * A343352 A307642 A338676

Adjacent sequences: A281909 A281910 A281911 * A281913 A281914 A281915

Keyword

nonn

Author

Jeremy Dover, Feb 01 2017

Status

approved