Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
63 views

Arrangements of fixed $k$-polyplets in a $n\times n$ matrix

Recently, I asked a question about the number of arrangements of $k$ elements inside a $n\times n$ matrix with certain restrictions. The one I´m actually interested in for this question is in its 2. ...
Cardstdani's user avatar
1 vote
0 answers
134 views

Number of ways to place 4 kings on nxn chessboard

I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example: In the case where the $4$...
Cardstdani's user avatar
-3 votes
1 answer
144 views

Count arrangements with pairs of attacking kings [closed]

I have a $1\times n$ chessboard and $2$ pairs of kings in it. Both components of each pair of kings must be adjacent in the chessboard, that is, they must be attacking. Now, I want to calculate the ...
Cardstdani's user avatar
1 vote
1 answer
170 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 ...
Cardstdani's user avatar
2 votes
1 answer
199 views

Average cluster size of a n-size vector

Given a vector of $n$ cells and $k$ elements in it, we can define a cluster of elements as a contiguous sequence of elements inside the vector. My goal is to calculate the average cluster size for all ...
Cardstdani's user avatar
0 votes
0 answers
55 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 ...
Cardstdani's user avatar
9 votes
1 answer
498 views

Quantum probabilistic method?

The probabilistic method uses arguments from probability to prove deterministic statements. This has been applied to diverse fields such as combinatorics, topology and number theory. In this method, ...
Riemann's user avatar
  • 654
1 vote
0 answers
84 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 ...
Cardstdani's user avatar
4 votes
2 answers
307 views

Lower bounding a partition-related sum

We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
MikeG's user avatar
  • 715
4 votes
0 answers
414 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 ...
Jackson's user avatar
  • 41
1 vote
0 answers
123 views

On probability of coprimality of a list of numbers

We know $r$ randomly chosen integers are coprime with probability $\frac1{\zeta(r)}$. Pick a bound $N$ and pick $k\lceil N^{\alpha}\rceil$ uniformly random integers in $[0,N^{\alpha+\beta}]$ where $\...
Turbo's user avatar
  • 13.9k
1 vote
1 answer
184 views

Expectation of edge weights on the complete graph

Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...
Stanley Yao Xiao's user avatar
5 votes
2 answers
708 views

Distribution of some sums modulo p

Fix a finite set of integers $S$ and a prime number $p$. Let $(a_1, a_2, \dotsc, a_n)$, $(b_1, b_2, b_3, \dotsc, b_n)$ be two sequences of integers where the numbers $a_i$ and $b_i$ are chosen ...
shurtados's user avatar
  • 1,101
8 votes
1 answer
380 views

Question about estimating random symmetric sums modulo p

Let $n > 0$ be a positive integer (large) and $p > 2$ a fixed prime number. What is the probability that $$\sum_{ 1 \leq i < j \leq n} a_ia_j = 0 \mod p$$ where $a_1, a_2, \dots a_n$ are ...
shurtados's user avatar
  • 1,101
11 votes
2 answers
1k views

Heuristic lower bounds on small sums of roots of unity

Let $f(k,n)$ be the smallest non-zero absolute value of a sum of $k$ complex $n$th roots of unity. Asking for bounds in either direction, Tao suggested that a polynomial lower bound seemed plausible ...
Ben Barber's user avatar
  • 4,589
5 votes
3 answers
601 views

Convergence speed of a random dyadic rational generator

We are given a multiset $M$ of real numbers which initially is equal to $\{0,1\}$. In a sequential fashion, at each round $r\in\mathbb{N}$ two distinct instances $x_r$ and $y_r$ of $M$'s numbers are ...
Penelope Benenati's user avatar
3 votes
1 answer
315 views

Distribution of the first occurrence of a maximum (record) run of zeros in the digits of a normal number (say $\pi$)

If the question was stated to appeal to the general public, it would be something like this. For a number such as $\pi$ or $\sqrt{2}$, the digits in base $b$ appear to be randomly distributed. We are ...
Vincent Granville's user avatar
1 vote
1 answer
266 views

Probability a near universal hash function $ax \bmod p \bmod m$ produces an output from inputs equal modulo $m$

For one of the near universal hash functions $f(x) = ax \bmod p \bmod m$ where $p$ is prime and $m < p, m>1$ and $x$ ranges over $1 \dots p-1$ , what is the probability that given $x_r \in \{ x |...
botsina's user avatar
  • 23
8 votes
1 answer
171 views

On the existence of a particular type of finite measure on $\mathbb N$

Let $\mathbb N$ denote the set of all positive integers. Does there exist a countably additive measure $\mu : \mathcal P(\mathbb N) \to [0,\infty)$ such that $\mu(\mathbb N)<\infty$ and $\mu(\{nk: ...
user521337's user avatar
  • 1,209
2 votes
1 answer
132 views

Independent decomposition of coordinate distribution

Let $\mathbf{x}$ be a random Gaussian vector in $\mathbb{R}^n$, i.e. $\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_n)$. Then for any fixed unit vector $\mathbf{u}$, one has $\mathbf{u}\mathbf{u}^\...
Wuchen's user avatar
  • 515
4 votes
0 answers
150 views

Dividing a finite arithmetic progression into two sets of same sum: always the same asymptotics?

This is inspired by the recent question How many solutions $\pm1\pm2\pm3…\pm n=0$. The oeis entries A063865 linked to this question and A292476/A156700 for the related one "How many solutions $\pm1\...
Wolfgang's user avatar
  • 13.4k
8 votes
2 answers
512 views

The average of reciprocal binomials

This question is motivated by the MO problem here. Perhaps it is not that difficult. Question. Here is an cute formula. $$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k2^{n-k}}...
T. Amdeberhan's user avatar
106 votes
5 answers
10k views

integral of a "sin-omial" coefficients=binomial

I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof? For any pair of integers $n\geq k\geq0$, we have $$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...
T. Amdeberhan's user avatar
9 votes
1 answer
564 views

combinatorics on cyclic sequences

Given $m\geq 1$, let $I=(a_1,\ldots,a_{3m})$ be a sequence such that $I$ contains exactly $m$ zeros, $m$ ones, and $m$ twos. Given $i=1,2$ and $j\leq 3m,k\leq m$ we can define $$U_{i,j}(k)=\text{...
Darío G's user avatar
  • 167
2 votes
0 answers
72 views

Sampling efficiently conditioned on linear constraints modulo both $\mathbb{F}_p$ and $\mathbb{F}_2$

Given a prime $p$ and positive integer $t \ll \log p$ (say $t = \sqrt{\log p}$), is there an algorithm that is polynomial time in $\log p$ to sample uniform $X, Y \in \mathbb{F}_p$ conditioned on the ...
user47772's user avatar
  • 305
11 votes
0 answers
282 views

Reference request: a combinatoric result [closed]

When I tried to construct a counterexample in my research, I encountered the following result, which should be true. Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = \omega(\...
Zhu Cao's user avatar
  • 211
5 votes
3 answers
938 views

Analogy between Integers and Permutations

I am reading Andrew Granville's Anatomy of Integers and Permutations where it is argued the factorization of a permutation into disjoint cycles is analogous to the factorization of a number into prime ...
john mangual's user avatar
  • 22.8k
8 votes
2 answers
379 views

Sets whose elements are mutually "weakly" coprime?

Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$, $$\mathrm{gcd}\bigg(x,\prod_{y\in S\setminus\{x\}}y\bigg)<\frac{x}{k}.$$ How small should a ...
Dustin G. Mixon's user avatar
4 votes
0 answers
1k views

Matula-Goebel ordering of rooted trees intrinsic?

I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here http://keithbriggs.info/matula.html) Looking through them, I ...
Zomulgustar's user avatar
3 votes
0 answers
173 views

Are numbers $h_{r,s} = \sum_{k} P(r;s;k) \frac{1}{n^{2k}} \bigg(1-\frac{1}{n}\bigg)^{n-2k}$ irrational?

I asked this question on MSE and Mike Spivey gave an insightful answer. I decided to put it here nevertheless in case someone else gets interested. If this violates rules on MO, please let me know, I'...
Alex's user avatar
  • 151
1 vote
0 answers
217 views

Calculating or estimating a combinatorial multivariate sum

Dear all, I'm currently looking at a problem in which the following combinatorial product emerges: $c(m_1,\dots,m_\lambda;n_1,\dots,n_\lambda)=\frac{m_1 !}{(m_1-n_1)!}\frac{(m_1+m_2-n_1)!}{(m_1+m_2-...
Ed Wolf's user avatar
  • 41
3 votes
0 answers
143 views

finding rank-3 tensors compatible with a rank-2 tensor projection

I am interested in the following problem: Consider a rank-3 symmetric tensor $\boldsymbol{\sigma}$ with $\sigma_{ijk}$ where $\sigma_{ijk}$ can be 0 or 1, and the symmetry is with respect to any ...
Ed Wolf's user avatar
  • 41
0 votes
1 answer
426 views

Lower bounds for partial sums of multiplicative functions

The motivation for this enquiry is to understand something about the impact of multiplicativity for $f:\mathbb{N}\rightarrow\mathbb{C}$ on the conditional convergence of Dirichlet series $$F(s)=\...
Kevin Smith's user avatar
  • 2,480
5 votes
1 answer
1k views

Self Avoiding Walk Enumerations

Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...
Alex R.'s user avatar
  • 4,952
0 votes
0 answers
319 views

Estimating a multinomial sum

I have the following sum \begin{equation} \sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda} \...
Eduardo Lopez's user avatar
3 votes
7 answers
4k views

How to tell if two random polynomials are identical

Let t be a positive real number. Let P(x) and Q(x) be two random polynomials with integer coefficients. If P(t) = Q(t), then what is the probability that P(x) is not identical to Q(x)? Will it make a ...
Balaji's user avatar
  • 179
4 votes
3 answers
579 views

Average distance between numbers of the form $2^{a}3^{b}$

I want to order all numbers of the form $2^a3^b$. I need to find the average distance between a random consecutive pair. For example, in case of a random consecutive pair $2^{n'}$ and $2^{n'+1}$, the ...
Pratik Poddar's user avatar