All Questions
Tagged with combinatorics number-theory
1,985
questions
3
votes
1
answer
75
views
If $1 \leq x_i \leq n$ and $k < n $ what is the value of $\sum_{x_1,x_2,\cdots, x_k \; | \; \sum^k_{i = 1} x_i = n} \sum_{i < j} x_i x_j $
Given positive integers $n$ and $k$ such that $1<k<n$, let $S(n,k)$ be the set of postiive integer $k$-tuples $(x_1,\dots,x_k)$ for which $\displaystyle\sum^k_{i = 1} x_i = n$. For example, $S(5,...
- 131
7
votes
2
answers
443
views
Explicit formula for tournament sequence
I am looking for an explicit formula for a sequence. The sequence is generated as follows:
There is a tournament with $10$ teams. In the beginning, all teams have a 0-0 win-loss record. The teams are ...
- 171
1
vote
0
answers
37
views
Find all ordered triples of non-negative integers $(a,b,c)$ such that $2^a + 2^b = c!$. [duplicate]
Find all ordered triples of non-negative integers $(a,b,c)$ such that $2^a + 2^b = c!$.
Here from the equation we have that if $a \le b$, then we have $2^a(1+2^{b-a}) = c!$, which implies that $2^a$ ...
- 399
3
votes
0
answers
333
views
Unsolved problems for partition function
In number theory, the partition function $p(n)$ represents the number of possible partitions of a non-negative integer $n$. For instance, $p(4) = 5$ because the integer $4$ has the five partitions $1 +...
- 907
0
votes
1
answer
102
views
Subarray Sum Equals K - If the same prefix sum is encountered why does it follow 1,3,7,15,31 pattern?
This is an interesting property I have noticed in the problem:
Subarray Sum Equals K
The basic algorithm is as follows:
You start with calculating the prefix (running sum).
You check if the ...
- 1,035
5
votes
2
answers
262
views
Shading the entire $i$-th row and $j$-th column of an $m\times n$ grid when $\gcd(i,m)>1$ and $\gcd(j,n)>1$, how many grids leave $x$ cells unshaded?
Is there a way of cleverly counting the following scenario?
Given an $m\times n$ grid, with $m$ and $n$ relatively prime, imagine shading a subset of the squares of an $m\times n$ grid using this ...
- 1,755
-1
votes
1
answer
118
views
Count number of solution to Diophantine equation $k_1a^2+k_2ab+k_3b^2-k_4c^2=0$
I am looking to count number of solutions of diophantine equation $k_1a^2+k_2ab+k_3b^2-k_4c^2=0$.
such that $ 1 \le a, b, c \le N$ and $gcd(a, b) = 1$
and $k_1,k_2,k_3,k_4$ are positive constant ...
- 470
0
votes
0
answers
100
views
Show that $2n\choose n$ divisible by primes $p,$ such that $n<p<2n$? [duplicate]
Suppose on the contrary that $2n \choose n$ is not divisible by $p\in (n,2n)$. There exis $k$ and $0\ne r\lt p$ such that
$(2n)\cdots (n+1)=kp \,n!+r \, n!$. The second term on RHS is not divisible by ...
- 11.5k
0
votes
1
answer
175
views
How many compositions of $n$ into distinct $k$ parts are there
Let $n, k$ be a non-negative integers with $k\leq n$. A $k$-composition or a composition of $n$ into $k$ parts is a $k$-tuple $(x_1, ..., x_k)$ such that $x_1+x_2+...+x_k = n$. I know that the number ...
- 157
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?...
- 397
2
votes
0
answers
69
views
Guessing algebraic number by its binary digits
Positive integers $d$, $H$ are given. It's known that $r\in(0,1)$ is such that $p(r)=0$ for some nonzero $p\in\mathbb Z[x]$ with $\deg p\leq d$ and coefficients $c_i$, such that $|c_i|\le H$, $i=0,\...
- 235
3
votes
2
answers
319
views
Number of grid points satisfying the triangle inequality
Background: The following questions arise from the Wigner $3j$ symbol, see here. It is well known that the angular momenta $(j_1,j_2,j_3)$ in the Wigner $3j$ symbol must satisfy the triangle ...
- 520
6
votes
0
answers
175
views
When are the partition numbers squares?
I'm unsure if this question is even interesting. I am playing around with partition numbers $p(n) :=$ # partitions of $n$, and I noticed that $p(n)$ never really is a square number, except for of ...
- 1,769
3
votes
1
answer
99
views
How many different products can we get using the first n natural number?
Let $U=\{1,2,3,...,n\}$ and $s$ to be an non-empty subset of $U$, let $prod$ be a function on set to calculate the product of all elements in a set.
My question is, what is the number of elements in $\...
- 31
2
votes
1
answer
339
views
Behrend's construction on large 3-AP-free set
Theorem (Behrend's construction)
There exists a constant $C>0$ such that for every positive integer
$N$, there exists a $3$-AP-free $A\subseteq[N]$ with $|A|\geq
Ne^{-C\sqrt{\log N}}$.
Proof. Let $...
- 17k
1
vote
1
answer
244
views
Farkas' lemma for variables in the natural numbers
A lot of questions regarding the Farkas' lemma has already been done here. Most of them seems to be related to consequences of the Farkas' lemma, for example, see [1, 2, 3]. This means that the ...
- 842
1
vote
1
answer
159
views
Deza-Frankl-Singhi theorem
Let $p$ be a prime number and $A$ b a system of $(2p-1)$ element subsets of of an $n$-element set such that no two sets in $A$ intersect in precisely $p-1$ elements. I would like to prove that
$$|A|\...
- 319
2
votes
1
answer
64
views
shifted set of residue classes hitting intervals of length p/k Alon and Spencer problem 4.8.6
I am working on the problem 4.8.6 from Alon and Spencer and I am completely stuck. The problem is the following:
We have a set $X$ of at least $4k^2$ residue classes modulo a prime $p$. We want to ...
- 433
1
vote
0
answers
36
views
generator of the lattice $L\subset \Bbb{C}$
Let $L\subset \Bbb{C}$ be a lattice, assume there is a $\gamma \in \Bbb{C}$ such that $\gamma L = L$, prove the following two facts:
(1) $\gamma$ must be roots of unity
(2) if $\gamma$ is not real, ...
- 4,940
2
votes
1
answer
83
views
Is the set of permuted digits countable
I wish to know whether it the following set is countable:
The set of all numbers with decimal expansions which simply permute the digits $\{0,1,2,...,9\}$
To put it more formally: a digit $x = 0....
- 147
2
votes
1
answer
153
views
Is there a formula for determining the number of a positive integer's factorizations (multiplicative partitions)?
The "factorization" in the question means "multiplicative partition", so the factors can be 1 or composite numbers.
To make things simple, let $f(n, 3)$ be the number of positive ...
5
votes
1
answer
208
views
If you write down all the numbers from 1 to n, how many digits would you have written down?
I've seen the question for numbers like 50, 100 or 1000, but not for $n$. Although I found a formula that might be the answer, but I don't know the name of it or the proof for it. I couldn't find it ...
- 161
3
votes
1
answer
88
views
relation between prime number and given recurrence relation
I have run into a question today. However , i stuck in it. I hope to find any help here. My question is the following
Let define a recurrence relation $\{b_n\}_0^{\infty}$ such that $b_{n+1}=2b_{n}+1$...
user1120825
0
votes
1
answer
311
views
Partitions of a number for a fixed number of integers
Is there a name for the number of ways to write a positive integer $n$ as a sum of $k$ integers, including 0?
For example, the number 4 can be written as the sum of 3 numbers in the following ways:
4+...
- 1,620
0
votes
0
answers
31
views
The Smallest non zero binomial coefficient of n over a modulo prime p .
Let $p$ be a prime, $n \in \mathbb{N}$ and let $m$ be the largest integer such that $p^m$ divides $n$. Then , the smallest $j\geq1$ such that $\binom{n}{j}$ is non zero modulo $p$, is $j=p^m$.
No idea ...
1
vote
0
answers
28
views
Reduce summation to expression [duplicate]
I am working on a probability problem and ran across the following sum...
$$ \sum_{i=1}^{k} {n-i\choose r} $$
where $k$ is some arbitrary positive integer such that $k \le n-r-1$.
is there a simple, ...
- 6,099
6
votes
0
answers
121
views
Count number of ways to distribute n distinct positive integers into $r$ identical bins such that the product of integers in each bin is $\le M$
Problem Statement:
We have $n$ distinct positive integers say $a_1,a_2....a_n$ and a given integer value $M$.
We have to count number of ways to distribute these integers to $r$ identical bins subject ...
user1068604
2
votes
0
answers
157
views
Who wins in this simple "factoring game" depending on the starting number?
There is a given $N$ written on a board. Two players, Alice and Bob choose a number from the board and factorize that number to $N=XY$ where $\gcd(X,Y)\neq1$, then erase $N$ and write $X, Y$ on the ...
- 742
1
vote
1
answer
141
views
The number of distinct powers of x that appear in the expansion of $(x^{7}+x^{11}+x^{14})^{10}$ is
The number of distinct powers of x that appear in the expansion of
$(x^{7}+x^{11}+x^{14})^{10}$ is
Let the power of $x^7$ is a, $x^{11}$ is b and $x^{14}$ is c
then by multinomial a+b+c=10
so we have ...
0
votes
0
answers
84
views
Consider the increasing list of positive integers that do not contain the digit zero, 1, 2, 3... 9, 11, 12,.... The 2022nd number in this sequence is
Consider the increasing list of positive integers that do not contain the digit zero, $1, 2, 3, \ldots, 9, 11, 12, \ldots$. The $2022$nd number in this sequence is
so the number of single-digit ...