All Questions
79
questions
8
votes
0
answers
280
views
Count permutations with given longest increasing subsequence
Problem: Given $n \in \mathbb{Z}_+$ and a set $A \subset \{ 1,\ldots,n \}$ sorted in ascending order, find the number of permutations $\sigma \in S_n$ such that $A$ is a longest increasing subsequence ...
- 4,051
1
vote
1
answer
48
views
Indexing function for placements of identical balls into distinct boxes.
I am trying to find out if there is a mathematical function which can take n objects and place them in m boxes in a way that is indexed?
For example if I had 3 balls and I wanted them in 4 boxes, the ...
- 111
0
votes
0
answers
24
views
Counting Paths in the XY Plane (Discrete math) [duplicate]
I need help with the following mathematical task:
A particle moves in the xy-plane according to the following rules:
U: (m, n) → (m+1, n+1)
L: (m, n) → (m+1, n-1)
where m and n are integers. I need ...
- 39
1
vote
2
answers
73
views
When can a deck be shuffled by shuffling fixed subdecks?
Suppose I want to shuffle a deck of $n$ cards, but I have a problem -- for some reason, I am only able to shuffle at most $n-1$ cards at a time at some fixed indices. For example, if $n=5$, I could ...
- 685
0
votes
0
answers
32
views
Effectively solve optimization problem in this system?
The system :
Given
$2$ sets $I,J$ such that $I\cap J = \emptyset , \#I = \#J$
a time-dependent function $c : \mathbb{R}_{\ge 0} \times I \times J \to \mathbb{R}_{\ge 0}$ .
Consider a system that ...
- 910
0
votes
0
answers
19
views
Is there a formula to find a permutation from a given rank?
Observing, for example, a set of permutations from 4 choose 2:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
Does such a formula exist to go from a permutation's rank to the values of it's permutation (...
- 1
0
votes
4
answers
195
views
Get all the methods to break 100% into certain number of parts?
Being straight about the question, for a program I'm writing, I need to divide 100% into 5 parts. In my program, percentages incremented/decremented by 10%. So I can express my requirement in the ...
- 103
0
votes
1
answer
99
views
What is the name of this variant of n choose k but with multiple subsets to pick?
$n$ choose $k$ can be seen as permuting a binary string with $k$ of the digits set to $1$, and $n - k$ of them to $0$. For example if the string is length $n=6$ and $k=3$, one permutation would be:
$$...
- 127
2
votes
1
answer
281
views
An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements
Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
- 922
1
vote
1
answer
429
views
Number of permutations following given order
I have $n$ numbers and ordered sets $s_i$ of some of these numbers, I need to calculate the number of all the possible permutations of the $n$ numbers respecting the orders in the sets $s_i$. I found ...
- 111
1
vote
0
answers
59
views
Is there a general term formula for 3 queens problem?
The specific question description is: Put 3 queens on a chessboard of M columns and N rows, how to determine the number of ways that no two of them are in attacking positions?
Note that M is not ...
- 11
1
vote
1
answer
163
views
Algorithms to check Pattern Avoidance Permutations
My question is the following: Given two permutations $\pi \in S_{n}$ and $\mu \in S_{k}$, decide whether $\pi$ is $\mu$-avoiding or not.
I think the formal definition is quite hard to write in the ...
- 108
1
vote
0
answers
55
views
How do I find unique rearrangements when given items & the item distributions?
I'm not sure what this type of question is called, but this what I'm trying to solve:
I own
3 hats
1 hat is red
2 hats are blue
4 shirts
1 shirt is red
1 shirt is blue
2 shirts are green
5 pairs ...
- 19
3
votes
2
answers
106
views
select sequence without "ABCD"
There are an infinite number of coupons bearing one of the letters A,B,C,D. Find the number of ways for selecting $10$ of these coupons so that there shouldn't be sequence of "ABCD", which ...
- 281
1
vote
0
answers
287
views
Rephrase a simple mathy logic problem (yielding solution of an ordered procedure), and its generalized counterpart, into a solvable algorithm.
I'm given a selection of logic puzzles about different entities crossing a river safely (either from the same side to the same other side, or switching sides; utilizing the same boat, with certain ...
- 29