All Questions
Tagged with combinatorics number-theory
1,983
questions
0
votes
0
answers
32
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 ...
- 111
0
votes
0
answers
33
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 ...
- 111
1
vote
1
answer
37
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/...
2
votes
0
answers
95
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$.
$$...
- 862
1
vote
1
answer
46
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 ...
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 $...
- 1,773
2
votes
1
answer
154
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 ...
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
38
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
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
1
vote
0
answers
38
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-...
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 ...
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,534
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 ...
- 111
2
votes
1
answer
30
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
75
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,498
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
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
0
answers
64
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
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 ...
6
votes
0
answers
82
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
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 ...
- 498
5
votes
1
answer
131
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,534
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,534
-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 ...
- 141
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 ...
- 702
1
vote
0
answers
321
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,352
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} \...
- 506
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
1
vote
0
answers
71
views
+50
$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 ...
- 558
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}|$ ...
- 1,581
0
votes
0
answers
49
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 ...
- 558
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,352
0
votes
1
answer
44
views
The Asymptotic formula of the generating function related with the partition of a positive integer
This question may be duplicate with this answer_1 and here I referred to the same paper by Hardy, G. H.; Ramanujan, S. referred to by wikipedia which is referred to in answer_1.
But here I focused on ...
- 416
2
votes
0
answers
39
views
AKS primality test lower bound
In this paper, in the first part of Section 7, D.J. Bernstein mentions that the original AKS paper (Lemma 4.4 and its proof) uses an extremely crude lower bound for the number of elements in $G$ (as ...
- 21
2
votes
1
answer
61
views
Counting gap sizes in a subfamily of partitions
Let $\mathcal{OD}$ be the set of all odd and distinct integer partitions. This has a generating function given by
$$\sum_{\lambda\vdash\mathcal{OD}}q^{\vert\lambda\vert}=\prod_{j\geq1}(1+q^{2j-1})$$
...
- 339
4
votes
0
answers
108
views
How many connected nonisomorphic graphs of N vertices given certain edge constraints?
Background:
I’m helping a colleague with a theoretical problem in ecology, and I haven’t quite the background to solve this myself. However, I can state the problem clearly, I think:
Problem statement:...
- 341
2
votes
1
answer
96
views
Show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs
I am trying to show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs. I'm pretty sure this is true but I don't see how to prove it. There is no obvious way to use induction.
Here is an example:
$...
- 3,187
2
votes
1
answer
204
views
Generalization of binomial coefficients to both non-integer arguments
It is known that binomial coefficients can be generalized to the following: for $s\in\mathbb R$ and $k\in\mathbb N$,
\begin{equation*}
\binom{s}{k} := \prod_{i=0}^{k-1} \frac{s-i}{k-i} = \frac{s(s-1)...
- 1,972
1
vote
0
answers
24
views
Notation for $k$-partitions of $n$ containing at least one summand equal to $s$
I am looking for whether there is any notation for the $k$-partition number of $n$ where the partitions must include some summand $s$.
An example of the kind of notation I am looking for is $P_k^s(n)$....
- 1,129
0
votes
0
answers
36
views
Show explicitly the rank-24 Leech lattice that is also symmetric unimodular matrix with integer entries?
A typical $E_8$ lattice is of the form of $E_8$ Cartan matrix:
$$\begin{pmatrix}
2 &−1 &0 &0& 0& 0& 0& 0\\
−1& 2 &−1& 0& 0& 0& 0& 0\\
0& −1&...
- 191
1
vote
0
answers
58
views
Exploring a Novel Pattern in Exponential Number Sequences and Their Relation to Factorials
Introduction
I've been exploring a concept in mathematics that I've termed "string math," which involves examining patterns in exponential number sequences and their intriguing connection to ...
- 11
0
votes
0
answers
48
views
Optimal Strategy for Identifying Lighter Balls: A Balance Scale Puzzle
There are n balls, among which m balls are lighter (and equally light with each other). We have a balance scale; how many times must we weigh at least, in order to find these m lighter balls? We ...
0
votes
0
answers
38
views
Schnirelmann density and bases of finite order
Let $\mathcal{A}$ be an additive set. We know that if the Schnirelmann density $\sigma_{\mathcal{A}}$ is positive then it is a basis of finite order. But it it not a necessary condition. My question ...
user1232857
3
votes
1
answer
87
views
Is there a smallest large set?
A set $A = \{a_1, a_2 ,..\}$ of positive integers is called large if $\frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + ...$ diverges. A small set is any set of the positive integers that is not large
...
- 702