A260669 -id:A260669 - cp's OEIS frontend

A054440 Number of ordered pairs of partitions of n with no common parts.

1, 0, 2, 4, 12, 16, 48, 60, 148, 220, 438, 618, 1302, 1740, 3216, 4788, 8170, 11512, 19862, 27570, 45448, 64600, 100808, 141724, 223080, 307512, 465736, 652518, 968180, 1334030, 1972164, 2691132, 3902432, 5347176, 7611484, 10358426, 14697028, 19790508, 27691500

Offset: 0

Herbert S. Wilf, May 13 2000

			a(3)=4 because of the 4 pairs of partitions of 3: (3,21),(3,111),(21,3),(111,3).

Reinhard Zumkeller, Table of n, a(n) for n = 0..5000
Sylvie Corteel, Carla D. Savage, Herbert S. Wilf, Doron Zeilberger, A pentagonal number sieve, J. Combin. Theory Ser. A 82 (1998), no. 2, 186-192.
Eric Weisstein's World of Mathematics, Pentagonal Number Theorem
Wikipedia, Pentagonal number theorem

Cf. A000041, A001255, A001318, A087960, A260672, A260664, A260669, A304873, A304877.

Main diagonal of A284592.

a054440 = sum . zipWith (*) a087960_list . map a001255 . a260672_row
-- Reinhard Zumkeller, Nov 15 2015

with(combinat): p1 := sum(numbpart(n)^2*x^n, n=0..500): it := p1*product((1-x^i), i=1..500): s := series(it, x, 500): for i from 0 to 100 do printf(`%d,`,coeff(s,x,i)) od:

nmax = 50; CoefficientList[Series[Sum[PartitionsP[k]^2*x^k, {k, 0, nmax}]/Sum[PartitionsP[k]*x^k, {k, 0, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jul 04 2016 *)

G.f.: Sum[p(n)^2*x^n]/Sum[p(n)*x^n], with p(n)=number of partitions of n.
a(n) ~ sqrt(3) * exp(Pi*sqrt(2*n)) / (64 * 2^(1/4) * n^(7/4)). - Vaclav Kotesovec, May 20 2018
a(n) = [(x*y)^n] Product_{k>=1} (1 + x^k / (1 - x^k) + y^k / (1 - y^k)). - Ilya Gutkovskiy, Apr 24 2025

Corrected and extended by James Sellers, May 23 2000

A108796 Number of unordered pairs of partitions of n (into distinct parts) with empty intersection.

Original entry on oeis.org

1, 0, 0, 1, 1, 3, 4, 7, 9, 16, 21, 33, 46, 68, 95, 140, 187, 266, 372, 507, 683, 948, 1256, 1692, 2263, 3003, 3955, 5248, 6824, 8921, 11669, 15058, 19413, 25128, 32149, 41129, 52578, 66740, 84696, 107389, 135310, 170277, 214386, 268151, 335261, 418896, 521204

Offset: 0

Wouter Meeussen, Jul 09 2005

nonn

Counted as orderless pairs since intersection is commutative.

			Of the partitions of 12 into different parts, the partition (5+4+2+1) has an empty intersection with only (12) and (9+3).
From _Gus Wiseman_, Oct 07 2023: (Start)
The a(6) = 4 pairs are:
  ((6),(5,1))
  ((6),(4,2))
  ((6),(3,2,1))
  ((5,1),(4,2))
(End)

Vaclav Kotesovec Table of n, a(n) for n = 0..1050 (terms 0..700 from Alois P. Heinz)

Column k=2 of A258280.
Cf. A079122, A086737.
Main diagonal of A284593 times (1/2).
This is the strict case of A260669.
The ordered version is A365662 = strict case of A054440.
This is the disjoint case of A366132, with twins A366317.
A000041 counts integer partitions, strict A000009.
A002219 counts biquanimous partitions, strict A237258, ordered A064914.
Cf. A000124, A000712, A001255, A006827, A032302, A122768, A355389.

using DiscreteMath`Combinatorica`and ListPartitionsQ[n_Integer]:= Flatten[ Reverse /@ Table[(Range[m-1, 0, -1]+#1&)/@ TransposePartition/@ Complement[Partitions[ n-m* (m-1)/2, m], Partitions[n-m*(m-1)/2, m-1]], {m, -1+Floor[1/2*(1+Sqrt[1+8*n])]}], 1]; Table[Plus@@Flatten[Outer[If[Intersection[Flatten[ #1], Flatten[ #2]]==={}, 1, 0]&, ListPartitionsQ[k], ListPartitionsQ[k], 1]], {k, 48}]/2
nmax = 50; p = 1; Do[p = Expand[p*(1 + x^j + y^j)]; p = Select[p, (Exponent[#, x] <= nmax) && (Exponent[#, y] <= nmax) &], {j, 1, nmax}]; p = Select[p, Exponent[#, x] == Exponent[#, y] &]; Table[Coefficient[p, x^n*y^n]/2, {n, 1, nmax}] (* Vaclav Kotesovec, Apr 07 2017 *)
Table[Length[Select[Subsets[Select[IntegerPartitions[n], UnsameQ@@#&],{2}],Intersection@@#=={}&]],{n,15}] (* Gus Wiseman, Oct 07 2023 *)

a(n) = {my(A=1 + O(x*x^n) + O(y*y^n)); polcoef(polcoef(prod(k=1, n, A + x^k + y^k), n), n)/2} \\ Andrew Howroyd, Oct 10 2023

a(n) = ceiling(1/2 * [(x*y)^n] Product_{j>0} (1+x^j+y^j)). - Alois P. Heinz, Mar 31 2017

a(n) = ceiling(A365662(n)/2). - Gus Wiseman, Oct 07 2023

Name edited by Gus Wiseman, Oct 10 2023

a(0)=1 prepended by Alois P. Heinz, Feb 09 2024

A365662 Number of ordered pairs of disjoint strict integer partitions of n.

Original entry on oeis.org

1, 0, 0, 2, 2, 6, 8, 14, 18, 32, 42, 66, 92, 136, 190, 280, 374, 532, 744, 1014, 1366, 1896, 2512, 3384, 4526, 6006, 7910, 10496, 13648, 17842, 23338, 30116, 38826, 50256, 64298, 82258, 105156, 133480, 169392, 214778, 270620, 340554, 428772, 536302, 670522

Offset: 0

Gus Wiseman, Sep 19 2023

nonn

Also the number of ways to first choose a strict partition of 2n, then a subset of it summing to n.

			The a(0) = 1 through a(7) = 14 pairs:
  ()()  .  .  (21)(3)  (31)(4)  (32)(5)   (42)(6)   (43)(7)
              (3)(21)  (4)(31)  (41)(5)   (51)(6)   (52)(7)
                                (5)(32)   (6)(42)   (61)(7)
                                (5)(41)   (6)(51)   (7)(43)
                                (32)(41)  (321)(6)  (7)(52)
                                (41)(32)  (42)(51)  (7)(61)
                                          (51)(42)  (421)(7)
                                          (6)(321)  (43)(52)
                                                    (43)(61)
                                                    (52)(43)
                                                    (52)(61)
                                                    (61)(43)
                                                    (61)(52)
                                                    (7)(421)

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

For subsets instead of partitions we have A000244, non-disjoint A000302.
If the partitions can have different sums we get A032302.
The non-strict version is A054440, non-disjoint A001255.
The unordered version is A108796, non-strict A260669.
A000041 counts integer partitions, strict A000009.
A000124 counts distinct possible sums of subsets of {1..n}.
A000712 counts distinct submultisets of partitions.
A002219 and A237258 count partitions of 2n including a partition of n.
A304792 counts subset-sums of partitions, positive A276024, strict A284640.
A364272 counts sum-full strict partitions, sum-free A364349.
Cf. A006827, A046663, A064914, A122768, A260664, A365661, A365663.

Table[Length[Select[Tuples[Select[IntegerPartitions[n], UnsameQ@@#&],2], Intersection@@#=={}&]], {n,0,15}]
Table[SeriesCoefficient[Product[(1 + x^k + y^k), {k, 1, n}], {x, 0, n}, {y, 0, n}], {n, 0, 50}] (* Vaclav Kotesovec, Apr 24 2025 *)

a(n) = 2*A108796(n) for n > 1.

a(n) = [(x*y)^n] Product_{k>=1} (1 + x^k + y^k). - Ilya Gutkovskiy, Apr 24 2025

A284592 Square array read by antidiagonals: T(n,k) is the number of pairs of partitions of n and k respectively, such that the pair of partitions have no part in common.

Original entry on oeis.org

1, 1, 1, 2, 0, 2, 3, 1, 1, 3, 5, 1, 2, 1, 5, 7, 2, 3, 3, 2, 7, 11, 2, 5, 4, 5, 2, 11, 15, 4, 6, 7, 7, 6, 4, 15, 22, 4, 10, 8, 12, 8, 10, 4, 22, 30, 7, 12, 14, 14, 14, 14, 12, 7, 30, 42, 8, 18, 16, 24, 16, 24, 16, 18, 8, 42, 56, 12, 23, 25, 28, 28, 28, 28, 25, 23, 12, 56

Offset: 0

Peter Bala, Mar 30 2017

Compare with A284593.

			Square array begins
  n\k|  0  1  2  3  4  5   6   7   8   9  10
- - - - - - - - - - - - - - - - - - - - - - -
  0  |  1  1  2  3  5  7  11  15  22  30  42: A000041
  1  |  1  0  1  1  2  2   4   4   7   8  12: A002865
  2  |  2  1  2  3  5  6  10  12  18  23  32
  3  |  3  1  3  4  7  8  14  16  25  31  44
  4  |  5  2  5  7 12 14  24  28  43  54  76
  5  |  7  2  6  8 14 16  28  31  49  60  85
  6  | 11  4 10 14 24 28  48  55  85 106 149
  7  | 15  4 12 16 28 31  55  60  95 115 163
  8  | 22  7 18 25 43 49  85  95 148 182 256
  9  | 30  8 23 31 54 60 106 115 182 220 311
  10 | 42 12 32 44 76 85 149 163 256 311 438
  ...
T(4,3) = 7: the 7 pairs of partitions of 4 and 3 with no parts in common are (4, 3), (4, 2 + 1), (4, 1 + 1 + 1), (2 + 2, 3), (2 + 2, 1 + 1 + 1), (2 + 1 + 1 , 3) and (1 + 1 + 1 + 1, 3).

Alois P. Heinz, Antidiagonals n = 0..200, flattened
H. S. Wilf, Lectures on Integer Partitions

Cf. A000041 (row 0), A002865 (row 1), A015128 (antidiagonal sums), A284593.

Main diagonal gives A054440 or 2*A260669 (for n>0).

#A284592 as a square array
ser := taylor(taylor(mul(1 + x^j/(1 - x^j) + y^j/(1 - y^j), j = 1..10), x, 11), y, 11):
convert(ser, polynom):
s := convert(%, polynom):
with(PolynomialTools):
for n from 0 to 10 do CoefficientList(coeff(s, y, n), x) end do;
# second Maple program:
b:= proc(n, k, i) option remember; `if`(n=0 and
       (k=0 or i=1), 1, `if`(i<1, 0, b(n, k, i-1)+
       add(b(sort([n-i*j, k])[], i-1), j=1..n/i)+
       add(b(sort([n, k-i*j])[], i-1), j=1..k/i)))
    end:
A:= (n, k)-> (l-> b(l[1], l[2]$2))(sort([n, k])):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Apr 02 2017

Table[Total@ Boole@ Map[! IntersectingQ @@ Map[Union, #] &, Tuples@ {IntegerPartitions@ #, IntegerPartitions@ k}] &[n - k], {n, 0, 11}, {k, 0, n}] // Flatten (* Michael De Vlieger, Apr 02 2017 *)
b[n_, k_, i_] := b[n, k, i] = If[n == 0 &&
     (k == 0 || i == 1), 1, If[i < 1, 0, b[n, k, i - 1] +
     Sum[b[Sequence @@ Sort[{n - i*j, k}], i - 1], {j, 1, n/i}] +
     Sum[b[Sequence @@ Sort[{n, k - i*j}], i - 1], {j, 1, k/i}]]];
A[n_, k_] := Function [l, b[l[[1]], l[[2]], l[[2]]]][Sort[{n, k}]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jun 07 2021, after Alois P. Heinz *)

O.g.f. Product_{j >= 1} (1 + x^j/(1 - x^j) + y^j/(1 - y^j)) = Sum_{n,k >= 0} T(n,k)*x^n*y^k (see Wilf, Example 7).

Antidiagonal sums are A015128.

A366132 Number of unordered pairs of distinct strict integer partitions of n.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 6, 10, 15, 28, 45, 66, 105, 153, 231, 351, 496, 703, 1035, 1431, 2016, 2850, 3916, 5356, 7381, 10011, 13530, 18336, 24531, 32640, 43660, 57630, 75855, 100128, 130816, 170820, 222778, 288420, 372816, 481671, 618828, 793170, 1016025, 1295245

Offset: 0

Gus Wiseman, Oct 08 2023

nonn

			The a(3) = 1 through a(8) = 15 pairs of strict partitions:
  {3,21}  {4,31}  {5,32}   {6,42}    {7,43}    {8,53}
                  {5,41}   {6,51}    {7,52}    {8,62}
                  {41,32}  {51,42}   {7,61}    {8,71}
                           {6,321}   {52,43}   {62,53}
                           {42,321}  {61,43}   {71,53}
                           {51,321}  {61,52}   {71,62}
                                     {7,421}   {8,431}
                                     {43,421}  {8,521}
                                     {52,421}  {53,431}
                                     {61,421}  {53,521}
                                               {62,431}
                                               {62,521}
                                               {71,431}
                                               {71,521}
                                               {521,431}

For subsets instead of partitions we have A006516, non-disjoint A003462.
The disjoint case is A108796, non-strict A260669.
For non-strict partitions we have A355389.
The ordered disjoint case is A365662, non-strict A054440.
The ordered version is 2*a(n).
Including equal pairs or twins gives A366317, ordered A304990.
A000041 counts integer partitions, strict A000009.
A002219 and A237258 count partitions of 2n including a partition of n.
A161680 and A000217 count 2-subsets of {1..n}.
Cf. A000124, A001255, A006827, A032302, A064914, A365661, A365663.

Table[Length[Subsets[Select[IntegerPartitions[n],UnsameQ@@#&],{2}]],{n,0,30}]

a(n) = binomial(A000009(n),2).

A366317 Number of unordered pairs of strict integer partitions of n.

Original entry on oeis.org

1, 1, 1, 3, 3, 6, 10, 15, 21, 36, 55, 78, 120, 171, 253, 378, 528, 741, 1081, 1485, 2080, 2926, 4005, 5460, 7503, 10153, 13695, 18528, 24753, 32896, 43956, 57970, 76245, 100576, 131328, 171405, 223446, 289180, 373680, 482653, 619941, 794430, 1017451, 1296855

Offset: 0

Gus Wiseman, Oct 08 2023

nonn

			The a(1) = 1 through a(7) = 15 unordered pairs of strict partitions:
  {1,1}  {2,2}  {3,3}    {4,4}    {5,5}    {6,6}      {7,7}
                {3,21}   {4,31}   {5,32}   {6,42}     {7,43}
                {21,21}  {31,31}  {5,41}   {6,51}     {7,52}
                                  {32,32}  {42,42}    {7,61}
                                  {32,41}  {42,51}    {43,43}
                                  {41,41}  {51,51}    {43,52}
                                           {6,321}    {43,61}
                                           {42,321}   {52,52}
                                           {51,321}   {52,61}
                                           {321,321}  {61,61}
                                                      {7,421}
                                                      {43,421}
                                                      {52,421}
                                                      {61,421}
                                                      {421,421}

For non-strict partitions we have A086737.
The disjoint case is A108796, non-strict A260669.
The ordered version is A304990, disjoint A032302.
The ordered disjoint case is A365662.
Excluding constant pairs gives A366132.
A000041 counts integer partitions, strict A000009.
A002219 and A237258 count partitions of 2n including a partition of n.
A364272 counts sum-full strict partitions, sum-free A364349.
Cf. A000712, A007582, A054440, A064914, A260664.

Table[Length[Select[Tuples[Select[IntegerPartitions[n], UnsameQ@@#&],2],OrderedQ]],{n,0,30}]

a(n) = A000217(A000009(n)).

Composition of A000009 and A000217.

A370005 Number T(n,k) of ordered pairs of partitions of n with exactly k common parts; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 2, 1, 1, 4, 3, 1, 1, 12, 7, 4, 1, 1, 16, 19, 8, 4, 1, 1, 48, 35, 23, 9, 4, 1, 1, 60, 83, 43, 24, 9, 4, 1, 1, 148, 143, 106, 47, 25, 9, 4, 1, 1, 220, 291, 186, 115, 48, 25, 9, 4, 1, 1, 438, 511, 397, 210, 119, 49, 25, 9, 4, 1, 1, 618, 949, 697, 444, 219, 120, 49, 25, 9, 4, 1, 1

Offset: 0

Alois P. Heinz, Feb 07 2024

			T(4,0) = 12: (1111,22), (1111,4), (211,4), (22,1111), (22,31), (22,4), (31,22), (31,4), (4,1111), (4,211), (4,22), (4,31).
T(4,1) = 7: (1111,31), (211,22), (211,31), (22,211), (31,1111), (31,211), (4,4).
T(4,2) = 4: (1111,211), (211,1111), (22,22), (31,31).
T(4,3) = 1: (211,211).
T(4,4) = 1: (1111,1111).
Triangle T(n,k) begins:
    1;
    0,   1;
    2,   1,   1;
    4,   3,   1,   1;
   12,   7,   4,   1,   1;
   16,  19,   8,   4,   1,  1;
   48,  35,  23,   9,   4,  1,  1;
   60,  83,  43,  24,   9,  4,  1, 1;
  148, 143, 106,  47,  25,  9,  4, 1, 1;
  220, 291, 186, 115,  48, 25,  9, 4, 1, 1;
  438, 511, 397, 210, 119, 49, 25, 9, 4, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Column k=0 gives A054440.
Row sums and T(2n,n) give A001255.
Cf. A000041, A000290, A260669, A370207.

b:= proc(n, m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
      add(add(expand(b(sort([n-i*j, m-i*h])[], i-1)*
       x^min(j, h)), h=0..m/i), j=0..n/i)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$3)):
seq(T(n), n=0..12);

A370207 Number T(n,k) of unordered pairs of partitions of n with exactly k common parts; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 6, 4, 3, 1, 1, 8, 10, 5, 3, 1, 1, 24, 18, 13, 6, 3, 1, 1, 30, 42, 23, 14, 6, 3, 1, 1, 74, 72, 55, 26, 15, 6, 3, 1, 1, 110, 146, 95, 61, 27, 15, 6, 3, 1, 1, 219, 256, 201, 109, 64, 28, 15, 6, 3, 1, 1, 309, 475, 351, 227, 115, 65, 28, 15, 6, 3, 1, 1

Offset: 0

Alois P. Heinz, Feb 11 2024

			T(4,0) = 6: (1111,22), (1111,4), (211,4), (22,31), (22,4), (31,4).
T(4,1) = 4: (1111,31), (211,22), (211,31), (4,4).
T(4,2) = 3: (1111,211), (22,22), (31,31).
T(4,3) = 1: (211,211).
T(4,4) = 1: (1111,1111).
Triangle T(n,k) begins:
    1;
    0,   1;
    1,   1,   1;
    2,   2,   1,   1;
    6,   4,   3,   1,  1;
    8,  10,   5,   3,  1,  1;
   24,  18,  13,   6,  3,  1,  1;
   30,  42,  23,  14,  6,  3,  1, 1;
   74,  72,  55,  26, 15,  6,  3, 1, 1;
  110, 146,  95,  61, 27, 15,  6, 3, 1, 1;
  219, 256, 201, 109, 64, 28, 15, 6, 3, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Column k=0 gives A260669.
Row sums and T(2n,n) give A086737.
Cf. A000041, A000217, A008284, A072233, A370005.

b:= proc(n, m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
      add(add(expand(b(sort([n-i*j, m-i*h])[], i-1)*
       x^min(j, h)), h=0..m/i), j=0..n/i)))
    end:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(expand(g(n-i*j, i-1)*x^j), j=0..n/i)))
    end:
T:= (n, k)-> (coeff(b(n$3), x, k)+coeff(g(n$2), x, k))/2:
seq(seq(T(n, k), k=0..n), n=0..12);

T(n,k) = (A370005(n,k) + A072233(n,k))/2.

A376821 Number of irreducible pairs of partitions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 3, 3, 6, 7, 8, 4, 6, 7, 12, 17, 23, 23, 31, 38, 36, 70, 71, 101, 127, 118, 145, 191, 209, 261, 309, 396, 462, 512, 652, 769, 878, 1097, 1320, 1563, 1827, 2098, 2533, 2932, 3475, 4185, 4756, 5726, 6614, 7686, 9189, 10825

Offset: 0

Pontus von Brömssen, Oct 05 2024

nonn

A pair of partitions of n is irreducible if the two partitions yield the same multinomial coefficient but have no parts in common. The partitions in the pair are required to be distinct, otherwise a(0) would be 1.

			   n | irreducible pairs of partitions of n
  ---+-------------------------------------
   7 | (1,1,1,4), (2,2,3)
   8 | (1,1,6), (3,5)
  10 | (1,4,5), (2,2,6)
  13 | (1,1,1,10), (6,7)
     | (1,1,3,8), (2,4,7)
     | (1,1,1,1,1,8), (2,2,2,7)
  14 | (1,2,2,9), (3,3,8)
     | (1,1,1,2,9), (3,4,7)
     | (1,1,1,1,1,1,4,4), (2,2,2,2,3,3)

George E. Andrews, Arnold Knopfmacher, and Burkhard Zimmermann, On the number of distinct multinomial coefficients, Journal of Number Theory 118 (2006), 15-30; arXiv preprint, arXiv:math/0509470 [math.CO], 2005. (See Section 7.)

Cf. A070289, A260669, A325306, A376661.

cp's OEIS Frontend

A054440 Number of ordered pairs of partitions of n with no common parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A108796 Number of unordered pairs of partitions of n (into distinct parts) with empty intersection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A365662 Number of ordered pairs of disjoint strict integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A284592 Square array read by antidiagonals: T(n,k) is the number of pairs of partitions of n and k respectively, such that the pair of partitions have no part in common.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A366132 Number of unordered pairs of distinct strict integer partitions of n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A366317 Number of unordered pairs of strict integer partitions of n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A370005 Number T(n,k) of ordered pairs of partitions of n with exactly k common parts; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A370207 Number T(n,k) of unordered pairs of partitions of n with exactly k common parts; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author