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)

5
votes
1answer
63 views

Combinatorial proof of a certain alternating sum of binomial coefficients

The following identity appeared as a question earlier today $$\displaystyle\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = \begin{cases} 1\ \text{if}\ n=0 \\ 0\ \text{if}\ n>0 ...
1
vote
3answers
43 views

Seating arrangements of 7 boys and 5 girls in a row.

In how many ways can these boys and girls be arranged in a row if between two particular boys A and B there are no boys but exactly 3 girls?
171
votes
17answers
30k views

Do men or women have more brothers?

Do men or women have more brothers? I think women have more as no man can be his own brother. But how one can prove it rigorously? I am going to suggest some reasonable background assumptions: ...
-1
votes
0answers
17 views

A SDR extension problem [closed]

enter image description here I think we should use induction. for subset I when $|I|=1$ then we have for any $i\in \{1,\dots,n\}$ $|A_i|\leq 2$. Then for any $A_i$ we have $2$ SDR. then we suppose ...
4
votes
0answers
46 views

Find the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even

Let $n$ denote the number of 4 digit numbers of the form $abcd$ such that $ab+cd$ is even. Find the last digit of $n$. There are two cases. $ab,cd$ is odd. Which means $a,b,c,d \in \text{odd}$. ...
6
votes
2answers
34 views

For a group of 7 people, find the probability that all of their birthdays do not occur in the winter using the stars and bars counting method

So for a group a 7 people, find the probability that all of their birthdays do not occur in the winter. That is, all of their birthdays occur either in the spring, summer or fall. Assume that the ...
9
votes
1answer
144 views

Application of Combinatorics/Graph Theory to Organic Chemistry?

Recently, I have been self-teaching graph theory and having an organic chemistry course at school. When I was learning isomer enumeration I found great resemblance between organic molecules and ...
1
vote
2answers
33 views

Total number of perfect square which are factors of n [closed]

A number $N$ can be factorized as $$N = p_1^5 p_2^4 p_3^7.$$ Find total number of perfect square, which are factors of $N$.
4
votes
1answer
62 views

What is the probability that all $n$ colors are selected in $m$ trials?

I have a concrete problem, say, there are $n$ different balls ($n$ different colors to distinguish them), each ball will be selected uniformly at random. The way I choose a ball is that I randomly get ...
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 ...
3
votes
0answers
36 views

Isomorphism of Non-Symmetric Matrix when Permutation-Set is given: A simple observation

Context: Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not ...
0
votes
1answer
55 views

What is the number of interior faces adjacent to an interior vertex in a triangulation in $\mathbb{R}^3$?

Let $\Omega$ be a polygonal domain in $\mathbb{R}^3$. Assume $\Omega$ is partitioned into tetrahedra using the most common admissible triangulation, that is, roughly speaking, two adjacent tetrahedra ...
3
votes
2answers
90 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
32 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
66 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
0answers
31 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 ...
2
votes
1answer
35 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 ...
-3
votes
1answer
52 views

What is the probability of getting intial state (read details)? [closed]

Alex, Bob and Charlie each have 5 different colored marbles in their bags(same 5 colors in each of those bags though). Alex randomly picks a marble from Bob's box and puts it into his bag. Then ...
1
vote
1answer
21 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 ...
3
votes
2answers
62 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 ...
6
votes
1answer
44 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 ...
0
votes
1answer
54 views

Number of additive partitions [closed]

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 ...
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
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 ...
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$ ...
4
votes
1answer
26 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?
0
votes
1answer
41 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 ...
1
vote
0answers
48 views

Game of Nim: Losing Positions [closed]

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. ...
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 ...
2
votes
2answers
39 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
0answers
34 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
0answers
64 views

Sequence of integers in given range that sums up to given value

I'm trying to find out, if there is a way to find the total number of possible combinations of integers $x_i \in [l,u] \cap \mathbb{Z}$ for all $i = 1,\ldots,n$ that sum up to $A$. Generally, ...
4
votes
2answers
56 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
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
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 ...
1
vote
2answers
40 views

Definition of Finite Projective Plane clarification

I do not understand part iii. Why can't there be four collinear points? The Fano plane is an example of a $3$-uniform configuration. What about configurations that are $4$-uniform? You must ...
1
vote
1answer
27 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 ...
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 ...
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
42 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? ...
-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.
2
votes
2answers
75 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
4answers
523 views

How many rectangles?

Q: How many rectangles? What should I do here? I don't even know where to start from. Please help me by giving me a hint.
2
votes
2answers
72 views

Odd binomial sum equality has only trivial solution?

Suppose $$\sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2} = \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}.$$ Does $m=n=1$? Clearly $m \leq n$, and for every $n$ there is at most one ...
2
votes
1answer
96 views

IMO Longlist 1989 (Number of ways product can be expressed)

Given two distinct numbers $ b_1$ and $ b_2$, their product can be formed in two ways: $ b_1 \times b_2$ and $ b_2 \times b_1.$ Given three distinct numbers, $ b_1, b_2, b_3,$ their product can be ...
0
votes
1answer
25 views

How to get this complementary form of derangement written in a Wikipedia article?

In this article, how do they get the complementary form of $$\Big|S\setminus\bigcup_{i=1}^{n}A_i\Big|=\sum_{k=0}^{n}(-1)^k\binom{n}{k}\alpha_k$$ from ...
4
votes
0answers
65 views

Central limit theorem for perfect matching counts

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the ...
5
votes
5answers
545 views

How many strings of four decimal digits that do not contain the same digit three times?

Hello, everyone! I received the following question as part of my Discrete Mathematics course and am unable to solve it. How many strings of four decimal digits that do not contain the same digit ...
0
votes
1answer
30 views

How to differentiate if this is permutation or combination

A man has $4$ sons. There are $6$ schools near his house. In how many ways can he send his sons to school, if no $2$ sons are to study in the same school? As far as I can understand we just need to ...