All Questions
Tagged with combinatorics number-theory
1,985
questions
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
5
votes
5
answers
14k
views
How many odd three-digits numbers are there whose all three digits are different
I faced this problem on one test. I wrote my solution but then I found out that my solution is wrong, I still cannot find where my mistake is.
The problem says: How many three-digits numbers are ...
- 226
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 ...
- 39.7k
2
votes
2
answers
500
views
Finding distinct integer solutions to $x_1 + x_2 + ...+ x_r = n$
How many different (distinct $x_i$) non-negative integer solutions does the equation $x_1 + x_2 + ...+ x_r = n$ have?
We know that it has $n+r-1 \choose r-1$ non negative solutions. But how many are ...
- 11
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
2
answers
705
views
Upper bound for the strict partition on K summands
In number theory and combinatorics, a partition of a positive integer $n$, also called an integer partition, is a way of writing $n$ as a sum of positive integers. Partitions into distinct parts are ...
- 191
8
votes
2
answers
697
views
How many numbers of length N(N is the number of digits) are possible
Given $N \le 10^9$, determine how many numbers of length $N$ are possible with the following constraint: the adjacent digits of the number should have an absolute difference of $1$.
For eg, for $N = ...
- 10.3k
2
votes
1
answer
221
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)...
- 40.1k
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})$$
...
- 62.3k
4
votes
0
answers
109
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
97
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:
$...
- 324