Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
347
questions
6
votes
2answers
128 views
Stars and Bars representation
How can I visualise/represent "Stars and Bars" in Mathematica?
Say I have $n$ balls and $k$ slots to fill (or not to fill) with balls, e.g. when $n=4$ and $k=4$,
...
4
votes
4answers
209 views
Finding all the lines that can be defined a set of points
Input ten Points, calculate every possible straight line from each possible pair of points and check if any of the other points are on the lines.
Is something like this possible in mathematica? and ...
2
votes
1answer
57 views
Tuples with more criteria
I have seen that there is question here which does almost what I wanted to ask but it's not quite what I wanted.
Efficiently generating tuples with Outer
What I would like to have is a Tuples of a ...
6
votes
5answers
376 views
A replacement for NextPermutation in Combinatorica [duplicate]
Does anyone know of a replacement for NextPermutation in Combinatorica? The problem with loading Combinatorica is that it interferes with new functionality which I ...
6
votes
1answer
107 views
Generating an efficient way to compute einsum?
Given an einsum like below, how could I generate an efficient computation graph for it?
$$X_{ik} M_{ij}M_{kl} X_{jl}$$
The indices range from $1$ to $d$ and the goal is to minimize computation time ...
1
vote
1answer
66 views
Generating summation formulas for factorized 4th moments
I'm interested in getting summation formulas for the following expression, in Einstein summation notation, with indices ranging from $1$ to $d$ $$c=X_{ik}M_{ijkl}X_{jl}$$
Here $M_{ijkl}$ is ...
7
votes
2answers
217 views
Generating set partition diagrams
I recently came across a very nice illustration of set partitions on wikipedia (Partition of a set article)
I need to reproduce this diagram in order to modify some things, does anyone have a good ...
0
votes
2answers
67 views
Permutations of $ \{1, 2, \dots, n\} $ [duplicate]
When I try
Permutations[Range[1, 12]]; // AbsoluteTiming
I get
{53.6949, Null}
and with ...
1
vote
1answer
64 views
Coloring ladder rung graphs
I can use various algorithms to list all proper $k$-colorings of the vertices of the ladder rung graph $nP_2$, the first six are show below.
Is there a quick way in Mathematica to list all proper $k$-...
3
votes
2answers
92 views
Counting k-colorings of a graph
Combinatorica can list all $k$-colorings of the vertices of a graph $g$, which is a coloring of the vertices with no two colors adjacent, and using no more than $k$-colors:
...
4
votes
1answer
57 views
Counting the number of strings starting with “t” and containing 2 vowels and 2 consonants
I generated a list of strings that match the criteria in the title as follows:
...
3
votes
1answer
87 views
Recursive solution to the extended Josephus problem [duplicate]
The Josephus Problem is described here, with extension of killing every $k$th problem. In the simple case where every other person is killed, we can also use the binary trick.
...
2
votes
2answers
77 views
4
votes
2answers
294 views
How to extract coefficients of a generating function like this one, using a computer?
For example if we have the generating function $G (x) = (1 + x + ... + x^k)^{10}$ and we want to calculate the coefficient of $x^{3k}$ as a function of $k $:
What is the best way to go about it using ...
5
votes
4answers
213 views
Maximum of determinant of $n\times n$-matrix with elements 0 and 1
Generalizing https://math.stackexchange.com/questions/3265627/largest-value-of-a-third-order-determinant-whose-elements-are-0-or-1 I'd like to propose two related problems
(a) find the maximum value ...
4
votes
1answer
115 views
Non-flat partitions of a set
A non-flat partition of a set is one where, when the elements of the set are on a grid, the partition does not contain subsets with elements from the same row. When the set is more irregular the same ...
4
votes
1answer
64 views
Question about FindKClique
Say we have a graph:
g = CompleteGraph[5];
and that we want to find all the triangles in g. I tried to use ...
3
votes
1answer
60 views
Generating integer partitions with fixed first element
I'm trying to generate all integer partitions where the first entry is a fixed number i.e. all young diagrams with first row/column fixed. I'm aware of the function IntegerPartitions[n] and I could ...
0
votes
0answers
33 views
Triangulations of a convex polygon
I have a piece of code which finds all triangulations of a convex polygon. It is known that a number of such triangulations for a given $n$-gon is is given by ($n-2$)th Catalan Number, so for instance,...
4
votes
0answers
56 views
Four color theorem in Mathematica [closed]
The four color theorem is a theorem about graphs (as in graphs and networks) and it was proved with the aid of a computer. To date, there is no hand-checkable proof. The software that was used to ...
0
votes
1answer
76 views
How to generate all the combinations with repetition?
I have $K$ variables.
Each variable can take any value form a set with $N$ elements.
We have $N^K$ possible solutions (permutations with repetition, when at each time slot we can choose among $N$ ...
1
vote
2answers
259 views
How to generate all the combinations? [duplicate]
There are $N$ optimization variables, $v_1,v_2,\cdots,v_N$.
and $v_n\in{0,1,2,3,\cdots,K}$.
Let $N=10$ and $K=5$.
How can I generate all the possible combinations?
For example, the first ...
0
votes
1answer
52 views
How make create all possible lists of twelve elements? [closed]
How can I create all possible lists of twelve elements when each element can be -1 or 1. That is, 2^12 different lists.
0
votes
1answer
36 views
Expanding integer compositions
Quick version: I would like Mathematica code that, for instance, turns {3,1,2} into {3,3,3,1,2,2}. More formally, given positive integers $c_1, \ldots, c_t$ which sum to $n$, produce the length $n$ ...
0
votes
1answer
39 views
0
votes
1answer
33 views
Different result with HypergeometricPFQ
I have a following sequence:
Table[Sum[Sum[(1 + j + k + n)!/((1 + j + k) j! k! ), {j, 0, n}], {k, 0, n}], {n, 1, 5}]
(* {16, 542, 31488, 2646024, 292224000} *)
...
5
votes
1answer
530 views
Is there a function to partition an integer set?
First I give an example. For an integer set $(0,1,2,3,4)$, there are eight kinds of subdivision or partition like this
$$(0,4);\\~~(0,1)(1,4);~~(0,2)(2,4);~~(0,3)(3,4);\\
(0,1)(1,2)(2,4);~~(0,1)(1,3)(...
4
votes
3answers
956 views
Create all possible words using a set or letters
Given a list of letters,
letters = { "A", "B", ..., "F" }
is it possible to get Mathematica to generate all ‘words’ (in this example, 6 letter words), if only ...
1
vote
0answers
39 views
Permute using symmetric vs alternating groups
Why does this happen?
Permute[{0, 0, 0}, SymmetricGroup[3]]
(* {{0, 0, 0}} *)
Permute[{0, 0, 0}, AlternatingGroup[3]]
(* {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}} *)
2
votes
1answer
164 views
Rewrite the power sum in terms of convolution
Let be an identity
$$n^{2m+1}=\sum_{r=0}^{m}A_{m,r}\sum_{k=0}^{n-1}k^r(n-k)^r,$$ where $A_{m,r}$ are real coefficients, see A302971 for numerators and formula of $A_{m,r}$. Here we can notice that $\...
8
votes
0answers
117 views
StableMarriage vs. FindIndependendEdgeSet: How to use the procedure FindIndependendEdgeSet as a Gale-Shapley algorithm?
From Help, the procedure StableMarriage was an element of the Combinatorica, but it is available in the built-in ...
3
votes
1answer
41 views
Using FindInstance for Identifying Feasible Planar Solutions in a 3D Latin Hypercube
Consider a $3d$ lattice latin hypercube with $n$ steps in each dimension, so it has $n^3$ positions. Coordinates $X, Y, Z \in \{1,2,...n\}$. I want to find all of the permutations of them where they ...
1
vote
3answers
126 views
Handling cases of cross terms for multi-sums
I have expressions consisting of many multi-sums and I would like to extract cross terms out of them. Consider a simple example:
$$
\sum_{m_1=1}^M \sum_{m_2=1}^M \sum_{m_3=1}^M \sum_{m_4=1}^M (x_{m_1}...
6
votes
5answers
699 views
Sum of list numbers smaller than one goal
I have five values that I would like to add them so that they can be equal to or less than 3000.
...
1
vote
0answers
37 views
Binomial coefficients for negative entries [duplicate]
Mathematica evaluates the binomial coefficient $\binom{-1}{-1}$ to 1. That agrees with an application I have in mind. However many books, such as Concrete Mathematics, e.g. see here, define $\binom{...
5
votes
3answers
423 views
Find position without iterating
The code below solves for the four value of $m_i$ for a given pair of $(N_m,M_m)$.
where
$$
m_1+m_2+m_3+m_4 = M_m\\
|m_1|+|m_2|+|m_3|+|m_4| = N_m
$$
Edit 2
New Sorting
I have now realised that the ...
0
votes
1answer
41 views
How can I construct binomial terms using the Binomial function? [closed]
I want to construct a table of the terms
Binomial[n, i] t^i (1-t)^(n-i)
where i goes from 0 to ...
1
vote
1answer
56 views
How to find efficiently the independent vertex sets from a large adjacency matrix?
I have a binary adjacency matrix $M$ of size $72\times 72$. I would like to find all possible combinations of 18 non-adjacent nodes.
There are $^{72}C_{18}$ possible (adjacent and non-adjacenct) ...
6
votes
1answer
116 views
Generate list of tuples, modulo PermutationGroup
I have a permutation group, e.g.
g = PermutationGroup[{Cycles[{{1, 2}}]}]
but not necessarily limited to a single generating cycle.
What I want is to create a ...
0
votes
1answer
44 views
Sums of binomial expressions returns different and sometimes indeterminate expressions
A problem that I encountered multiple times when taking sums over expressions involving binomials, factorials, etc. is that Mathematica (version 11.2) returns indeterminate expressions when it should ...
0
votes
2answers
84 views
Tuples of elements from list excluding anything with repeated values
What I would like to do is the following.
For a given list of elements; say (0,1,2,3,4) I would like to obtain all possible combinations of five, but not the ones with ANY repeated values. That is I ...
7
votes
2answers
337 views
How to represent a product of cycles in matrix form?
I have a permutation a in a product of disjoint cycles form as follows
$a = {{(1,9,3,7)(2,11,6)(4,8,5,10)}}$
I want to represent it in a matrix form ...
0
votes
0answers
30 views
Enumerate all lists of $m$ non-negative integers that add to $n$ [duplicate]
Let $x_1,\dots,x_m$ be non-negative integers such that $\sum_{i=1}^m x_i=n$, where $m,n$ are given. How can I enumerate all such lists of $m$ integers that add to $n$?
Note that ...
4
votes
2answers
60 views
Groupings of the Elements of a List with at Most $k$ Elements
Given a list with $n$ elements and an integer $k$ I want to get a list with all possible groupings of these n elements in sets with at most k elements. For example, given $n=\{1,2,3,4\}$ and $k=3$ I ...
3
votes
1answer
281 views
How to calculate all possible resistances made from 5 distinct resistors in series and/or parallel? [closed]
Five distinct resistors resistors={1,2,3,4,5} are given. The objective is to find a list of all possible resistances obtained by configuring all these resistors in ...
2
votes
1answer
101 views
Find All Compositions of an Integer
I can use the Combinatorica package to produce all integer compositions of the integer $n$ into $k$ parts by writing ...
3
votes
0answers
94 views
Package like combinat
I started using Mathematica and want to do some computation involving Characters of the symmetric group. In maple, I used to use the package combinat. The link is below
https://www.maplesoft.com/...
1
vote
3answers
111 views
How to generate the lists of $0 \leq m \leq X$ integer values so these values add up to $X$
This must be basic, but my Mathematica (and overall programming) skill level is too low to find a handy solution:
I need to generate all possible lists of $m$ integers (I call these integers $x_i$'s, ...
8
votes
3answers
283 views
Find k smallest sum n-tuples
Given a collection of sorted lists {l1, l2, ...} I need to find the smallest k index tuples taken from these lists by summed ...
2
votes
1answer
42 views
Simpifying expressions with binomial coefficients
I wrote:
Simplify[Binomial[n, k] - Binomial[n - 1, k]]
I expected Mathematica to simplify this according to Pascal's identity to:
...
