All Questions
Tagged with combinatorics number-theory
1,985
questions
0
votes
0
answers
33
views
Prove that for $n$ sufficiently large and $k \leq n$, there exists $m$ having exactly $k$ divisors $\le n$
Prove that for all sufficiently large positive integers $n$ and a positive integer $k \leq n$, there exists a positive integer $m$ having exactly $k$ divisors in the set $\{1,2, \ldots, n\}$.
here is ...
- 39.7k
12
votes
1
answer
2k
views
Partitioning sets such that the sum of 2 elements is Prime
Given an $n >0$ is it possible to partition the set $\mathcal{P} = \{1,2, \cdots, 2n\}$ into $n$ pairs $(a_{i},b_{i})$ such that $a_{i} + b_{i}$ is a prime?
- 182
0
votes
0
answers
35
views
Average cluster size of a nxn matrix
I asked a question about the cluster size inside a vector here. As a result, I finally used the expression $\frac{n}{-k+n+1}$ as the average cluster size, although it´s not proved correct for every ...
- 159
0
votes
0
answers
49
views
Mean of probability distribution
I have a probability distribution defined by the following density function:
$f(k,j,n,m)=\frac{(m n)! \mathcal{S}_k^{(j)}}{(m n)^k (m n-j)!}$ (With $\mathcal{S}_k^{(j)}$ being the Stirling number of ...
- 159
1
vote
0
answers
112
views
$q$-Pochhammer at root of unity
Are there any identities, papers/studies, posts, etc that go over
$$(\ln\zeta_n^k;q)_{\infty} = \prod_{m=0}^{\infty}(1-\frac{2\pi i k q^m}{n})$$
which is sometimes called the $q$-Pochhammer or quantum ...
- 702
1
vote
0
answers
39
views
Counting matrix paths for (n,m>2) matrices
Given a $n\times m$ matrix with $k$ elements inside it, I need to calculate the number of arrangements of those $k$ elements that form at least 1 path from the top to bottom matrix row composed of the ...
- 159
2
votes
0
answers
97
views
Fractional part of a sum
Define for $n\in\mathbb{N}$ $$S_n=\sum_{r=0}^{n}\binom{n}{r}^2\left(\sum_{k=1}^{n+r}\frac{1}{k^5}\right)$$
I need to find $\{S_n\}$ for $n$ large where $\{x\}$ denotes the fractional part of $x$.
$$...
- 27
1
vote
1
answer
38
views
Summation of n-simplex numbers
Gauss proved that every positive integer is a sum of at most three triangular(2-simplex) numbers. I was thinking of an extension related to n-simplex.
Refer: https://upload.wikimedia.org/wikipedia/...
- 181k
17
votes
2
answers
942
views
Cut a number to a random integer between 0 and that number. Keep going until that number is 0. How many cuts do we need?
Start with an integer like n = 100 and set it equal to a uniformaly random integer between [0,n] inclusive. Keep cutting it this way until n = 0. What's the expected value of the number of cuts needed?...
- 29.8k
1
vote
1
answer
49
views
Generating function of partitions of $n$ in $k$ prime parts.
I have been looking for the function that generates the partitions of $n$ into $k$ parts of prime numbers (let's call it $Pi_k(n)$). For example: $Pi_3(9)=2$, since $9=5+2+2$ and $9=3+3+3$.
I know ...
- 47.4k
2
votes
1
answer
155
views
About the product $\prod_{k=1}^n (1-x^k)$
In this question asked by S. Huntsman, he asks about an expression for the product:
$$\prod_{k=1}^n (1-x^k)$$
Where the first answer made by Mariano Suárez-Álvarez states that given the Pentagonal ...
- 15.8k
0
votes
0
answers
82
views
The n-th number open problems
Some open problems in mathematics boil down to the question of defining the $n$-th term of a certain sequence for a specific $n$. For instance, the value of the $5$-th diagonal Ramsey number and the $...
- 583
4
votes
4
answers
814
views
Counting numbers smaller than $N$ with exactly $k$ *distinct* prime factors
Using common notation, $\omega(n)$ is the number of distinct prime factors on $n$. Similiarly, $\Omega(n)$ is the number of prime factors of $n$, not necessarily distinct: $120=2^{3}\cdot 3 \cdot 5$ , ...
2
votes
2
answers
60
views
Regarding scaling in sumsets
Let $A$ be a finite subset of $\mathbb{N}$. We denote the set $\{a_1 +a_2: a_1, a_2\in A\}$ as $2A$. We call the quantity $\sigma[A]:= |2A|/|A|$ as the doubling constant of $A$, and this constant can ...
- 971
3
votes
1
answer
84
views
For which integers $m$ does an infinite string of characters $S = c_{1} \cdot c_{2} \cdot c_{3} \cdot c_{4} \cdot c_{5} \ldots$ exist
Question:
For which integers $m$ does an infinite string of characters
$$S = c_{1} \cdot c_{2} \cdot c_{3} \cdot c_{4} \cdot c_{5} \ldots$$
exist such that for all $n \in \mathbb{Z}_{>0}$ there are ...
- 432k
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
1
vote
0
answers
65
views
A question on generalized bases
I just came to know that it is possible to define a generalized base as an infinite sequence of natural numbers $\mathbf b=(b_1,b_2,\dots)$ where $b_i\ge 2$ for all $i$. With this definition, any $m\...
0
votes
0
answers
76
views
Let $f$ satisfy $f(mr)<f(r)$ for all $m,r\in \mathbb N$. Is $f(k)$ decreasing for all large $k$?
Consider the question
Let $f:\mathbb N \to \mathbb R$ satisfy $f(mr)<f(r)$ for all $m,r\in \mathbb N$, $m>1$. Is $f(k)$ decreasing for all $k>k_0$ for some $k_0$?
The answer is clearly no ...
1
vote
2
answers
522
views
Closed Formula Expression for Sum of Combinatorics
I have recently been interested in the problem of summing Combinatorials. I have been beating my brain for the past days to figure out how to find an explicit closed form of:
$n \choose 0 $+$ n \...
- 54.3k
0
votes
0
answers
22
views
Exploring the Intersection of Expander Graphs, Number Theory, Representation Theory and Recent Computer Science Developments
I have a solid understanding of the basics of expander graphs and their properties and the recent development of High-Dimensional Expanders and their application to Random Walks, along with other ...
30
votes
5
answers
5k
views
When the product of dice rolls yields a square
Succinct Question:
Suppose you roll a fair six-sided die $n$ times.
What is the probability that the product of the rolls is a square?
Context:
I used this as one question in a course for elementary ...
- 239k
6
votes
0
answers
83
views
how many natural numbers require at least 6 terms to express as the sum of distinct squares?
I wrote a computer program as an exercise in dynamic programming. It finds the minimum number of distinct squares which sum to some positive target integer n. I found something interesting and would ...
- 261
8
votes
1
answer
263
views
Existence of a Subset $S$ of $\mathbb{N}$ Where All but Finitely Many Natural Numbers Are Sums of Consecutive Elements of $S$
I am pondering a question in number theory that touches upon the representation of natural numbers as sums of consecutive elements from a subset S of $\mathbb{N}$. Specifically, the question is:
Does ...
- 93.3k
3
votes
1
answer
121
views
How many $k$-full numbers are there?
Recall that $n\in\mathbb{N}$ is $k$-full if, for a prime number $p$ : $p\mid n$ implies $p^{k}\mid n$. In the paper I am currently reading it is said that there are $O(B^{1/k})$ $k$-full positive ...
- 78.4k
3
votes
0
answers
90
views
On thickness of binary polynomials
OEIS A169945 introduces the concept of thickness of a polynomial as the magnitude of the largest coefficient in the expansion of the square of the polynomial. Considering the $2^{n+1}$ polynomials $p(...
- 9,592
5
votes
1
answer
132
views
Number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$
I was wondering about sets that do not contain any $3$-term AP, and came to know that the official name of such a set is Salem–Spencer set. I was considering the question of counting the number of ...
- 9,080
1
vote
1
answer
255
views
Quadratic Nimber Equation
I'd like to ask how to solve the quadratic nimber equation $x\otimes x \oplus b \otimes x \oplus c=0$, where $\otimes$ is nim multiplication and $\oplus$ is nim addition.
- 78.4k
5
votes
1
answer
205
views
Conjecture: $\binom{n}{k } \mod m =0$ for all $k=1,2,3,\dots,n-1$ only when $m $ is a prime number and $n$ is a power of $m$
While playing with Pascal's triangle, I observed that $\binom{4}{k } \mod 2 =0$ for $k=1,2,3$,and $\binom{8}{k } \mod 2 =0$ for $k=1,2,3,4,5,6,7$ This made me curious about the values of $n>1$ and ...
- 6,565
-1
votes
1
answer
70
views
Non negative integral solutions when coefficients are involved and inequality among parameters
What is the number of non negative integral solutions of
$5w+3x+y+z=100$, such that $w≤x≤y≤z$.
I have the answer key to this but I do not understand how to even start. The second inequality condition ...
- 42.8k
1
vote
0
answers
323
views
A conjecture on representing $\sum\limits_{k=0} ^m (-1)^ka^{m-k}b^k$ as sum of powers of $(a+b)$.
UPATE: I asked this question on MO here.
I was solving problem 1.2.52 in "An introduction to the theory of numbers by by Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery"
Show that if ...
- 6,565
1
vote
1
answer
66
views
Sum-free sequence but multiset
The question is:
Show that if $S$ is a set of natural numbers such that no number in S can be expressed as a sum of other (not necessarily distinct) numbers in S, then $\sum_{ s \in S} \frac{1}{s} \...
- 70.4k
0
votes
0
answers
48
views
Find generating series on set of descending sequences, with weight function as taking sum of sequence
Given the set of all sequences of length k with descending (not strictly, so $3,3,2,1,0$ is allowed) terms of natural numbers (including $0$), $S_k$, and the weight function $w(x)$ as taking the sum ...
- 183
0
votes
0
answers
65
views
Given an integer $n>0$, $\forall 0<k\le n$, the total factor $2$ does the sequence contain?
For example,
if $n=2$, we have a sequence: $1,2$, where $2$ has one factor $2$, so the counting function: $\phi(2)=1$
if $n=4$, we have a sequence: $1,2,3,4$, where $4=2\cdot2$ has two factor $2$, so ...
- 21.2k
51
votes
1
answer
1k
views
How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?
For the numbers $1, \ldots, N$, how many ways can I arrange them such that either:
The number at $i$ is evenly divisible by $i$, or
$i$ is evenly divisible by the number at $i$.
Example: for $N = 2$,...
- 1,745
2
votes
1
answer
104
views
power of a matrix that has a very "big" entry on a column
Given a matrix $A = (a_{i,j}) \in \mathbb{Z}^{n,n} $. We say the entry $a_{r,k} $ on the $k$-th column is big if $a_{r,k} > \frac{1}{2} \sum_{i=1}^n\left|a_{i,k}\right| + 1$ (so that $|a_{r,k}|$ ...
- 227
0
votes
0
answers
50
views
Higher dimensional polygonal numbers formula
The general formula for the $m$-th $n$-gonal number is given by
$$P_n(m) = \frac{m^2(n-2)-m(n-4)}{2}$$
So, to give quick examples:
Triangular numbers ($n=3$):
$$P_3(m) = \frac{m^2+m}{2}$$
Square ...
- 61.5k