login
Number of partitions of n into 3 unordered relatively prime parts.
22

%I #34 Jan 09 2024 08:45:42

%S 1,1,2,2,4,4,6,6,10,8,14,12,16,16,24,18,30,24,32,30,44,32,50,42,54,48,

%T 70,48,80,64,80,72,96,72,114,90,112,96,140,96,154,120,144,132,184,128,

%U 196,150,192,168,234,162,240,192,240,210,290,192,310,240,288,256,336,240,374

%N Number of partitions of n into 3 unordered relatively prime parts.

%H Fausto A. C. Cariboni, <a href="/A023023/b023023.txt">Table of n, a(n) for n = 3..10000</a>

%H Mohamed El Bachraoui, <a href="https://www.fq.math.ca/Papers1/46_47-4/Bachraoui.pdf">Relatively Prime Partitions with Two and Three Parts</a>, Fibonacci Quart. 46/47 (2008/2009), no. 4, 341-345.

%F G.f. for the number of partitions of n into m unordered relatively prime parts is Sum(moebius(k)*x^(m*k)/Product(1-x^(i*k), i=1..m), k=1..infinity). - _Vladeta Jovovic_, Dec 21 2004

%F a(n) = (n^2/12)*Product_{prime p|n} (1 - 1/p^2) = A007434(n)/12 for n > 3 (proved by Mohamed El Bachraoui). [_Jonathan Sondow_, May 27 2009]

%F a(n) = Sum_{k=1..floor(n/3)} Sum_{i=k..floor((n-k)/2)} floor(1/gcd(i,k,n-i-k)). - _Wesley Ivan Hurt_, Jan 02 2021

%e From _Gus Wiseman_, Oct 08 2020: (Start)

%e The a(3) = 1 through a(13) = 14 triples (A = 10, B = 11):

%e 111 211 221 321 322 332 432 433 443 543 544

%e 311 411 331 431 441 532 533 552 553

%e 421 521 522 541 542 651 643

%e 511 611 531 631 551 732 652

%e 621 721 632 741 661

%e 711 811 641 831 733

%e 722 921 742

%e 731 A11 751

%e 821 832

%e 911 841

%e 922

%e 931

%e A21

%e B11

%e (End)

%t Table[Length[Select[IntegerPartitions[n,{3}],GCD@@#==1&]],{n,3,50}] (* _Gus Wiseman_, Oct 08 2020 *)

%Y Cf. A023024-A023030, A000742-A000743, A023032-A023035.

%Y A000741 is the ordered version.

%Y A000837 counts these partitions of any length.

%Y A001399(n-3) does not require relative primality.

%Y A023022 is the 2-part version.

%Y A101271 is the strict case.

%Y A284825 counts the case that is also pairwise non-coprime.

%Y A289509 intersected with A014612 gives the Heinz numbers.

%Y A307719 is the pairwise coprime instead of relatively prime version.

%Y A337599 is the pairwise non-coprime instead of relative prime version.

%Y A008284 counts partitions by sum and length.

%Y A078374 counts relatively prime strict partitions.

%Y A337601 counts 3-part partitions whose distinct parts are pairwise coprime.

%Y Cf. A000010, A000217, A007434, A055684, A078374, A200976, A220377, A302698, A327516, A337563, A337600, A337605.

%K nonn

%O 3,3

%A _David W. Wilson_