All Questions
Tagged with combinatorics number-theory
1,985
questions
0
votes
0
answers
45
views
Partition of a number as the sum of k integers, with repetitions but without counting permutations.
The Hardy-Littlewood circle method (with Vinogradov's improvement) states that given a set $A \subset \mathbb{N}\cup \left \{ 0 \right \} $ and given a natural number $n$, if we consider the sum:
$$f(...
6
votes
0
answers
215
views
The sequence $0, 0, 1, 1, 3, 10, 52, 459, 1271, 10094, 63133,...$
Let $a_0$ be a permutation on $\{1, 2, ...,N\}$ (i.e. $a_0 \in S_N$) . For $n \geq 0$:
If $a_n(i+1) \geq a_n(i)$, then $a_{n+1}(i) = a_n(i+1) - a_n(i)$.
Otherwise, $a_{n+1}(i) = a_n(i+1) + a_n(i)$.
$...
- 1,029
0
votes
0
answers
77
views
How to prove the following partition related identity?
So I want to show that the following is true, but Iam kidna stuck...
$$
\sum_{q_{1}=1}^{\infty}\sum_{q_{2}=q_{1}}^{\infty}\sum_{q_{3}=q_{1}}^{q_{2}}...\sum_{q_{k+1}=q_{1}}^{q_{k}}x^{q_{1}+q_{2}+...+q_{...
- 1
1
vote
0
answers
39
views
Counting solution to congruences
I want to count the $x, y \mod a$ and $r, s \mod b$ subject to the following conditions (defining $u, v, w, k$ which exist by the coprimality conditions)
$$(a, x, y) = 1$$
$$(b, r, s) = 1$$
$$ as+xr+...
- 1,285
2
votes
0
answers
111
views
On $s$-additive sequences
For a non-negative integer $s$, a strictly increasing sequence of positive integers $\{a_n\}$ is called $s$-additive if for $n>2s$, $a_n$ is the least integer exceeding $a_{n-1}$ which has ...
- 9,592
1
vote
0
answers
39
views
How to explain arithmetic form of surprising equality that connects derangement numbers to non-unity partitions?
$\mathbf{SETUP}$
By rephrasing the question of counting derangements from
"how many permutations are there with no fixed points?"
to
"how many permutations have cycle types that are non-...
1
vote
2
answers
102
views
Numbers in a Fixed Ratio with Same Multiset of Digits
Recently I'm thinking of a problem of “magic simplifying of fractions”. Specifically, we can simplify $\frac{19}{95}$ to $\frac{1}{5}$ as we can “factor” or “cancel” out the “9”. Now I am consider the ...
- 5,239
3
votes
3
answers
704
views
Is it true that $\sum_{k=0}^m\binom{n-k}k$ outputs the $(n+1)$th Fibonacci number, where $m=\frac{n-1}2$ for odd $n$ and $m=\frac n2$ for even $n$?
Does $$\sum_{k=0}^m\binom{n-k}k=F_{n+1}$$ where $m=\left\{\begin{matrix}
\frac{n-1}{2}, \text{for odd} \,n\\
\frac n2, \text{for even} \,n
\end{matrix}\right.$ hold for all positive integers $n$?
...
- 17k
1
vote
1
answer
1k
views
How to compute the Möbius function
I have no clue how to begin this problem. It involves computing the Möbius inversion function $\mu$. This problem comes from Stanley's $\textit{Enumerative Combinatorics}$, vol 1, problem 70, Chapter ...
- 23.1k
1
vote
1
answer
82
views
Percolative process distribution not equivalent to coupon collector problem distribution
I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...
- 159
2
votes
1
answer
31
views
Growth of the least $k$ such that $\sigma^k$ has a fixed point for each $\sigma\in S_n$
Let $f(n)$ be the least $k\in \mathbb{N}$ such that $\sigma^k$ has a fixed point for each permutation $\sigma\in S_n$. In light of the cycle decomposition of $\sigma$, $f(n)$ is the least $k\in \...
- 2,407
0
votes
0
answers
19
views
Estimate the order of restricted number partitions
There are $k$ integers $m_l,1\leq l\leq k
$(maybe negetive), satisfiying $|m_l|\leq M$ and $\sum_l m_l=s$.
I want to get an order estimate of the number of solutions for $k, M$ when fixing $s$.
I came ...
- 91
0
votes
0
answers
76
views
Applications, Generalisations and developments of Green-Tao Theorem after 2018
The well-known Green-Tao Theorem is definitely one of the most striking results among different area of Mathematics such as: Number Theory, Combinatorics, Graph Theory, Ergodic Theory,... etc.
https://...
- 2,508
0
votes
0
answers
23
views
An optimal order estimation problem for combinatorics background
def:
$\gamma(k)=\frac{\sqrt2^k}{\sqrt\pi}\Gamma(\frac{k+1}{2})$
$m_l$ are integers and $|m_l|<M$, $k_l$ are positive integer and $\sum_{l}k_l=k,\sum_{l}k_lm_l=s$.In other words, decompose $s$ into ...
- 91
2
votes
0
answers
127
views
Minimal sum of natural representatives of subgroup of $\mathbb{Z}_p^d$
Let $p$ be a prime and $U$ a subgroup of $\mathbb{Z}_p^d$ generated by $(a_1, \ldots, a_d) \in \mathbb{Z}_p^d$. Are there any theorems concerning the minimum of the sum of the natural representatives ...
- 21