All Questions
Tagged with enumerative-combinatorics nt.number-theory
53 questions
1
vote
0
answers
108
views
Asymptotics for sums of two sets of positive integers
Assume that $A$ and $B$ are subsets of $\mathbb N$, with counting functions verifying $A(x)\gg x^\alpha$ and $B(x)\gg x^\beta$, with $\alpha+\beta<1$. Let $C=A+B$ and $C(x)$ its counting function.
...
- 423
4
votes
1
answer
409
views
On the parity of the sum $\sum_{1\le j<k\le p-1\atop p\nmid aj^2+bjk+ck^2}(aj^2+bjk+ck^2)$
QUESTION. Let $p$ be an odd prime and let $a,b,c\in\mathbb Z$. How to determine the parity of the sum
$$S_p(a,b,c)=\sum_{1\le j<k\le p-1\atop p\nmid aj^2+bjk+ck^2}(aj^2+bjk+ck^2)$$
in terms of $a,b,...
- 15.6k
-3
votes
1
answer
116
views
Enumerative number theory term searching [closed]
Given $a,b$ positive numbers such that $gcd(a,b)=1$.Prove that there are infinitely many $n$ positive integers such that $x_n=a+nb$ sequence has many terms such that it is not divisible by any prime'...
5
votes
0
answers
307
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 ...
- 791
3
votes
3
answers
756
views
Ordinary partitions vs partitions into odd parts
Let $\mathcal{P}(n)$ be the set of all unrestricted partitions of $n$ while $\mathcal{O}(n)$ stand for the set of all partitions of $n$ into odd parts. We adopt the power notation for partitions $\...
- 43.1k
0
votes
1
answer
346
views
A combinatorial proof: where art thou?
Start by introducing the finite sums
$$A_n:=\sum_{m=1}^nq^m\prod_{j=1}^{m-1}(1-q^j) \qquad \text{and} \qquad
B_n:=\sum_{m=1}^nq^m\prod_{j=m+1}^n(1-q^j).$$
An algebraic proof is facile: Clearly, $A_1=...
- 43.1k
4
votes
0
answers
211
views
Sum $f(n_1,n_2,\ldots,n_k) 1^{n_1} 2^{n_2} \ldots k^{n_k}$ over partitions
Use the notation $(n_1,n_2,\ldots,n_k) \vdash n$ to denote that $(n_1,n_2,\ldots,n_k)$ is a partition of the positive integer $n$, that is, $n_1+n_2+\ldots+n_k = n$ and $n_1 \ge n_2 \ge \ldots \ge n_k ...
- 261
4
votes
0
answers
97
views
"Convolving" a general Catalan with classical Catalan
Consider what is sometimes known as generalized Catalan sequence
$$\mathcal{{\color{red}C}}_{a,b}:=\frac{2b+1}{a+b+1}\binom{2a}{a+b}.$$
Observe that $\mathcal{{\color{red}C}}_{n,0}$ reduces to the ...
- 43.1k
2
votes
1
answer
232
views
Proof of a binomial identity
Computations with Maple suggest the following binomial identity
\begin{equation*}
\forall{p,j}: \sum_{k=j+1}^{p+1} (-1)^j \dfrac{1}{k}\binom{k-1}{j} =
\sum_{k=j+1}^{p+1} (-1)^{k-1} \dfrac{1}{...
- 1,020
8
votes
2
answers
528
views
Number of matrices with unit determinant and fixed sum of elements
Question. Let $\mathcal{M}_3$ be the set of $3\times 3$ matrices with non-negative integer entries and unit determinant. What is the number of $M\in \mathcal{M}_3$ with fixed sum of entries? What is ...
- 577
7
votes
2
answers
843
views
Decomposition of a natural number as sum of positive integers
Let $n \in \mathbb{N}$ be a positive natural number and denote by $f(n)$ the number of decompositions of $n$ of the form $n = a+b+c+d$ where $a,b,c,d > 0$ are also positive natural numbers such ...
- 8,998
2
votes
0
answers
177
views
Existence of fully supported element in a finite-dimensional vector space over $\mathbb{F}_p$ (and in finite abelian groups)
Let $V$ be an $n$-dimensional vector space over $\mathbb{F} = \mathbb{Z} / (p)$, the field of $p$ elements, $p$ a prime, with $\{v_1, \dotsc, v_n \}$ a basis for $V$. An element $x \in V$ is called &...
- 191
3
votes
0
answers
115
views
Counting monomials modulo prime numbers
The present quest emanates from this study by R. Stanley, including his recent MO question. Define the product (polynomials after full expansion)
$$I_n(x)=\prod_{i=1}^n(1+x^{F_{i+1}})$$
based on the ...
- 43.1k
3
votes
1
answer
226
views
Sums over permutations relates to permutations?
Consider the permutation group $\mathfrak{S}_n$ on $n$ letters $\{1,2,\dots,n\}$. Let $\iota=(1,2,3,\dots,n)\in\mathfrak{S}_n$ be the identity permutation in a $1$-line notation. Given $\pi, \rho\in\...
- 43.1k
4
votes
1
answer
263
views
A refinment of Beck's conjecture
Let $\mathcal{O}(n)$ and $\mathcal{D}(n)$ denote the set of all integer partitions of $n$ into odd parts and distinct parts, respectively. Let $o(n)=\#\mathcal{O}(n)$ and $d(n)=\#\mathcal{D}(n)$. ...
- 43.1k
2
votes
3
answers
742
views
Asking for a proof for a sum of products of binomials: an "interesting" identity?
The following identity must have received alternative proofs, including a combinatorial argument by David Callan as found at Bijections for the Identity $4^n = \sum_{k = 0}^n \binom{2k}k\binom{2(n - k)...
- 43.1k
12
votes
1
answer
405
views
Looking for a "clever" argument for a $q$-series identity
Consider the below $q$-series identity. One of the things I like about this expansion is how nicely the difference on the left hand side factors to the right hand side of the equation.
$$\prod_{k\geq1}...
- 43.1k
1
vote
0
answers
203
views
Generalizing "partition into odd parts=partition into distinct parts"?
The number of partitions into distinct parts is known to agree with the number of partitions with odd parts. For instance, this follows from
$$\prod_{k=1}^{\infty}(1+q^k)=\prod_{n=1}^{\infty}\frac1{1-...
- 43.1k
9
votes
2
answers
1k
views
Extracting constant terms: is there a direct way?
$\DeclareMathOperator\CT{CT}$
Let $\CT_t(f(t))$ denote the constant term of the Laurent polynomial of $f(t)$.
Define the two functions $F(x_1,\dots,x_n)$ and $G(y)$ by
$$F:=\prod_{i=1}^nx_i^{-1}(1-x_i)...
- 43.1k
6
votes
1
answer
281
views
Another generalization of parity of Catalan numbers
Recently, a question by T. Amdeberhan gathered up many enjoyable proofs that a Catalan number $C_n$ is odd if and only if $n=2^r-1$.
Noam D. Elkies' answer considered $F=\sum_{n=0}^\infty C_n x^{n+1}$....
- 524
15
votes
4
answers
3k
views
Collecting alternative proofs for the oddity of Catalan
Consider the ubiquitous Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$. In this post, I am looking for your help in my attempt to collect alternative proofs of the following fact: $C_n$ is odd if and ...
- 43.1k
13
votes
2
answers
803
views
Two interpretations of a sequence: an opportunity for combinatorics
The sequence that is addressed here is resourced from the most useful site OEIS, listed as A014153, with a generating function
$$\frac1{(1-x)^2}\prod_{k=1}^{\infty}\frac1{1-x^k}.$$
In particular, look ...
- 43.1k
4
votes
1
answer
298
views
Enumeration of dominated Dyck paths
Using horizontal steps $(1,0)$ and vertical steps $(0,-1)$, consider the lattice paths starting from $(0,q)$ and reaching $(p,0)$ with $p$ horizontal and $q$ vertical steps. The set of such paths $\...
- 43.1k
1
vote
1
answer
209
views
Number of paths to a specific vertex in the Young's lattice
Consider the Young's lattice. What is the number of paths starting from the origin (0) to a specific Young diagram?
For instance, the Young diagram corresponding to the integer partition 1+1+1 has 1 ...
- 153
0
votes
0
answers
171
views
Total sum of characters over partitions with distinct parts
In my earlier quest, we looked at $\chi_{\mu}^{\lambda}=$value of an irreducible character of the symmetric group $\frak{S}_n$, where $\mu$ and $\lambda$ are (unrestricted) partitions of $n$. Then, ...
- 43.1k
4
votes
1
answer
698
views
Total sum of characters of the symmetric group $\frak{S}_n$
Let $\chi_{\mu}^{\lambda}$ denote a value of an irreducible character of the symmetric group $\frak{S}_n$, where $\mu, \lambda\vdash n$. When $\mu=(n)$, then it's known that
$$\sum_{\lambda\vdash n}\...
- 43.1k
7
votes
0
answers
183
views
Explaining $\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(a^i-1\right)$ by a free $S_n$-action
Here is an olympiad-level problem on elementary number theory:
Let $a$ be an integer and $n$ a positive integer. Prove that
\begin{align}
\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(...
- 33.8k
3
votes
0
answers
254
views
Enumerating multi-core binary partitions
An integer partition $\lambda$ of $n$ is called a binary partition provided that its parts are powers of $2$ (dyadic). Example: Let $n=3$. The binary partitions are $\lambda=(2,1)$ and $\lambda=(1,1)$ ...
- 43.1k
2
votes
0
answers
290
views
Can ${2n \choose n}$ ever be divisble by $2n+1$ (for positive integer $n$)?
The question in the title arose from some semi-recreational number theory. A quick check on a spreadsheet shows the answer is negative for $1\leq n \leq 20$; I haven't tried to use any more serious ...
- 25.8k
6
votes
1
answer
242
views
$(q,t)$-Fibonacci polynomials: area & bounce statistics
This is related to my earlier (unanswered) MO post. Preserve notations from there.
We take advantage of the one-to-one correspondence between the $(s,s+1)$-core partitions and $(s,s+1)$-Dyck paths. ...
- 43.1k
3
votes
0
answers
258
views
Partitions of n into k distinct parts which are multiples of given numbers
Is there anything known about the number of partitions of an integer $n$ into $k$ distinct parts in the following way?
Let $a_1,\dotsc,a_k\geqslant1$ be given integers. In how many ways can we write $...
- 539
4
votes
1
answer
423
views
Identity involving binomial coefficients and partitions
Working on a problem in the symmetric group I have stumbled upon the following equation:
$$\sum_{\substack{\pi=(1^{c_1},2^{c_2},\ldots,n^{c_n})\\\textrm{partition of }n}}(-1)^{n-\sum_{i=1}^nc_i}\frac{...
- 934
18
votes
2
answers
991
views
A conjecture harmonic numbers
I will outlay a few observations applying to the harmonic numbers that may be interesting to prove (if it hasn't already been proven).
From the Online Encyclopedia of Positive Integers we have:
$a(n)$ ...
- 181
1
vote
1
answer
394
views
Integer partitions into restricted parts
Given a linear diophantine equation $$x_1+\dots+x_n=m\leq nn'$$ how many solutions does it have with each $x_i\in[0,n']\cap\mathbb Z$? Looking for asymptotics that parametrizes well with both $n$ and $...
- 1,826
6
votes
4
answers
627
views
Request for an exact formula related to a partition in number theory
The Frobenius equation is the Diophantine equation $$
a_1 x_1+\dots+a_n x_n=b,$$
where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$
must consist of non-...
- 10.5k
4
votes
0
answers
274
views
What arithmetic would you do in parallel?
This is a post asking for references, and soliciting problems and people interested in accelerated computing. I will add the big-list tag and make it community-wiki. If this interests you strongly, ...
12
votes
0
answers
642
views
Wilf's conjecture: complementary Bell numbers
The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....
- 43.1k
5
votes
0
answers
175
views
A close cousin of involutions?
If $\mathfrak{S}_n$ denotes the permutation group on $n$ letters, then $Inv(n)=\{\pi: \pi^2=1\}\subset\mathfrak{S}_n$ is the set of involutions or
self-inverse permutations. The latter is enumerated ...
- 43.1k
2
votes
2
answers
168
views
Existence of 3-distributed subsets
Denote $[n]=\{1,2,\dots,n\}$. Assume $n\geq2$.
Question. Is it true that given any $S_1,S_2,\dots,S_{2n}$ (repetition allowed) subsets of $[2n]$ with $a\in S_a$ and $\# S_a=n$ for all $1\leq a\leq ...
- 43.1k
11
votes
1
answer
330
views
a Hankel matrix of involution numbers
Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. I always enjoy these numbers. Of course, here is yet another cute experimental finding for which I ask validity. ...
- 43.1k
7
votes
0
answers
124
views
in search of intepretations and connections for $k$-central binomials
Fix a positive integer $k$. Then, the sequences
$$c(n,k)=\frac{k^n}{n!}\prod_{m=1}^{n-1}(1+km)=[x^n]\left(\frac1{1-k^2x}\right)^{1/k}$$
are referred to as "$k$-central binomial coefficients",...
- 43.1k
13
votes
2
answers
1k
views
an identity for a sum over partitions
Write an integer partition $\lambda\vdash n$ in two different ways:
(1) $\lambda=\lambda_1\geq\lambda_2\geq\lambda_3\cdots\geq\lambda_k\geq1$
(2) $\lambda=1^{m_1}2^{m_2}3^{m_3}\cdots n^{m_n}$ for ...
- 43.1k
2
votes
1
answer
238
views
"flavored" equivalence classes of permutations
We say two permutations $\pi_1$ and $\pi_2$ in the symmetric group $\mathfrak{S}_n$ are $k$-equivalent, denoted
$\pi_1 \sim_k \pi_2$, if one can be
determined from the other after a finite number of ...
- 43.1k
7
votes
1
answer
232
views
counting monomials and integrality
For $n\in\mathbb{Z}^{+}$, consider the polynomials
$$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$
QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?
...
- 43.1k
7
votes
1
answer
480
views
Imprimitive solutions to $x^2+y^3=z^7$
Poonen, Schaefer, & Stoll give the primitive solutions to $x^2+y^3=z^7$:
$$
(±1, −1, 0), (±1, 0, 1), ±(0, 1, 1), (±3, −2, 1), (±71, −17, 2),\\
(±2213459, 1414, 65), (±15312283, 9262, 113), (±...
- 9,114
1
vote
0
answers
742
views
Kaprekar's mapping fixed points
Jens Kruse Andersen in his comment in OEIS's A099009 noticed 3 families of numbers among Kaprekar's fixed mapping points (otherwise known as kernels of the Kaprekar's routine):
"Let $d(n)$ denote $n$...
- 335
2
votes
0
answers
970
views
Is the stationary distribution of this Markov chain uniform?
First, a little bit of background: Since 2012, Canada has decided to phase out the penny for its coinage system. Product prices may still use arbitrary cents, especially since prices do not typically ...
- 29
6
votes
1
answer
372
views
A parity counting problem for subsets over finite fields
Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$.
For a subset $T\subseteq {\mathbb F}_p$, define
$$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb F}_p,b)|...
- 121
13
votes
1
answer
2k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
user56218
3
votes
1
answer
705
views
bounded partitions and bounded signed partitions of integers
Define a bounded signed partition of length $m$ and of bounded height $h$ of an integer $n$ by a relation:
$$n = \pm a_{1} \pm a_{2} \pm a_{3} \pm \dots \pm a_{m}$$ where each $a_{i}$ is a integer in ...
- 13.9k