A008302 Thomas Wieder, Comments on A008302

We define the coefficients K(m,j) = 1 if 0 <= j <= m and 0 else, where m 
is an integer with m = 0,1,2,3... These K(m,j) can be considered as binomial 
coefficients for the unlabeled case. In the unlabeled case, we select j 
elements from an unlabeled m-set M={*,*,...,*} composed of m unlabeled elements
 '*'. Obviously, we can take j elements from M in one manner only. 

Let p~(k,i,n-1) = k_1+k_2+...+k_i+...+k_(n-1)=k be an unordered integer 
partition of k into i parts > 0 and (n-1) - i parts = 0. The number of parts 
(length) of the partition p~(k,i,n-1) is equal to n-1. For i the values i = 
1,2,...,n-1 are allowed. We will speak of partitions p~ with zeros attached. 
Example: For k=4, i=2 and n=4 we have the following unordered partitions with 
i=2 parts > 0 and (4-1)-2=1 part = 0: p~_1(4,2,3) = [0,2,2] and p~_2(4,2,3)= 
[0,1,3]. For k=0 we set p~(0,0,n-1)=[0,0,...,0] with (n-1) zeros.

>From an unordered partition p~ we can form an ordered partition p~ by 
permutation. The ordered partitions p~ for k=4 i=2 and ((n=4)-1)=3 are 
[3, 1, 0], [3, 0, 1], [1, 3, 0], [1, 0, 3], [0, 3, 1], [0, 1, 3],
[2, 2, 0], [2, 0, 2], [0, 2, 2]].

Let denote sum_{k_1+k_2+...+k_(n-1)=k} a sum over all such ordered integer 
partitions p~(k,i,n-1) of given k. Then T(n,k) in A008302 is such a sum over a 
product of those coefficients K(m,l) with

T(n,k)=sum_{k_1+k_2+...+k_i+...+k_(n-1)=k} K(1,k_1) K(2,k_2)...K(n-1,k_(n-1)).

In this formula, k may run from 0 to n(n-1)/2.


Example: n=4. We omit all ordered partitions for which the product vanishes.


For k=0 we have T(n=4,k=0)= 1 because

K(1,0) K(2,0) K(3,0) = 1

and the sum equals 1.


For k=1 we have T(n=4,k=1)= 3 because

K(1,1) K(2,0) K(3,0) = 1
K(1,0) K(2,1) K(3,0) = 1
K(1,0) K(2,0) K(3,1) = 1

and the sum equals 3.


For k=2 we have T(n=4,k=2)=5 because

K(1,1) K(2,1) K(3,0) = 1
K(1,1) K(2,0) K(3,1) = 1
K(1,0) K(2,1) K(3,1) = 1
K(1,0) K(2,2) K(3,0) = 1
K(1,0) K(2,0) K(3,2) = 1

and the sum equals 5.


For k=3 we have T(n=4,k=3)=6 because

K(1,1) K(2,1) K(3,1) = 1
K(1,1) K(2,2) K(3,0) = 1
K(1,0) K(2,1) K(3,2) = 1
K(1,0) K(2,2) K(3,1) = 1
K(1,1) K(2,0) K(3,2) = 1
K(1,0) K(2,0) K(3,3) = 1

and the sum equals 6.


For k=4 we have T(n=4,k=4)=5 because

K(1,1) K(2,1) K(3,2) = 1
K(1,1) K(2,2) K(3,1) = 1
K(1,0) K(2,2) K(3,2) = 1
K(1,1) K(2,0) K(3,3) = 1
K(1,0) K(2,1) K(3,1) = 1

and the sum equals 5.


For k=5 we have T(n=4,k=5)=3 because

K(1,1) K(2,1) K(3,3) = 1
K(1,1) K(2,2) K(3,2) = 1
K(1,0) K(2,2) K(3,3) = 1

and the sum equals 3.


For k=6 we have T(n=4,k=6)=1 because

K(1,1) K(2,2) K(3,3) = 1

and the sum equals 1.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Example for the use of the Maple program MacMahon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

> with(combinat):
> read("E:/Eigene Dateien/Maple/MacMahon.mpl"):
> MacMahon(4);
                         "MM(", 0, ")=", 1
                         "MM(", 1, ")=", 3
                         "MM(", 2, ")=", 5
                         "MM(", 3, ")=", 6
                         "MM(", 4, ")=", 5
                         "MM(", 5, ")=", 3
                         "MM(", 6, ")=", 1
                     "Sum of all MM(k) = ", 24

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Begin of Maple Program MacMahon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

MacMahon:=proc(n::integer)

# Begonnen am: 5.12.2007
# Letzte Änderung am: 9.12.2007
# Berechne die Zahlen von Mac Mahon.
# thomas.wieder@t-online.de

# n=3 --> MM(3,0) = 1, MM(3,1) = 2, MM(3,2) = 2, MM(3,3) = 1.

# Voraussetzungen:
# Die Partitionen enthalten auch die Null.
# Die Partitionen sind geordnet.
# Die Zahl der Teile einer Partition ist gleich n-1.

local iverbose, i, k, kend, Teil, ZahlTeile, ListeDerPartitionen,
      EinePartition, Summe, Produkt, Term, MM;

# Please load the package combinat using the command: with(combinat);

iverbose:=0;
# For iverbose:=1; you will get a output for debugging purposes.

# Sample output for n=3 and iverbose = 1:
#
#                                " "
#                          "Schleife k=", 0
#
#                     "ListeDerPartitionen=", []
#
#                         "MM(", 0, ")=", 1
#
#                                " "
#
#                          "Schleife k=", 1
#
#              "ListeDerPartitionen=", [[1, 0], [0, 1]]
#
#                        "Partition=", [1, 0]
#
#                "EinePartition, Produkt=", [1, 0], 1
#
#                        "Partition=", [0, 1]
#
#                "EinePartition, Produkt=", [0, 1], 1
#
#                         "MM(", 1, ")=", 2
#
#                                " "
#
#                          "Schleife k=", 2
#
#          "ListeDerPartitionen=", [[2, 0], [0, 2], [1, 1]]
#
#                        "Partition=", [2, 0]
#
#                "EinePartition, Produkt=", [2, 0], 0
#
#                        "Partition=", [0, 2]
#
#                "EinePartition, Produkt=", [0, 2], 1
#
#                        "Partition=", [1, 1]
#
#                "EinePartition, Produkt=", [1, 1], 1
#
#                         "MM(", 2, ")=", 2
#
#                                " "
#
#                          "Schleife k=", 3
#
#      "ListeDerPartitionen=", [[3, 0], [0, 3], [2, 1], [1, 2]]
#
#                        "Partition=", [3, 0]
#
#                "EinePartition, Produkt=", [3, 0], 0
#
#                        "Partition=", [0, 3]
#
#                "EinePartition, Produkt=", [0, 3], 0
#
#                        "Partition=", [2, 1]
#
#                "EinePartition, Produkt=", [2, 1], 0
#
#                        "Partition=", [1, 2]
#
#                "EinePartition, Produkt=", [1, 2], 1
#
#                         "MM(", 3, ")=", 1
#
#                      "Sum of all MM(k) = ", 6

Summe:=0;

kend:=(n-1)*(n)/2;

# Schleife über die Klassen *** k ***.
for k from 0 to kend do
if iverbose=1 then print(" "); print("Schleife k=",k) fi;

if k=0 then
MM[k]:=1;
else
MM[k]:=0;
fi;

   ListeDerPartitionen:=NULL;
   # Schleife über die Zerlegungen von *** n-1 *** in *** i *** Teile.
   for i from 1 to n-1 do
   # Erstelle die Liste aller geordneten Partitionen von *** k *** 
   # in *** i *** Teile > 0,
   # wobei die Länge jeder Partition gleich *** n-1 *** ist.
   ListeDerPartitionen:=
ListeDerPartitionen,op(AlleGeordnetenPartitionenVonNInKTeileUndNullen(k,i,n-1));
   end do;
   ListeDerPartitionen:=[ListeDerPartitionen];
   if iverbose=1 then print("ListeDerPartitionen=",ListeDerPartitionen) fi;

       # Nimm eine Partition.
       for EinePartition in ListeDerPartitionen do
       if iverbose=1 then print("Partition=",EinePartition) fi;
                 
           Produkt:=1;
           i:=0;
           # Nimm einen Teil der Partition.
           for Teil in EinePartition do
           i:=i+1;
           
               # Setze den Teil *** Teil *** auf die Stelle *** i ***.
               Term:=KC(i,Teil);
               Produkt:=Produkt*Term;
               #if iverbose=1 then print("Teil, Term:",Teil,Term) fi;
           
           # Ende der Schleife *** Teil ***
           end do;

       MM[k]:=MM[k]+Produkt;
       if iverbose=1 then print("EinePartition, Produkt=", EinePartition,
       Produkt) fi;

       # Ende der Schleife *** EinePartition ***
       end do;

print("MM(",k,")=",MM[k]);
Summe:=Summe+MM[k];
# Ende der Schleife über *** k ***
end do;

print("Sum of all MM(k) = ",Summe);
end proc;



AlleGeordnetenPartitionenVonNInKTeileUndNullen:= proc(n::integer, k::integer,
Länge::integer)
# Begonnen am: 9.12.2007
# Letzte Änderung am: 9.12.2007
# thomas.wieder@t-online.de

# Berechne alle geordneten Partitionen der ganzen Zahl *** n ***
# in *** k *** Teile und fülle diese Partitionen jeweils auf
# die Länge *** Länge *** mit Nullen auf.
# Z.B: n=3, k=2, Länge=3 --> [1,2] wird zu [1,2,0].

# AlleGeordnetenPartitionenVonNInKTeileUndNullen(4,1,3); --> 
# [[4, 0, 0], [0, 4,0], [0, 0, 4]].
# AlleGeordnetenPartitionenVonNInKTeileUndNullen(4,2,3); --> 
# [[3, 1, 0], [3, 0,1], [1, 3, 0],
# [1, 0, 3], [0, 3, 1], [0, 1, 3],
# [2, 2, 0], [2, 0, 2], [0, 2, 2]].
# AlleGeordnetenPartitionenVonNInKTeileUndNullen(4,3,3); --> 
# [[2, 1, 1], [1, 2,1], [1, 1, 2]].

local iverbose, EinePartition, AllePartitionenVonNOhneNullen,
AlleGeordnetenPartitionenVonNUndNullen, PermutationenDerPartition, AnzahlNullen;
iverbose:=0;

AlleGeordnetenPartitionenVonNUndNullen:=NULL;

AllePartitionenVonNOhneNullen := PartitionList(n,k);
if iverbose = 1 then
print("AlleGeordnetenPartitionenVonNUndNullen",AllePartitionenVonNOhneNullen);
end if;

for EinePartition in AllePartitionenVonNOhneNullen do

# Nullen einfügen.
AnzahlNullen:= Länge - k;
if AnzahlNullen > 0 then
# Hänge **** AnzahlNullen *** Nullen an.
EinePartition:=op(EinePartition),0$AnzahlNullen;
EinePartition:=[EinePartition];
end if;

PermutationenDerPartition := permute(EinePartition);
AlleGeordnetenPartitionenVonNUndNullen:=
AlleGeordnetenPartitionenVonNUndNullen,op(PermutationenDerPartition);
if iverbose = 1 then
print("EinePartition, PermutationenDerPartition",EinePartition,
PermutationenDerPartition);
end if;

end do;
AlleGeordnetenPartitionenVonNUndNullen:=
[AlleGeordnetenPartitionenVonNUndNullen];
end proc;



KC:=proc(n::integer,k::integer)
# Begonnen am: 5.12.2007
# Letzte Änderung am: 5.12.2007
local KC;
if (0 <= k) and (k <= n) then
KC:=1;
else
KC:=0;
fi;
end proc;



PartitionList := proc (n, k) # Authors: 
# Herbert S. Wilf and Joanna Nordlicht,
# Source:
# Lecture Notes "East Side West Side,..."
# University of Pennsylvania, USA, 2002. # Avalible at:
http://www.cis.upenn.edu/~wilf/lecnotes.html
# Calculates the partition of *** n *** into *** k ***parts.
# E.g. PartitionList(5,2) --> [[4, 1], [3, 2]].
local East, West;
if n < 1 or k < 1 or n < k then
#if n < 0 or k < 0 or n < k then
RETURN([])
elif n = 1 then
RETURN([[1]])
else if n < 2 or k < 2 or n < k then
#else if n < 1 or k < 1 or n < k then
West := []
else
West := map(proc (x) options operator, arrow;
[op(x), 1] end proc,PartitionList(n-1,k-1)) end if;
if k <= n-k then
East := map(proc (y) options operator, arrow;
map(proc (x) options operator, arrow; x+1 end proc,y) end proc,PartitionList(n-
k,k))
else East := [] end if;
RETURN([op(West), op(East)])
end if;
end proc;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% End of Maple Program MacMahon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%