A093695 Number of one-element transitions among partitions of the integer n for unlabeled parts.
0, 0, 2, 4, 10, 18, 34, 56, 94, 146, 228, 340, 506, 730, 1050, 1476, 2066, 2844, 3896, 5268, 7090, 9442, 12518, 16454, 21534, 27980, 36210, 46572, 59674, 76056, 96594, 122106, 153852, 193048, 241492, 300974, 374038, 463286, 572304, 704826, 865874, 1060766
Offset: 0
Keywords
Examples
In the unlabeled case we have 10 one-element transitions among all partitions of n=4: [1,1,1,1] -> [1,1,2]; [1,1,2] -> [2,2]; [1,1,2] -> [1,3]; [2,2] -> [1,3]; [1,3] -> [4] and [1,1,2] -> [1,1,1,1]; [2,2] -> [1,1,2]; [1,3] -> [1,1,2]; [1,3] -> [2,2]; [4] -> [1,3].
n=5:
partition number p=1 is [1,1,1,1,1], parts d(1,1)=1, d(2,1)=1 contribute 1;
partition number p=2 is [1,1,1,2], parts d(1,1)=1, d(2,2)=1 contribute 1, parts d(1,2)=2, d(4,2)=2 contribute 1;
partition number p=3 is [1,2,2], parts d(1,3)=1, d(2,3)=2 contribute 1, parts d(2,3)=2, d(3,3)=2 contribute 1;
partition number p=4 is [1,1,3], parts d(1,4)=1, d(2,4)=1 contribute 1, parts d(1,4)=1, d(3,4)=3 contribute 1;
partition number p=5 is [2,3], parts d(1,5)=2, d(2,5)=3 contribute 1;
partition number p=6 is [1,4], parts d(1,6)=1, d(2,6)=4 contribute 1;
partition number p=7 is [5], parts d(1,7)=5 contributes 0;
==> a(5)=2*9=18 (factor 2 if we accept up and down transitions).
a(5) = 18 because the 11 partitions of n=5+1=6 have the following sets of parts:
{1} contributes 0, {1, 2} contributes 2, {1, 2} contributes 2,
{2} contributes 0, {1, 3} contributes 2, {1, 2, 3} contributes 6,
{3} contributes 0, {1, 4} contributes 2, {2, 4} contributes 2,
{1, 5} contributes 2, {6} contributes 0,
which gives 0 + 2 + 2 + 0 + 2 + 6 + 0 + 2 + 2 + 2 + 0 = 18.
G.f. = 2*x^2 + 4*x^3 + 10*x^4 + 18*x^5 + 34*x^6 + 56*x^7 + 94*x^8 + ...
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..5000
Programs
-
Maple
A093695 := proc(n::integer) local a,ndxp,ListOfPartitions,APartition,PartOfAPartition,SetOfParts, iverbose; with(combinat): iverbose:=1; ListOfPartitions:=partition(n+1); a:=0; for ndxp from 1 to nops(ListOfPartitions) do APartition := ListOfPartitions[ndxp]; SetOfParts := convert(APartition,set); a := a + nops(SetOfParts)^2 - nops(SetOfParts); if iverbose = 1 then print ("ndxp, SetOfParts, nops(SetOfParts)^2 - nops(SetOfParts): ", ndxp,SetOfParts,nops(SetOfParts)^2 - nops(SetOfParts)); fi; # End of do-loop *** ndxp ***. end do; print("n, a(n):",n,a); end proc; # second Maple program b:= proc(n, i) option remember; local j, f, g; if n=0 then [0] elif i=1 then [1] else f:= b(n, i-1); for j to floor(n/i) do f:= zip((x, y)-> x+y, f, `if`(n=i*j, [1], [0, b(n-i*j, i-1)[]]), 0) od; f fi end: a:= n-> (l-> add(i*(i-1)*l[i], i=1..nops(l)))(b(n+1, n+1)): seq(a(n), n=0..50); # Alois P. Heinz, Apr 05 2012
-
Mathematica
a[n_] := Block[{p = IntegerPartitions[n + 1], l = PartitionsP[n + 1]}, Sum[ Length[ Union[ p[[k]]]]^2 - Length[ Union[ p[[k]] ]], {k, l}]]; Table[ a[n], {n, 0, 40}] (* Robert G. Wilson v, Jul 13 2004, updated by Jean-François Alcover, Jan 29 2014 *)
Formula
a(n) = Sum_p=1^P(n) Sum_i=1^D(p) Sum_j=1^D(p) 1 [subject to: i <> j and d(i,p) <= d(j,p) and d(i,p) <> d(i-1,p) (if i > 1) and d(j,i) <> d(j-1,i) (if j > 1 and if d(j-1,p) has given a contribution to the sum) ]; P(n) = number of partitions of n, D(p) = number of parts in partition p, d(i,p) and d(j,p) = parts number i and j in partition p of integer n.
See the corresponding formula for a(n) for the labeled case A094533.
a(n) = Sum_i=1^P(n+1) S(i, n+1)^2 - S(i, n+1), where P(n+1) is the number of integer partitions of n+1 and S(i, n+1) is the number of parts in the set of parts of the i-th partition of n+1. (E.g. the partition [1111233] has the set of parts {1, 2, 3} and would contribute 3^2 - 3 = 6 to the sum.)
G.f.: 2*x^2 / (x^3-x^2-x+1) * Product_{m>=1} (1/(1-x^m)) (conjectured). - Thomas Baruchel, May 12 2018
Extensions
More terms from Robert G. Wilson v, Jul 13 2004
Comments