A175707 Number of ways to put n copies of 1,2,3,4 into sets.

1, 15, 139, 862, 4079, 15791, 52450, 154279, 411180, 1009741, 2314278, 5000125, 10264997, 20152950, 38037517, 69323949, 122448455, 210271756, 351989816, 575711716, 921889652, 1447822620, 2233501928, 3389114724, 5064582169, 7461570579, 10848490675, 15579077786, 22115241763, 31054971635, 43166197978, 59427633555, 81077755892, 109673237289, 147158299390, 195946638641

Offset: 0

Author

Thotsaporn Thanatipanonda, Dec 04 2010

Keywords

• nonn

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.

Examples

			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}.
		

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).

Crossrefs

Cf. A000110, A011863, A020554, A165434.

Programs

Maple

a:= n-> (5382*n^11 +236808*n^10 +4643760*n^9 [phone]*n^8 [phone]*n^7 [phone]*n^6 [phone]*n^5 [phone]*n^4 [phone]*n^3 [phone]*n^2 [phone]*n [phone] +7016625*(-1)^n*n^3 [phone]*(-1)^n*n^2 [phone]*(-1)^n*n [phone]*(-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 *)

Formula

a(n) = (5382*n^11 +236808*n^10 +4643760*n^9 [phone]*n^8 [phone]*n^7 [phone]*n^6 [phone]*n^5 [phone]*n^4 [phone]*n^3 [phone]*n^2 [phone]*n [phone] +7016625*(-1)^n*n^3 [phone]*(-1)^n*n^2 [phone]*(-1)^n*n [phone]*(-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).