Lösen Sie Kombinatorikaufgaben mit Permanenten
Eine Permanente ist ähnlich der Determinante, außer dass alle Terme ein positives Vorzeichen besitzen.
![Click for copyable input](assets.de/solve-combinatorial-problems-using-permanent/In_85.png)
Permanent[\!\(\*
TagBox[
RowBox[{"(", "", GridBox[{
{
SubscriptBox["a",
RowBox[{"1", ",", "1"}]],
SubscriptBox["a",
RowBox[{"1", ",", "2"}]]},
{
SubscriptBox["a",
RowBox[{"2", ",", "1"}]],
SubscriptBox["a",
RowBox[{"2", ",", "2"}]]}
},
GridBoxAlignment->{
"Columns" -> {{Left}}, "ColumnsIndexed" -> {},
"Rows" -> {{Baseline}}, "RowsIndexed" -> {}, "Items" -> {},
"ItemsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {
Offset[0.27999999999999997`], {
Offset[0.7]},
Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
Offset[0.2], {
Offset[0.4]},
Offset[0.2]}, "RowsIndexed" -> {}, "Items" -> {},
"ItemsIndexed" -> {}}], "", ")"}],
Function[BoxForm`e$,
MatrixForm[BoxForm`e$]]]\)]
![](assets.de/solve-combinatorial-problems-using-permanent/O_74.png)
![Click for copyable input](assets.de/solve-combinatorial-problems-using-permanent/In_86.png)
Permanent[\!\(\*
TagBox[
RowBox[{"(", "", GridBox[{
{
SubscriptBox["a",
RowBox[{"1", ",", "1"}]],
SubscriptBox["a",
RowBox[{"1", ",", "2"}]],
SubscriptBox["a",
RowBox[{"1", ",", "3"}]]},
{
SubscriptBox["a",
RowBox[{"2", ",", "1"}]],
SubscriptBox["a",
RowBox[{"2", ",", "2"}]],
SubscriptBox["a",
RowBox[{"2", ",", "3"}]]},
{
SubscriptBox["a",
RowBox[{"3", ",", "1"}]],
SubscriptBox["a",
RowBox[{"3", ",", "2"}]],
SubscriptBox["a",
RowBox[{"3", ",", "3"}]]}
},
GridBoxAlignment->{
"Columns" -> {{Left}}, "ColumnsIndexed" -> {},
"Rows" -> {{Baseline}}, "RowsIndexed" -> {}, "Items" -> {},
"ItemsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {
Offset[0.27999999999999997`], {
Offset[0.7]},
Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
Offset[0.2], {
Offset[0.4]},
Offset[0.2]}, "RowsIndexed" -> {}, "Items" -> {},
"ItemsIndexed" -> {}}], "", ")"}],
Function[BoxForm`e$,
MatrixForm[BoxForm`e$]]]\)]
![](assets.de/solve-combinatorial-problems-using-permanent/O_75.png)
Eine Permanente auf eine Matrix anzuwenden, deren Einträge alle gleich 1 sind, ist eine vergnügliche, aber ineffiziente Art, die Fakultät zu berechnen.
![Click for copyable input](assets.de/solve-combinatorial-problems-using-permanent/In_87.png)
Table[Permanent[ConstantArray[1, {n, n}]], {n, 10}]
![](assets.de/solve-combinatorial-problems-using-permanent/O_76.png)
Mit der Permanente kann auch das folgende, wesentlich interessantere Kombinatorikproblem gelöst werden: Gegeben seien Mengen, von denen jede eine Teilmenge
enthält. Wie viele Möglichkeiten gibt es, ein immer anderes Element von jeder Teilmenge auszuwählen? Konstruieren Sie zuerst die Matrix
, wobei die Position
eine 1 enthält, wenn
in der Teilmenge
enthalten ist, und 0, wenn nicht.
![Click for copyable input](assets.de/solve-combinatorial-problems-using-permanent/In_88.png)
sets = {{3, 5, 6, 7}, {3, 7}, {1, 2, 4, 5, 7}, {3}, {1, 3, 6}, {1, 5,
7}, {1, 2, 3, 6}}
![](assets.de/solve-combinatorial-problems-using-permanent/O_77.png)
![Click for copyable input](assets.de/solve-combinatorial-problems-using-permanent/In_89.png)
m = Table[If[MemberQ[sets[[i]], j], 1, 0] , {i, 7}, {j, 7}];
m // MatrixForm
![](assets.de/solve-combinatorial-problems-using-permanent/O_78.png)
Die Permanente von ist die Lösung des Problems.
![Click for copyable input](assets.de/solve-combinatorial-problems-using-permanent/In_90.png)
Permanent[m]
![](assets.de/solve-combinatorial-problems-using-permanent/O_79.png)
Bekräftigen Sie die Antwort, indem Sie alle Tupel darstellen.
![Click for copyable input](assets.de/solve-combinatorial-problems-using-permanent/In_91.png)
Select[Tuples[sets], DuplicateFreeQ]
![](assets.de/solve-combinatorial-problems-using-permanent/O_80.png)