All Questions
Tagged with enumerative-combinatorics pr.probability
23 questions
4
votes
1
answer
197
views
On a double sum involving binomial coefficients
For natural $n$, let
\begin{equation}
p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l)
\sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1}
\end{equation}
where $k:=\lfloor(n+1)/...
- 128k
1
vote
0
answers
77
views
Distribution of colour pairs from a random matching
Given $a$ many red balls and $b$ many blue balls, with $a+b$ even, suppose we chose a random matching between the $a+b$ balls. What is the distribution of the number of red-red and red-blue (and blue-...
- 129
3
votes
2
answers
250
views
Proof of an asymptotic formula by Tricomi
Firs of all I ask my question, then I explain how this question arises in my mind and lastly what I tried to solve it.
QUESTION:
Let $P_{n,N}(k)$ be the number of composition of an integer $k$ in $n$ ...
- 361
0
votes
0
answers
91
views
Connectivity constant for lattices
A celebrated result due to Duminil-Copin and Smirnov states that the connectivity constant for the honeycomb lattice is equal to $\sqrt{2+\sqrt{2}}$.
My question is the following: apart from the ...
- 1,561
3
votes
1
answer
158
views
Random covering of a set
Let $A$ be a set of $n$ elements. Let $S_1,\dots,S_n$ be independent $k$-element random subsets of $A$. What is the probability that $S_1,\dots, S_n$ evenly cover $A$, i.e. each element of $A$ belongs ...
- 1,608
17
votes
1
answer
1k
views
Can this probability be obtained by a combinatorial/symmetry argument?
Suppose that $a_1,\dots,a_n,b_1,\dots,b_n$ are iid random variables each with a symmetric non-atomic distribution.
Let $p$ denote the probability that there is some real $t$ such that $t a_i \ge b_i$ ...
- 128k
3
votes
1
answer
118
views
Using singularity analysis for probability at a threshold?
In some urn model with parameter $p$, the generating function
$$
f_p(z) \;=\; \frac{1+p\,z}{1-(1-p)\,z\,(1+p\,z)}
$$
is such that $[z^n]f_p(z)$ is the probability that an $n$-urn configuration has a ...
- 674
0
votes
1
answer
305
views
Number of duplicate pairs in multiple samplings
My universe has M different items. I run m=10 independent samplings over M. In each sampling, n elements are picked without replacement (n<<M). What is the expected number of pair duplicates we ...
- 67
1
vote
0
answers
100
views
Balls and bins, with cardinality constraints
Suppose I have $n$ sets of $k$ balls each, with each one of the $nk$ balls distributed uniformly at random among $m$ bins. Further suppose that I have a probability vector $p=(p_1,\dots,p_m)$. I am ...
- 4,049
8
votes
1
answer
270
views
Sizes of connected components from a random choice in a grid
This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares. ...
- 13.4k
4
votes
1
answer
115
views
What is the probability of an empty convex $k$-gon among many given points?
Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points.
For a big number $n$ of randomly distributed ...
- 13.4k
1
vote
2
answers
237
views
Fair partitioning of a set - Weighted sums of Bernoullis
For $n$ an integer, let $a_n$ be the number of ways in which one may partition the set $\{1, \ldots, 2n \}$ in two parts with:
the same number of elements: $n$
and the same sum: $2n(2n+1)/4$.
...
- 468
3
votes
0
answers
78
views
Using Kac-Rice formula to count average number of sub-regions carved out by $n$ random hyper-planes
Context. This is the first in a set of tiny pieces of a problem I've formulated to help me measure the "complexity" of certain piecewise linear functions. Thanks in advance for your help and patience.
...
- 6,853
13
votes
1
answer
564
views
Coincidences between average Catalan tableaux
There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices:
$$
P_n \, := \, \frac{1}{C_n} \, \...
- 17k
3
votes
1
answer
197
views
Generalized Shared Birthday
Suppose a year has $d$ days. How many people should be in a room so that there are at least $2k$ people in the room with birthdays shared with each other (all could be same day or there could be $k$ ...
user94040
3
votes
0
answers
142
views
Probability of hitting two vectors
Call an element of $ \{-m,\dots,0,\dots,m\}^{2^n}$ a vector. Assume $m = O(2^{2^n})$.
Let $u_1,u_2$ be vectors.
Let $\{v_1,\dots,v_{2^n}\}$ and $\{w_1,\dots,w_{2^n}\}$ be linearly independent ...
- 13.9k
3
votes
1
answer
693
views
Size of automorphism group of random regular graph
If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$?
--
I want to know what is the ...
- 13.9k
2
votes
1
answer
300
views
Number of subsets that sum to $0$
Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...
user76479
3
votes
2
answers
256
views
Picking codewords that are close
I posted this question in https://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
- 13.9k
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
0
votes
1
answer
123
views
Enumeration of quadrangulations with a boundary and simple faces.
I wish to enumerate all quadrangulations of a $2p$ gon with $n$ internal vertices. Quadrangles are required to have simple faces. Simple face means all four vertices of each quadrangle are distinct.
...
- 141
29
votes
6
answers
2k
views
Combinatorial Morse functions and random permutations
This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...
- 34.7k
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k