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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%