taking apart the partition numbers (A000041)

wouter meeussen wouter.meeussen at pandora.be
Sun Aug 10 13:25:00 CEST 2003

```dear SeqFanners,

consider the following subset of the partitions of 12:

{12}
{8, 4}
{8, 2, 2}
{8, 1, 1, 1, 1}
{6, 6}
{4, 4, 4}
{4, 4, 2, 2}
{4, 4, 1, 1, 1, 1}
{4, 2, 2, 2, 2}
{4, 2, 2, 1, 1, 1, 1}
{4, 1, 1, 1, 1, 1, 1, 1, 1}
{3, 3, 3, 3}
{2, 2, 2, 2, 2, 2}
{2, 2, 2, 2, 1, 1, 1, 1}
{2, 2, 1, 1, 1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

it shows the partitions of 12 into either
(multiples of 4) or (runs of equal integers that sum to a multiple of 4).

This type of thing shows up in the symmetry of Set Partitions under
rotation.  (Yes, I'm still slowly eating away at that).
All set partitions of 12 that have fourfold symmetry, have block lengths
that fall in these types.

Now, instead of 4, we can take any divisor d of 12, and generate the
partitions "symmetric under d-fold rotation" :
d=12:
{{12},{6,6},{4,4,4},{3,3,3,3},{2,2,2,2,2,2},{1,1,1,1,1,1,1,1,1,1,1,1}}

d=6:
{{12},{6,6},{6,3,3},{6,2,2,2},{6,1,1,1,1,1,1},{4,4,4},{3,3,3,3},{3,3,2,2,2},
{3,3,1,1,1,1,1,1},{2,2,2,2,2,2},{2,2,2,1,1,1,1,1,1},{1,1,1,1,1,1,1,1,1,1,1,1}}
etc.

It is obvious that the 6-fold partitions will contain the (higher symmetric)
12-fold partitions, and generally a k-fold partition will contain all m-fold
partitions for k any multiple of m. We can clean out the multiples by a
'variation' on the Cauchy-Frobenius-not_Burnside Lemma (or, ahumm, play
with it until it clicks):

n            # of d-fold partitions of n                     same, with
multiples cleaned out.

1     {1}                              {1}
2     {2,2}                            {0,2}
3     {3,2}                            {1,2}
4     {5,4,3}                          {1,1,3}
5     {7,2}                            {5,2}
6     {11,8,5,4}                       {2,4,1,4}
7     {15,2}                           {13,2}
8     {22,14,7,4}                      {8,7,3,4}
9     {30,9,3}                         {21,6,3}
10    {42,24,5,4}                      {17,20,1,4}
11    {56,2}                           {54,2}
12    {77,40,18,16,12,6}               {31,18,6,10,6,6}
13    {101,2}                          {99,2}
14    {135,64,5,4}                     {70,60,1,4}
15    {176,31,10,4}                    {139,27,6,4}
16    {231,100,32,11,5}                {131,68,21,6,5}
17    {297,2}                          {295,2}
18    {385,154,54,30,9,6}              {207,124,21,24,3,6}
19    {490,2}                          {488,2}
20    {627,232,61,20,12,6}             {387,165,55,8,6,6}
21    {792,88,10,4}                    {698,84,6,4}
22    {1002,344,5,4}                   {657,340,1,4}
23    {1255,2}                         {1253,2}
24    {1575,504,144,112,68,28,23,8}    {995,347,76,69,45,20,15,8}
25    {1958,35,3}                      {1923,32,3}
26    {2436,728,5,4}                   {1707,724,1,4}
27    {3010,225,20,4}                  {2785,205,16,4}
28    {3718,1040,197,20,12,6}          {2670,837,191,8,6,6}
29    {4565,2}                         {4563,2}
30    {5604,1472,351,63,144,32,14,8}   {3900,1304,201,25,136,24,6,8}

I've tried to find traces of this in OEIS but came up empty,
except for the obvious like
# of n-fold partitions of n = sigma(n) and
first column = P(n) = rowsum of last column

Wouter.