For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
0answers
2 views

The coordinate difference of a nearest neighbor in a random set

Consider the following problem: $r$ vectors of length $t$ are drawn randomly, where each coordinate is an i.i.d Bernoulli random variable with success probability $$p_i , i=1...t.$$ What is the ...
0
votes
0answers
9 views

Number of possible ways to join n relations

The number of possible ways to join n relations r1⨝r2⨝r3.....⨝rn can have 3 distinct cases - If the join orders cannot change i.e. ri can only be joined to rj or any other intermediate relation ...
4
votes
3answers
37 views

How many ways a 9 digit number can be formed using the digits 1 t0 9 without repetition such that it is divisble by $11$.

How many ways a 9 digit number can be formed using the digits 1 t0 9 without repetition such that it is divisible by $11$. My attempt- A number is divisible by 11 if the alternating sum of its digit ...
1
vote
1answer
30 views

Maximize the number of non zero elements of a product of binary matrices.

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that: $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$) The number of ...
0
votes
0answers
27 views

All unique shapes from drawing lines between array of points

I have encountered this problem various times, but have never got my head around it. (I'm not very good in in problems like this...) Please don't blame me for not knowing specific math terms. (I ...
2
votes
3answers
35 views

Counting the number of subsets of a set of 2n elements satisfying some conditions.

Let $X =\{v_1, v_2,\cdots, v_n, v_{n+1},\cdots, v_{2n}\}$ be a set of $2n$ elements. I want to find the number of subsets of $X$ with $n$ elements such that both $v_i$ and $v_{n+i} $ are not together ...
-1
votes
0answers
22 views

For a set of positive integers $A$, does there exist some other set of positive integers $B$ such that some subset of $B$ sums to all $a\in A$

We ask, given a set of positive integers $A$ where each $a\in A$ $a>1$, does there exist some other set of positive integers $B$ such that for each positive integer $a\in A$ there exists $b_i\...
0
votes
0answers
23 views

Using the general ham sandwich theorem to proof Hobby-Rice

Matousek mentions that you can proof the continuous necklace theorem known as Hobby-Rice theorem via the continuous ham sandwich theorem. The continuous ham sandwich states: Let $\mu_1,\mu_2,...,\...
0
votes
0answers
25 views

Number of distinct integer-valued vector solution for $x_1 + x_2 + … + x_r = n$ [duplicate]

The Number Of Integer Solutions Of Equations $$x_1 + x_2 + ... + x_r = n$$ An approach is to find the number of distinct non-negative integer-valued vectors $(x_1,x_2,...,x_r)$ such that $$x_1 + x_2 +...
0
votes
0answers
7 views

how to calculate slack(u,v) in the Edmond's minimum weight matching algorithm (u and v are vertices of a graph)?

I am trying to execute the Edmond's minimum weight matching algorithm. As a reference, I am using a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen. The ...
3
votes
2answers
34 views

Languages acceptable with just a single final state

For a given regular language $L$ we can always find a corresponding automaton with exactly one initial state, this is quite a common result and in most textbooks even non-deterministic automata are ...
-1
votes
1answer
31 views

If G and H are two gaphs then what does $G \Delta H$ indicate in graph theory?

I came across this notation in a book titled " Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen.
0
votes
1answer
39 views

Number of graphs having a specific structure

Let $\mathcal{N} = \{1,2,\ldots,N\}$ and $\mathcal{N}^i = \mathcal{N}\setminus \{i\} $. For each $i \in \mathcal{N}$ and for each $S \subset \mathcal{N}^i$, we have a vertex $C_i^S$. For example, if $...
3
votes
3answers
359 views

Arranging numbers around a square

In how many ways numbers 1 to 12 can be arranged on a sides of squares (5 places on each sides i.e 20 places total) leaving 8 places empty? I am getting answer as 12c5(selecting 5 numbers)*7c5(...
1
vote
2answers
63 views

Find the divisors of $5040$ in the Plato's dialogue “Theaetetus”

In the Plato's dialogue "Theaetetus", at a certain point, we have the following "problem" \begin{align*} 5040 &= 7! \\ &= 1\times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \\ &= 2 \...
1
vote
3answers
36 views

Concerning The Number of Ways of Drawing a Full House vs. Two Pair

The Wikipedia entry for "Poker probability" gives the following result for the number of ways of drawing a full house: $$ \binom{13}{1} \binom{4}{3} \binom{12}{1} \binom{4}{2} = 3, 744. $$ The logic ...
1
vote
1answer
48 views

Closed form for $\sum_{k=0}^{m} {\binom {m}{k}} a^{k} (b+ck)^N$

Is there a closed form for the following? $$\sum_{k=0}^{m} {\binom {m}{k}} a^{k} (b+ck)^N$$ how about a pretty limit for large $b$. I have tried using the binomial expansion for the $(b+ck)^...
2
votes
0answers
43 views

Partitioning a set of integers (with Alice and Bob)

Let $ d_1,\ldots,d_n \in \mathbb{N}_{\ge 2} $ (not necessarily distinct) be given. Define $ D:=\operatorname{lcm}(d_1,\ldots,d_n) $ and $ d:=\sum_{i=1}^n d_i $. (1) Alice claims that whenever $ \...
2
votes
1answer
50 views

Black are berries and maroon are cherries. Place 8 more cherries removing berries 1 from each row and each column. No of ways?

I tried to see it as a matrix where for a position (i,j) , i+j = 8, 9, 16 means you can't change that position. Any help?
0
votes
1answer
41 views

Binomial coefficient paths?

Here's a problem and my attempt to answer it: We want to get a binomial coefficient identity depending on grid walking. Starting from the bottom left corner and going to the top right corner. You can ...
1
vote
2answers
33 views

What is the chance of randomly generating a given 10-character sentence? [on hold]

Suppose we have an alphabet of the following allowed characters: the lowercase letters $a$ through $z$ (26) the uppercase letters $A$ through $Z$ (26) the numerals $0$ through $9$ (10) the common ...
2
votes
1answer
57 views

The first step in the proof of the Pólya-Vinogradov Inequality.

The well-known Pólya-Vinogradov Inequality states: $$\forall m, n \in \mathbb{N}: \displaystyle \left|{\sum_{k \mathop = m}^{m+n} \left({\frac k p}\right)}\right| < \sqrt p \ \ln p,$$ where $\...
3
votes
1answer
24 views

How to find combinations with two conditions, one of them dependent on the other?

How to find the number of combinatorial arrangements with two conditions, if one of the conditions is itself dependent on the second? The question below will make it clearer. The problem statement ...
3
votes
2answers
79 views

The number of positive integer solutions to the equation $x_1+x_2+…+x_n=n^2.$

I'm working on this problem. To solve it I need this lemma: Let $n\ge2, n\in \mathbb N$. Let $X$ be the number of solutions in positive integers to the equation $x_1+x_2+...+x_n=n^2$. Let $Y$ be ...
2
votes
1answer
17 views

Expectation of absolute sum of squared normal distributions

Let $u_i$ be a standard normal distribution for all $i$. All $u_i$'s are independent of each other. I want to compute the expectation of: $$| \sum_i u_i^2 \lambda_i |$$ Where $\lambda_i$ is real ...
1
vote
1answer
42 views

Expected number of couples having same number

I have $n_1$ red balls in a box $A$. These balls are numbered from $1, \cdots n_1$. Let make a copy version of box $A$, called box $D$ (It means that the box $D$ will contain $n_1$ red balls from $1, \...
0
votes
1answer
18 views

Expected sum of Hamming distances in set of random strings

Thee Hamming distance $H(S_1, S_2)$ between two binary strings $S_1, S_2$ of length $n$ is the number of positions on which the two strings disagree. It is straightforward to show that if $S_1, S_2$ ...
3
votes
1answer
63 views

Team grouping troubles

Imagine there are 12 teams, numbered 1 through 12. There are 10 games those teams can compete in, with two teams needed per game. There are 10 rounds, and it is important that after the 10 rounds are ...
2
votes
0answers
21 views

Extending a code by adding a parity check

Let $C$ be a $[n,k,d]_2$ code where $d$ is odd. It is known that you can construct a $[n+1,k,d+1]_2$ code by adding a column $\boldsymbol{c}_{n+1}$ to the codebook matrix where each element contains ...
2
votes
1answer
46 views

Probability of sums with 6 dice [duplicate]

You roll six independent fair dice. What is the probability that their sum is divisible by 6? I don't really know where to start. Does the ordering of the dice matter? (1,2,2,2,2,3) vs (3,2,2,2,2,1)....
4
votes
1answer
43 views

Different combinations of 7 books distributed to 7 critics, twice

I'm having an exam on Discrete Mathematics II in my university, and I came up to this problem. A publishing firm has 7 books ready to publish. Each of them needs to be reviewed by 2 different ...
0
votes
1answer
64 views

Condition that for a given set of numbers and given divisor all finite sums from this set contain all possible remainders

Given $q \in \mathbb{N}$ and ${a_1, a_2, ...}$ where each $a_j \in \mathbb{N} \cup{\{0\}}$ define $A_p=$ {set of all finite sums of $\{a_1 ... a_p\}$ such that each $a_j$ will appear either $1$ or $0$ ...
1
vote
1answer
58 views

binomial coefficients difference? [on hold]

I need a difference of 2 binomial coefficients that would be equivalent to the following sum: $12\choose5$+$11\choose5$+$10\choose5$+$9\choose5$+$8\choose5$ How to answer this?
3
votes
3answers
59 views

When should we consider objects as distinguishable in probability?

Example : Why is the probability of getting a sum of 12 when we roll two fair dices is 1/6 whereas probability of getting 5 is 2/6 . When we labeling the dice red and green in our head , isn't (6 ...
3
votes
4answers
48 views

Probability of a dice launched three times

A dice is launched three times. What is the probability to obtain three even numbers ? I've solved this problem calculating the number of total results: $$u=D'_{6,3}=6^3$$ and the number of ...
1
vote
1answer
34 views

Prove there are two points an integral number of inches apart of the same colour

A line is coloured in $11$ colours. Prove that there are two points of the same colour that are an integral number of inches apart. I don't know how to do this, but I know how to do a similar problem ...
-1
votes
2answers
47 views

What is the probability of random walking ant to be at a position after some finite steps on an infinite grid? [on hold]

Is it even calculable? What if the grid is infinitely dimensional? Lets say that it is a simple random walk, and probability to move to any neighboring position is equal, but other types are also ...
4
votes
5answers
72 views

How many subsets contain no consecutive elements?

How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers ? Here is the solution : The subsets are interpreted as $n$-words from the alphabet $\{0,1\}$. Let $a_n$ be the number of words ...
1
vote
0answers
25 views

Area under staircase walk

If I create a random lattice path from $(0,0)$ to $(n,k)$, taking only north or east steps $(1,0)$ or $(0,1)$, with equal probability, the so called staircase walk, what are the moments of the area ...
1
vote
1answer
69 views

Decomposition of $ \binom {n} {j-1}j^k $

It is easy to check that: $$ \binom {n} {j-1}j = \binom {n-1} {j-1}+\binom {n-1} {j-2}(n+1) $$ and $$ \binom {n} {j-1}j^2 = \binom {n-2} {j-1}+\binom {n-2} {j-2}(3n+2)+\binom {n-2} {j-3}(n+1)^2 $$ We ...
2
votes
2answers
72 views

Enumeration of primes

Given a prime number $p$, there is an associated number $n(p)$, giving its ranking in the sense that $n(2)=1$, $n(3)=2$, $n(5)=3$ etc. Is there a closed form expression for $n(p)$ in terms of $p$?
2
votes
1answer
35 views

Arrange 18 pips on a die with at least one 0 side to maximize the probability that 5 rolls sum to 13 or more.

You are arranging pips on a standard 6-sided dice. Rules: At least one side must be left blank at 0. The average roll must be 3 (so, you have 18 pips to distribute among five sides). You want to ...
0
votes
0answers
18 views

maximize a sum of unit fractions (without containing a subset of sum 1)

Let $ u \ge 2 $ be fixed. Then consider: $ S(u)=\max\left\lbrace \sum_{i=1}^{u+1} \frac{c_i}{t_i} \, \middle| \, 2 \le t_1 \le t_2-1 \le \ldots \le t_{u+1}-1, \, t_i \in \mathbb{N}, \, c_i \in \...
0
votes
0answers
23 views

Symmetric brace algebras - unshuffle sequences

I'm studying brace algebras in this article: Symmetric Brace Algebras. In the following definition, what do the authors mean by "unshuffle sequences"? Definition 2. A symmetric brace algebra is a ...
3
votes
1answer
21 views

Seeking Additional Solutions for the Number of Network Links

The Problem Show that the number of possible links in a computer network of $n$ computers ($n \in Z \land n \geq 1$) is $\frac{n(n-1)}{2}$ in as many ways as you can. My Work Solution 1 Given $n$ ...
8
votes
1answer
30 views

Selecting disjoint subsets with the same sum from a set of ten distinct two digit numbers

My question is the following: Is it possible to select two disjoint subsets whose members have the same sum from a set of ten distinct two-digit numbers (in the decimal system)? I guess the answer ...
0
votes
0answers
40 views

Counting GF($q=8$) matrices with a certain property

Let us denote by $\boldsymbol{v}_i$ the columns of an $m \times n$ GF($8$) matrix. The field elements are enumerated $\{0,1,2,...,q-1\}$. To define the arithmetic operations between field elements, we ...
3
votes
3answers
46 views

Number of 10-digit binary strings with 6 ones, 4 zeros and no consecutive zeros

The answer is $\binom{7}{4}$ but I can't figure out why.