Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
350
questions
2
votes
2answers
100 views
Find all permutations with a condition (part 2) [closed]
This question (21008) asks to find all permutations of {a, b, c} subject to a + b + c = n. The answer was provided by Dr. ...
3
votes
1answer
124 views
Speeding the computation of Landau's function
This computational question is based on this question of combinatorics on the Mathematics.SE.
A permutation of a list of $n$ items, $\{ 1, 2, \ldots, n \}$, is of course a reordering of them. If ...
1
vote
2answers
226 views
Using Mathematica to solve matrix equations
I am curious as to whether it is possible to use Mathematica for counting the number of square matrices $S$ (with non-negative integer entries) of size $n$x$n$ that satisfy: $\sum_{i,j=1}^n S_{ij}=n-1....
3
votes
6answers
134 views
Finding the number of $4$-tuples of consisting of digits $1$-$6$ satisfying a certain condition
I'm trying to enumerate a sample space for an experiment in which $4$ fair $6$-sided dice are rolled such that exactly $3$ of them are $5$s or $6$s. The way I understand it, the last die must be any ...
1
vote
1answer
150 views
All Perfect Matchings on a Square Lattice
Is there a way to quickly display all the perfect matchings of the vertices of a square lattice?
The following code only finds one:
...
2
votes
2answers
301 views
Sum over permuted indices
Consider this rank 6 tensor: $g_{ab}g_{cd}g_{ef}$.
Now I'd like to have a code to sum over all possible $6!$ permutations of the six indices with some coefficient $f[i]$, where $1 \leq i \leq 720$... ...
7
votes
4answers
308 views
Number of ways of writing N as sum of K positive natural numbers not more than W
My problem is similar to this
where i want to count number of ways where Order also matters. ( Restricted Composition instead of Restricted Partition).
Ex, n = 6, k =4, w = 3
Partitions: {2,2,1,1}...
3
votes
2answers
142 views
How can I output list of permutation products?
I have A = Permutations[{1, 2, 3, 4}]. And c = Cycles[{{1, 2, 3, 4}}].
And I need to output for all $a \in A: a \cdot с \cdot a^{...
0
votes
0answers
416 views
Splitting a list into 2 sublists in all possible ways
I have a list and I want to split it into 2 sublists in all possible ways
If
S={1,2,3,4}
I should get
...
1
vote
1answer
106 views
How do I calculate the number of possible cases of polynomial equation (combinations) in Mathematica?
if I have the equation
$$f(x_1,x_2,x_3,x_4)=x_1x_3+x_2x_4+x_1x_2x_4+x_1x_2x_3x_4$$
How many equations are possible if two variables ?
when $x_1=x$ and the other four are y
when $x_2=x$ and the ...
6
votes
0answers
127 views
how to efficiently generate all directed graphs with 6 vertices
I am attempting to generate all non-isomorphic directed graphs with 6 vertices using command ListGraphs[6, Directed].But it does not work efficiently and takes a ...
16
votes
7answers
953 views
Permutations of nested parentheses (Dyck words)
How would I construct a function that outputs Dyck Words?
e.g. - there are 14 words in $\mathcal{D}_{8}$:
...
7
votes
1answer
145 views
Fast creation of state transitions and probabilities?
Normally I'd wait until I'd fleshed/thought things out further but I find this interesting enough that I think others might.
Take an ordered list of $N$ slots, integers from $[0,2]$. This represents ...
30
votes
9answers
2k views
Faster derangements?
I wonder what is the fastest method to generate derangements?
Both the Combinatorica function and Martin Ender's answer to Permutations of lists of fixed even numbers are based on filtering the ...
5
votes
1answer
308 views
Wilf-Zeilberger simplification
I am working my way through the book "A=B" and doing some of the problems. One of them was to prove that:
$$
\frac{1}{{n+x \choose n+r}} \sum_{k=0}^n{n \choose k}{x\choose k+r}=1
$$
I am able to ...
10
votes
3answers
557 views
Permutations of lists of fixed even numbers
Let's say we have this list
list={3,6,5,21,23,76,1,28,96,54,77}
I would like to know the number of permutations when every even number stays where it is and ...
3
votes
3answers
692 views
Number walls with mathematica
I want to create "number walls" of a user-defined number of rows with mathematica. (They look similar to a CompleteKaryTree.)
Each pair of 2 values in a lower row ...
2
votes
1answer
132 views
Calculating partial binary `Permutations`
I would like MMA to only calculate some of the permutations of a set. I am currently doing something along the lines of
...
2
votes
2answers
86 views
How many combinations of certain variables add up to at least n?
I have a set of numbers, let's say:
a=16
b=19
c=19
d=31
e=5
f=... etc.
How to create a simple function that shows how many combinations of the letters add up to at least the number n?
I have no clue ...
2
votes
2answers
750 views
How to “Prove” this summation result?
I have this messy function with $n$, $k$, $i$ integers:
$$ r(\rm n,k)=\frac{k 2^{1-2 \rm{n}} (2 k)! (-2 k+2 \rm{n}+1) (2 \rm{n}-2 k)!}{(k!)^2 \left(1-4 (i-k)^2\right) ((\rm{n}-k)!)^2} $$
I want to ...
2
votes
2answers
243 views
Integer partitions without repetitions
What combination of numbers makes a specific sum?
The code below is not very effective, because it also gives answers in which a number is used more than once even though it was given in the list ...
4
votes
1answer
104 views
Summing factors of binomial coefficients - get general formula?
Consider summing more and more factors of binomial coefficients:
...
7
votes
3answers
1k views
List all possible license plate numbers
The length of license plate numbers is 6, with 2 letters and 4 numbers.
The first two characters are letters and the last four are numbers. Example: AA1234.
This is the code I have so far:
...
8
votes
1answer
195 views
Doing combinations of sub-sublists
To create a list of all the possible combinations of a sublist.
I have a list, somewhat resembling the following format:
...
2
votes
2answers
211 views
Modified Multinomial formula
I am trying to compute an explicit formula using Mathematica for the following multinomial expression:
\begin{equation} \sum_{n_{1}+n_{2}+...+n_{M}=N}^{M} {N \choose
n_{1},n_{2},...,n_{M }} \cdot ...
2
votes
2answers
177 views
How many equation systems can I build from five equations?
Suppose I have five quantities:
A1 = 4; A2 = 2 + 4b; A3 = a + 6 b; A4 = 10 b; A5 = 4 a
I want to make as many systems of equations as I can from these five ...
6
votes
3answers
463 views
Duplicate Permutations with Tuples
Permutations without repetition
(in Italian: simple dispositions)
Permutations[{a, b, c, d}, {3}]
or
...
10
votes
5answers
696 views
unordered Tuples [duplicate]
I gather from this question that there is no primitive to build unordered tuples. That is, I want to do the equivalent of the following:
...
1
vote
1answer
98 views
Choose numerical values according to given rules
General problem
Given a set of logical expressions I need to find numbers with a margin between pairs that obey the logical rules.
Example
For the expression $m=n=o,p=q$ with a margin of 10 the ...
1
vote
0answers
176 views
Wilf-Zeilberger algorithm in Mathematica [duplicate]
I am trying to prove the q-combinatorial identity
$$\sum_{s=0}^r(-1)^sq^{\frac{s(s+1)}{2}}{n-2r+s\brack n-2r}_q{n\brack r-s}_q=\sum_{s=0}^{r-1}(-1)^{s+1}q^{\frac{s(s+1)}{2}}{n-2r+s\brack n-2r}_q{n\...
0
votes
1answer
105 views
How do you group cycles?
I want to define a function that takes a list of pairs as input and groups cycles, e.g. {{a1,a2},{b1,b2},{a2,a3},{c1,c2},{a3,a1},{b2,b1}} becomes ...
4
votes
1answer
84 views
More efficient ways of listing matchings of possible rolls of 10 dice by max matching
The question is inspired by a dice game named 'Tenzi'. You roll 10 dice and record the size of the largest matching (the face-value is irrelevant). Exhaustively, listing all combinations of matchings ...
6
votes
1answer
220 views
How does FindGeneratingFunction work?
How do FindGeneratingFunction and FindSequenceFunction work?
How might one implement similar functionality from scratch in ...
3
votes
1answer
138 views
Applying the binomial theorem with an arbitrary exponent
I was asked a question by a student today. The solution I came up with seemed a bit suspicious, so I tried to verify it using Mathematica and failed. I created a PDF of my solution which can be found ...
4
votes
4answers
255 views
Listing sequence with rules
How would one go about listing all sequences S length 10 made up of a combination of a's and ...
6
votes
1answer
130 views
Understanding KnapsackSolve
I was playing around with the new KnapsackSolve function in Mathematica 11 and came across something odd that I don't understand. Perhaps someone could shed some ...
3
votes
2answers
116 views
Producing a list of all the pairs can be made by from two lists of equal length [closed]
I have two lists:
{x1, x2, x3, x4, x5}
and
{y1, y2, y3, y4, y5}
How can I get a list like the one below from them, where ...
1
vote
1answer
290 views
How to get a combination of lists from a large list? [closed]
I have a list with ten elements, for example:
{x1,x2,x3,x4,x5,x6,x7,x8,x9,x10}
I want to have all the combinations of the 3 elements-list like below:
...
4
votes
2answers
228 views
How to derive large Tuples (25^25, 50^50,100^100) under certain condition
My problem is that computer has no sufficient memory to calculate tuples of my list. A simple example can be given as follows:
...
4
votes
1answer
59 views
Faster solution to combinatorial problem of two-part contractions
Given a list of elements I need all possible pairings of elements with a leading factor that describes the number of permutations. A (ugly but) working version would be:
...
1
vote
1answer
70 views
Non-Simple Lattice Paths using PathGraph
I am encoding a lattice walk of steps North, South and East on $\mathbb{Z}^{2}$ between the two extremities of the $x$-axis:
...
16
votes
3answers
907 views
House of Santa Claus
The house of Santa Claus is an old German drawing game for small children.
You have to draw a house in one line.
You must not lift your pencil while drawing. $\color{red}{\text{You must not repeat a ...
1
vote
0answers
57 views
Alternative Methods of Using Cumulative Density Functions To Obtain Probabilities
I have a CDF that is generated from the subtraction of two arrays as part of a minimization procedure. A consequence is that events in the simulation can cause the subtracted total to be less than 0:
...
3
votes
0answers
81 views
Generating All Regular Multigraphs — Issue with Solve and/or FindInstance
I'm looking to generate all regular multi-graphs over $n$ vertexes and of degree $d$ in mathematica (side note: $n,d$ are fairly small, this problem gets unmanagable very fast). So here $n,d$ are my ...
7
votes
2answers
402 views
Symmetrization of a Function
Suppose we have a function $f(x_1, \cdots, x_n)$ where $n$ is determined from outside (i.e. our function defined via a double blank f(x__):=...) I'm looking for a ...
4
votes
1answer
132 views
Strategies for simplifying recurrences with sums
The problem:
Count the number of permutations of n distinct objects that leave none of them fixed.
This is actually a well-studied problem with pretty well-...
6
votes
1answer
78 views
Non-trivial partitions of numbers using Combinatorica
I have made a code which gives back partitions of numbers in two Young diagrams (one Young diagram is trivial). For example, the partitions of 1 are
...
4
votes
1answer
262 views
How to efficiently generate unique combination from several lists
For example I have a list
data={{1,3,2},{3,2,4},{2,4,3}}
sublist of data has no duplicate elements.
We know ...
11
votes
1answer
333 views
Warning in version 11.0 when loading package Combinatorica
After the usual and well-known warning
General::compat: "Combinatorica Graph and Permutations functionality has been superseded
by preloaded functionality..."
...
0
votes
0answers
119 views
Tuples with restrictions
SHORT VERSION
Given 2t Ranges, each of length len, what is the fastest way of finding the ...
