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)

4
votes
1answer
29 views

On the GCD of two palindromes.

I had an observation. Which I will discuss below. My question will be Is my observation correct? If so, how can one prove it? Observation: Consider the string of palindromes below: $100...01$ and ...
1
vote
2answers
145 views

What is the probability of sinking all ships in a simplified game of battleship?

Consider a simplified game of battleship. We are given a $4\times 4$ board on which we can place $2$ pieces. One destroyer which is a $1 \times 2$ squares and a submarine that is $1 \times 3$ ...
2
votes
3answers
55 views

Finding a ratio from a set of discrete values

For $x = p/q$, where $x$ is a known value between $0.000$ and $1.000$ rounded to the thousandths place, $p$ is an integer value between $0$ and $127$, and $q$ is an integer value between $0$ and ...
3
votes
2answers
61 views

How many colours do we at least need so that we can ensure all 250 countries have different flags.

One for FN standardized flag consists of three horizontal rectangular fields. If we assume that the middle field not are allowed to have the same colour as the top or bottom field, how many colours do ...
3
votes
2answers
86 views

How can I prove this equation holds?

As the final part of a big proof I got for uni homework: (It is an extra question, may be unsolvable) $$k^n<\sum_{i=0}^n\binom{n}ik^{n-i}(2^i-1)$$ My idea is to develop the right side into an ...
0
votes
1answer
30 views

Letter combinatorics and probabilities

Hello I've got some problems and I don't know if my solutions are correct: Given a Text with two letters $A$ and $B$ and the the probability of occurrence of letter $A$ is $p_a$ and $B$ is $p_b$, the ...
1
vote
2answers
60 views

Sum of odd integers $= x$

How many sums are there that add up to a whole number $x$, and are made of only odd numbers? Each number can be used more than once.
1
vote
1answer
383 views

Identity using q-Pochhammer symbols

Prove - $$∑_{n=0}^{∞} \frac{(a;q)_n}{(q;q)_n} q^{n\choose 2} q^n={(−q;q)_∞}{(aq;q^2)_∞}.$$ where $(a;q)$ are the q-Pochhammer symbols. I know that the RHS is the product of generating functions of ...
6
votes
1answer
42 views

Tokens in boxes problem

Tokens numbered $1,2,3...$ are placed in turn in a number of boxes. A token cannot be placed in a box if it is the sum of two other tokens already placed inside that box. How far can you reach for a ...
1
vote
0answers
26 views

Vandermonde-type convolution with geometric term

Is there a closed-form solution to the following sum? \begin{align*} f(r, s, n) = \sum_{k=0}^{n}c^k\binom{r}{k}\binom{s}{n-k} \end{align*} I know this corresponds to find the coefficient of $x^n$ of ...
3
votes
2answers
125 views

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$. Relevant definitions: $G$ is a simple graph that consists of a vertex set ...
2
votes
1answer
32 views

Probability - Combinations

I am having big problems with this exercise: There are $n$ customers and $k$ types of products and number $i$, where $n \ge k \ge i$. I have to find the probability of the situation where ...
1
vote
1answer
19 views

Pigeonhole Principle by using induction

Prove the generalized Pigeonhole Principle: Let $n$ and $m$ be natural numbers, $X$ and $Y$ sets with $|X| = mn + 1,\; |Y | = n$, and $f : X\to Y$ a function. Then there exists $y \in Y$ such that ...
0
votes
1answer
53 views

Number of additive partitions [on hold]

Show that the number of additive partitions of $n$ in which no summand appears more than $d$ times equals the number of additive partitions of $n$ in which no summand is a multiple of $d+1$. Now ...
1
vote
2answers
40 views

Number of possible arrangements of rings on a hand

This is a homework question that I'm having trouble figuring out how to start. Here's the question. A woman has 3 different rings. On any given day she wears 1, 2, or (inclusive) 3 of her rings on ...
0
votes
0answers
80 views

integral vertex of the polyhedron

I am trying to prove the following : If $A$ is a $\{0, 1\}$-matrix, then any integral vertex of the polyhedron $P = \{x \mid x \geq 0 ; Ax \geq 1\}$ is a $\{0, 1\}$-vector. But I cannot do it. ...
0
votes
2answers
40 views

12 books shelf and bag.

I got two varieties for the same question: Ways that four books out of a bag of 12 books can be placed on a shelf. Ways to choose 4 books out of 12 arranged on a shelf and put them in a bag. ...
1
vote
0answers
44 views

Game of Nim: Losing Positions [on hold]

If you have heard of the game Nim, this is a version of the game. However, in this version, the players can only remove the amount of stones from the pile which is coprime to the current pile size. ...
2
votes
2answers
74 views

Asymptotic for combinatorial function

Let $$F_q(k) = \sum_{n=1}^{\infty} \binom{n-1}{k} \binom{1/2}{n} q^n$$ be a function on $\mathbb{N}$. I am interested in the asymptotic behavior of $F$. Any ideas how to tackle it?
2
votes
1answer
24 views

Arrangements with no anomalous neighborhoods

How many ways can $8$ boys and $20$ girls be ordered such that for each boy at position $i$, there is no neighborhood (of $2n+1$ points with $n > 0$) consisting of positions $j \in [i-n,i+n]$ that ...
2
votes
1answer
18 views

Suppose a bookshelf contains five discrete math texts, two data structures texts, six calculus texts, and three Java texts

(a) How many ways can you choose one of the texts? (b) How many ways can you choose one of each type of text? Solution: a) By the rule of sum, there are all together $5 + 2 + 6 + 3 = 16$ ...
5
votes
0answers
66 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ (random order). We have a comparator $C$, but it has a probability $p$ to ...
4
votes
1answer
24 views

There are how many ways can we list, without repetition of all the elements of $S = \{ x, y, z\}$

Solution: there are six ways: $xyz$, $xzy$, $yxz$, $yzx$, $zxy$ and $zyx$. Doubt: How do we know there are six possible ways?
2
votes
2answers
38 views

Seating children in the cinema

I just had finished my class and have been struggling with a problem. There's $9$ seats in the cinema, and two families $F_a=\{F_1,F_2,F_3,F_4,F_5\},$ $F_b=\{F_a,F_b,F_c,F_d\}$ In how many ways can ...
0
votes
1answer
40 views

How many coefficients in $(x_1 +x_2 + \cdots + x_L)^N$?

How many coefficients in $(x_1 + x_2 + \cdots + x_L)^N$? That is to say, what is the number of coefficients when it represents as sum of products.
4
votes
0answers
50 views

Birthday problem: why is this solution wrong?

This question is about the birthday problem: the probability that in a group of n people, at least two of them have the same birthday (https://en.wikipedia.org/wiki/Birthday_problem). An easy way to ...
6
votes
3answers
2k views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
0
votes
1answer
17 views

How many words can be formed, given $4$ letters, and in each word there must be at least two letters are the same?

How many words can be formed, given $4(a,b,c,d)$ letters, and in each word from $4$ letters there must be at least two letters are the same? The position of the letter doesn't matter. The answer is ...
5
votes
4answers
841 views

Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Consider the following identity: \begin{equation} \sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1} \end{equation} Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ ...
0
votes
0answers
33 views

inding all possible non-repeating numbers with given digits

How to find all non-repeating number from the following digits:$0,2,4,5,7,8$ This is how I tried to solve it: Since numbers can't start with 0, and the order of the elements matters, it has to be ...
0
votes
1answer
407 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
0
votes
2answers
49 views

In how many ways can $2t+1$ identical balls be placed in $3$ boxes so that any two boxes together will contain more balls than the third?

In how many ways can $2t+1$ identical balls be placed in $3$ boxes so that any two boxes together will contain more balls than the third? I think we have to use multinomial theorem, but I cannot ...
1
vote
3answers
260 views

Isomorphism of Non-Symmetric Matrices

$A, B$ are non-symmetric matrices of dimension $m \times n$ where $m=n$ or $m \neq n$. Example: An example of $6 \times 3$ non-symmetric matrix is $$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & ...
4
votes
2answers
54 views

Why does the Number of Graphs on $n$ Vertices Blow up so Quickly?

See for example here: https://en.wikipedia.org/wiki/Graph_enumeration I would have thought (naively) that the number of graphs on $n$ vertices would only grow as $\mathscr{O}\left( _nC_2\right)$, but ...
0
votes
1answer
50 views

Recurrence for integer triangles with perimeter $n$

Let $a_n$ be the number of sets $\{x,y,z\}\subset\mathbb{N}$ such that $x,y,z$ are the lengths of the sides of a triangle with perimeter $n$. Obtain a recurrence relation for $a_n$. I don't ...
-1
votes
1answer
20 views

HW Question about the Eccentricity of connected graphs. [closed]

How do I prove the following Theorem?: "Let G=[V,E] be connected graph with n vertices, therefore: rad(G)<=Diam(G)<= 2 * rad(g).
1
vote
2answers
508 views

Number of binary search trees on $n$ nodes of height up to $h$

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$? For example, if ...
-1
votes
0answers
19 views

Any rectangle that consists of rectangles with property p has property p [duplicate]

In a rectangle, property p is defined as follows "at least height or width is an integer" PROVE THAT:any rectangle that consists of rectangles with property p has property p with using graph.
1
vote
2answers
31 views

Minimum number of elements in $S_A$, given $|A|=n$

Problem: Suppose $A$ is a set of integers with $A=\{a_1,a_2,...a_n\}$. Define $S_A=\{r+s:r,s\in A\}$. For example, if $A=\{1,3\}$ then $S_A=\{2,4,6\}$. Show that, $$|S_A|\geq2n-1$$ My attempt: I ...
0
votes
1answer
733 views

Probability of Obtaining A Particular Sum from Successive Dice Rolls

Suppose you have a regular die with 6 faces numbered 1 through 6, respectively, and roll the die 4 times. What is the probability that the sum of the 4 rolls is 14? This problem is equivalent to ...
0
votes
1answer
42 views

Number of Possible Configurations

I have an embarrassingly simple problem that I'm not confident that I'm answering correctly. Say you have a 3 by 3 grid, where any number of spaces in the grid can be colored in, including all or ...
-5
votes
0answers
33 views

ENUMAERATIVE COMBINATORICS [closed]

IN HOW MANY WAYS CAN YOU PUT PARENTHESES IN A NON ASSOCIATIVE PRODUCT OF N FACTORS?
1
vote
1answer
26 views

Show every self-complementary graph on $4k + 1$ vertices has a vertex of degree $2k$.

I am not sure how to show this. I know a self complimentary graph on $4k+1$ vertices will have $\frac{\binom{4k+1}{2}}{2}=4k^2+k$ edges. I think another way to rephrase the problem is to show that ...
2
votes
3answers
1k views

Black and white balls in 2 boxes and probability that I pick the white ball.

Maybe there already is solution for that and if it is so, then maybe someone can tell me where I can find it. I have 2 boxes. In first box there are 3 white and 2 black balls. In second box there are ...
3
votes
1answer
177 views

Ballot box - conditional probability

I indicate with $(w,b)$ a box with $w$ white balls and $b$ black balls. 1st step. From a box $(6,5)$ I extract one ball at random and put it back with another one of the opposite color. 2nd ...
7
votes
3answers
173 views

Probabilistic Interpretation of Burnside's Lemma

Burnside's Lemma states that $N$, the number of orbits when a group $G$ acts on a set $X$ is given by $$N = \frac{1}{|G|} \sum_{g \in G} |\text{Fix } g|$$ The standard proof involves applying the ...
1
vote
3answers
31 views

Three Digit Numbers Above $560$ Formed From $3,4,5,6,7$

Is there a straight forward way of calculating the number of three digit numbers greater than 560 that can be formed from the numbers $3,4,5,6$, and $7$. I found it to be $30$ but I did it in a round ...
4
votes
1answer
40 views

Number of ways to make a bracelet with n beads and m colors

I was solving a problem on the Art of Problem Solving website that was posed like this: How many ways can the $7$ spokes of a wheel be painted such that each spoke can be either red, green, or blue? ...
-6
votes
0answers
45 views

Guys please help me :) [closed]

Help me in maths please :) There are 12 (resp.15) black and 10(12resp.) white balls in the first (resp. Second) box? To find the porbability that the ball taken from the second box will be white. If ...
3
votes
2answers
259 views

Probability of having 'k' elements that occur only once in a multiset filled by sampling with replacement

Let's say that I have a set of unique elements, $P$, and a multiset $M$ that I fill with $N \leq ||P||$ elements by sampling with replacement from $P$. What is the probability that the multiset $M$ ...