Язык Wolfram Language™

Решение комбинаторной задачи с использованием постоянной

Постоянная схожа с детерминантой с различием в том, что все члены имеют положительный знак.

In[1]:=

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$]]]\)]

Out[1]=

In[2]:=

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$]]]\)]

Out[2]=

Таким образом, применение Permanent для матрицы, все элементы которой равны 1 является интересным, но неэффективным способом вычисления функции факториала.

In[3]:=

Table[Permanent[ConstantArray[1, {n, n}]], {n, 10}]

Out[3]=

Постоянная может использоваться для решения более интересных комбнаторных задач: даны n систем, каждая из которых содержит подсистему . Сколько существует способов нахождения определённого элемента из каждой подсистемы? Начнем с создания матрицы m, в которой положение (i, j) содержит 1, когда подсистема i содержит j, и 0 в противном случае.

In[4]:=

sets = {{3, 5, 6, 7}, {3, 7}, {1, 2, 4, 5, 7}, {3}, {1, 3, 6}, {1, 5, 7}, {1, 2, 3, 6}}

Out[4]=

In[5]:=

m = Table[If[MemberQ[sets[[i]], j], 1, 0] , {i, 7}, {j, 7}]; m // MatrixForm

Out[5]//MatrixForm=

Постоянная m является решением задачи.

In[6]:=

Permanent[m]

Out[6]=

Доказать результат, точно создав все наборы чисел.

In[7]:=

Select[Tuples[sets], DuplicateFreeQ]

Out[7]=