OFFSET
0,2
COMMENTS
Related to generalized Bell Numbers.
The n copies of each digit must be in different sets, and the sets must be nonempty.
Other definition: Number of ways to distribute n copies of 1,2,3,4 into an arbitrary number of (nonempty) sets. Due to the nature of sets, the same digit may not be several times in the same set.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Doron Zeilberger, In How Many Ways Can You Reassemble Several Russian Dolls? (2009).
Doron Zeilberger, In How many ways can you reassemble several russian dolls?, arXiv:0909.3453 [math.CO], 2009.
Doron Zeilberger, BABUSHKAS; Local copy
Index entries for linear recurrences with constant coefficients, signature (7, -17, 8, 36, -60, 4, 56, -22, -22, -22, 56, 4, -60, 36, 8, -17, 7, -1).
FORMULA
a(n) = (5382*n^11 +236808*n^10 +4643760*n^9 +53507520*n^8 +402098796*n^7 +2067612624*n^6 +7421736960*n^5 +18616942080*n^4 +32101468047*n^3 +36555545268*n^2 +25131098880*n +8024016000 +7016625*(-1)^n*n^3 +84199500*(-1)^n*n^2 +359251200*(-1)^n*n +538876800*(-1)^n) / (2^11*3^7*5^2*7*11) +5/3^6*(-1)^n * (sin(n*Pi/3)/sqrt(3) +cos(n*Pi/3)).
Recurrence: a(n) -7*a(n-1) +17*a(n-2) -8*a(n-3) -36*a(n-4) +60*a(n-5) -4*a(n-6) -56*a(n-7) +22*a(n-8) +22*a(n-9) +22*a(n-10) -56*a(n-11) -4*a(n-12) +60*a(n-13) -36*a(n-14) -8*a(n-15) +17*a(n-16) -7*a(n-17) +a(n-18) = 0.
G.f.: (x^10 +8*x^9 +51*x^8 +136*x^7 +252*x^6 +300*x^5 +252*x^4 +136*x^3 +51*x^2 +8*x+1) / ((x^2+x+1)*(x+1)^4*(x-1)^12).
EXAMPLE
For n=1, the solution is the fourth term of Bell numbers A000110.
For n=2, one way to partition 2 copies of 1, 2 copies of 2, 2 copies of 3 and 2 copies of 4 is {1}{2}{34}{12}{34}. On the other hand {112}{34}{23}{4} is not allowed since the same numbers are in the same set {112}.
MAPLE
a:= n-> (5382*n^11 +236808*n^10 +4643760*n^9 +53507520*n^8 +402098796*n^7 +2067612624*n^6 +7421736960*n^5 +18616942080*n^4 +32101468047*n^3 +36555545268*n^2 +25131098880*n +8024016000 +7016625*(-1)^n*n^3 +84199500*(-1)^n*n^2 +359251200*(-1)^n*n +538876800*(-1)^n) /(2^11*3^7*5^2*7*11) +5/3^6*(-1)^n * (sin(n*Pi/3)/sqrt(3)+ cos(n*Pi/3));
seq(a(n), n=0..40);
seq(SeqBrnDJ(n, 4)[5], n=1..6); # using the Maple package BABUSHKAS (see links)
MATHEMATICA
LinearRecurrence[{7, -17, 8, 36, -60, 4, 56, -22, -22, -22, 56, 4, -60, 36, 8, -17, 7, -1}, {1, 15, 139, 862, 4079, 15791, 52450, 154279, 411180, 1009741, 2314278, 5000125, 10264997, 20152950, 38037517, 69323949, 122448455, 210271756}, 36] (* Jean-François Alcover, Nov 13 2018 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Thotsaporn Thanatipanonda, Dec 04 2010
STATUS
approved