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)

0
votes
0answers
4 views

How many $(r+1)$- subsets of $[n+1]$ have $(k+1)$ as their largest element?

Let $[n+1]$ be the set defined by $4[n+1]=\{1,2,...,n+1\}$. Call a subset of $[n+1]$ with $r+1$ distinct elements an $(r+1)$-subset. How many $(r+1)$-subsets of $[n+1]$ have $(k+1)$ as their largest ...
1
vote
0answers
5 views

Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$. I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$. (If the answer is ...
1
vote
3answers
39 views

Combinatorics proof $\binom{2n}{2}=2\binom{n}{2}+n^2$

The problem is prove that $$\binom{2n}{2}=2\binom{n}{2}+n^2$$ by showing that each side counts the same collection of subsets. I am trying to study for a final exam and this is a question from a ...
2
votes
0answers
24 views

A fair die is rolled nine times. What is the probability that 1 appears three times, 2 and 3 each appear twice, 4 and 5 once and 6 not at all?

A fair die is rolled nine times. What is the probability that 1 appears three times, 2 and 3 each appear twice, 4 and 5 once and 6 not at all? My approach is fairly simple. The dice is fair, so we ...
0
votes
1answer
24 views

how many bit strings of length n are palindromes

While reading in a Discrete maths text book, there was this question : how many bit strings of length n are palindromes The answer is : $2^\frac{n+1}{2}$ for odd and $2^\frac{n}{2}$ for even ...
0
votes
0answers
6 views

scalar multiple of Young symmetriser

The following is a lemma on Fulton and Harris' book -Representation theory,a first course (page 53): Lemma: For all $x\in \mathbb{C}\mathfrak{S}_r$, $c_{\lambda}\cdot x\cdot c_{\lambda}= scalar ...
3
votes
1answer
30 views

Some unique representation of nonnegative integers

Let $\mathbb N$ be the set of nonnegative integers, that is $\mathbb N=\{0,1,2,3,\ldots\}$. Does there exist a subset $K\subset\mathbb N$ such that every $n\in\mathbb N$ has a unique ...
2
votes
1answer
20 views

Possible functions from one set to another

**I've seen this question is discrete maths text : How many functions are there from the set $\{1, 2, . . . , n\},$ where $n$ is a positive integer, to the set $\{0, 1\}.$ a) that assign to ...
0
votes
0answers
6 views

How many functions are there from the sets that assign 1 to exactly one of the positive integers less than n [duplicate]

I've seen this question is discrete maths text : How many functions are there from the set {1, 2, . . . , n}, where n is a positive integer, to the set {0, 1} a) that assign 1 to exactly ...
0
votes
1answer
20 views

Generating function for the number of ways to part an integer $n$ such that no summand will repeat more than 3 times

What is the generating function for the number of ways to part an integer $n$ such that no summand will repeat more than 3 times? For example: $n=6$ so we can part it like this: $1+1+1+3$ but ...
2
votes
1answer
24 views

Ways to place 3 red, 4 blue and 5 green wagons such that no 2 blue wagons were standing next to each other

As the title says I need to find the number of ways to to place 3 red, 4 blue and 5 green wagons such that no 2 blue wagons were standing next to each other. The wagons of the same color are ...
3
votes
1answer
22 views

Choosing n objects from k types of objects, each of which is in limited supply

Suppose I wanted to light my Christmas tree. In my basement, I find a cord that has $5$ sockets in which I can screw bulbs. I also locate $5$ red bulbs, $4$ green bulbs, and $3$ blue bulbs. How many ...
2
votes
0answers
40 views

An identity involving Bernoulli and Stirling numbers

I was playing with some combinatorial sums and made an observation that I didn't know how to prove: $$\forall n\in\mathbb N,\hspace{10px}\sum_{k=1}^n\frac{B_k\ ...
1
vote
2answers
38 views

Given three values, how can I change two values to guarantee they are not equal to each other?

This is a variation of a previous question, hopefully without the same way to prove a solution cannot be found. I have 3 values; x, y, and z. Each value can only be a single digit (0-9). x and y are ...
-1
votes
1answer
26 views

I need some help to make a generating function for [on hold]

. I need some help to make a generating function for those series (3,6,11,18,...) and (3a1,0,0,3^2 a2,..) .
1
vote
1answer
48 views

Number of ways to place $n$ balls in $k$ bins where just the first $r$ bins have less than $m$ balls

How many ways are there to distribute $n$ balls into $k$ bins where the first $r$ bins have less than $m$ balls (each) and the rest of the bins have more than $m$ (each)? Given this solution for ...
2
votes
2answers
33 views

Given three values, how can I change one value to guarantee it is not equal to one of the other values?

I have 3 values; x, y, and z. Each value can only be a single digit (0-9). I know that x and y are different. I don't know if y and z are different or the same. I don't know if x and z are already ...
0
votes
1answer
49 views

How many numbers smaller than one million, their sum of digits is at least 20?

How many numbers smaller than one million, their sum of digits is at least 20? My attempt: Since I don't know how to handle the "at least" part, I'll be using a complement: The general case is ...
0
votes
1answer
21 views

How many bits strings are there of length n consisting entirely of 1's?

I've seen this question in a discrete maths text book : How many bits strings are there of length n consisting entirely of 1's ? and the answer is : Answer for that question is : n+1 ...
1
vote
1answer
18 views

Is the disjoint union of 2 copies of the complete bipartite graphs vertex transitive?

Is the disjoint union of $K_{n/4,n/4}$ and $K_{n/4,n/4}$ a vertex transitive graph? I think it is true, but since I failed to come up with a proof I have some doubts about it. Thanks
0
votes
2answers
13 views

Number of trees which has specific vertex as a leaf?

For vertices ${1,2,...n}$, I want to find the number of trees that has vertex $k$ as a leaf. By Cayley's theorem, the number of total trees are $n^{n-2}$. designate vertex k as a leaf. Now all trees ...
0
votes
2answers
15 views

Product Rule of Counting

I am new to combinatorics and I'm reading it from Kenneth H.Rosen book. Under the topic Product rule of counting, this problem was given : A new company with just two employees, Sanchez and ...
0
votes
1answer
24 views

Infinite Decision Problems [on hold]

How can I prove that there are infinitely many decision problems of natural numbers that cannot be soved?
2
votes
3answers
44 views

Combinatorics Question with a rectangular grid

Let $G$ be a rectangular grid of unit squares with $3$ rows ($3$ rows of squares) and $8$ columns. How many self-avoiding walks are there from the bottom left square of to the top left square of $G$ ? ...
0
votes
0answers
20 views

Prove that h:$\mathbb{Z}\rightarrow\mathbb{O}$ where h(n)=2n-1 is bijective

I need to prove that h:$\mathbb{Z}\rightarrow\mathbb{O}$ where h(n)=2n-1 is bijective. I haven't done problems where $\mathbb{Z}\rightarrow\mathbb{O}$ and have seen no examples. I am only familiar ...
0
votes
0answers
8 views

How many isosceles trapezes can one choose of four vertices of a regular 12 - gon?

How many isosceles trapezes can one choose of four vertices of a regular 12 - gon? I tried. First case. We have six lines parallel are $GF$, $HE$, $ID$, $JC$, $KB$, $LA$. Choose two lines from this ...
0
votes
1answer
28 views

Number of binary sequences containing a prefix with more 0's than 1's

Consider the set of all $(o+z)$-sized binary strings that contains $o$ 1's and $z$ zeros (and we assume $o>z$). Obviously, there are ${o + z \choose z}$ such sequences. I was wondering how many ...
0
votes
0answers
16 views

Result of a $2D$ random walk with position dependent probabilities

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk:- A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
1
vote
2answers
32 views

Limit and convergence of $\frac{1}{n^{n-1}}\sum_{p=2}^{n-1} \left[ {n \choose p} (n-p)^{n-2} p (-1)^p \right]$

This is a part of larger question, in which I was asked to show that a certain ratio has a limit of $e^{-1}$. After much of algebraic manipulation, I've found this ratio to be $$ ...
0
votes
1answer
27 views

Nonnegative integer solutions

How many non negative integer solutions are there to the equation: $(2*X_1) + (2*X_2) + X_3 + X_4 = 12$?
0
votes
1answer
35 views

In how many ways can two oranges, one apple, and one banana be distributed to two distinguishable bags?

I have $2$ oranges, $1$ apple and $1$ banana. I want to put $2$ of them at a time in $2$ bags, having $1$ ($1$ fruit at max in $1$ bag) each. The $2$ oranges are indistinguishable (there are two but ...
2
votes
1answer
43 views

Intuition behind receive a straight in poker

I know the answer is on wiki and other sites, but I am looking for some intuition of how to get there. Given that I am being dealt 5 cards from a well shuffled deck, there are $52 \choose 5 $ ways to ...
1
vote
1answer
20 views

Lines cutting regions

15 lines are drawn in a plane such that 4 of them are parallel. a. What is the maximum number of regions into which the plane is divided? b. How many of the regions are finite(bounded)? a) The ...
0
votes
0answers
22 views

Induction of maximum degree in multigraph

The Caen and Furedi paper The maximum size of 3-uniform hypergraphs not containing a Fano plane states several times and we can finish by induction and I can't work out how. Specifically in the ...
2
votes
1answer
41 views

Number of hairs of inhabitants and the population of a city

There is a town T where the population is greater than the number of hairs of each inhabitant. That is, if we count the number of hairs on the head of any inhabitant of the town, the amount will be ...
1
vote
1answer
21 views

Arrangements around a circle

$5$ mathematicians, $5$ biologists, $5$ chemists, $5$ physicists, and $5$ economists sit around a large round table. Prove that the $25$ people can be seated such that, if $A$ and $B$ are two ...
1
vote
1answer
15 views

Combination of Soccer Players

"A group of 30 students try out for a soccer team, which consist of 11 players. In how many ways can you select a team where there is a captain and an assistant captain?" I feel like there will be ...
4
votes
2answers
26 views

Counting identical beads on a necklace

Suppose I have 11 beads. 4 of them are red and 3 of them are blue. The remaining 4 are all distinct (so just say labelled 1 to 4). If these beads were in a straight line, then computing the number of ...
2
votes
2answers
65 views

Combinatorial proof $n {2n \choose n} = (n+1) {2n \choose n+1}$

I want to prove combinatorially that $n {2n \choose n} = (n+1) {2n \choose n+1} $. I have noticed that ${2n \choose n}$ is the number of ways walking only right or upwards in a square from a corner to ...
3
votes
2answers
82 views

Sum of series with binomial

How to calculate $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{2n}{2^{2n}(2n-1)}$$ ? I tried to use residues, generating function, combinatorics formulas, but unsuccessfully.
0
votes
1answer
38 views

Generalisation of Binomial Coefficient (Combinatorics on words)

So, when trying to find subwords from a bigger word: $\binom{abracadabra}{ab} = 5$ with $ABracadabra$, $AbracadaBra$, $abrAcadaBra$, $abracAdaBra$, $abracadABra$. I have noticed that it doesn't go ...
0
votes
2answers
30 views

Science Bowl Question Regarding Connecting Segments

Given a set of 5 points, no 3 of which are collinear, how many different ways are there to use 5 segments to connect the 5 points in such a way that each point is an endpoint for exactly 2 of the ...
0
votes
2answers
16 views

How many parallelograms can be formed when a parallelogram is cut by $2$ sets of $n$ parallel lines?

A parallelogram is cut by two sets of n parallel lines parallel to the sides of the parallelogram. The number of parallelogram thus formed is..?? I think we can do it by combinatorics.. But I'm not ...
0
votes
1answer
68 views

If a coin is flipped 25 times with eight tails occurring, what is the probability that no run of $6$ or more heads occurs?

I'm trying to approach this question using generating functions. I set the problem up similar to a "toss $17$ balls into $9$ bins, what's the probability that no bin gets $6$ or balls in it." as the ...
0
votes
2answers
27 views

Number of ways to distribute n identical balls amongst $k$ bins

So I've heard different responses from a lot of my friends when we were discussing this, and no answer seems to make intuitive sense to me. I thought it would be $n^k$, as this would represent the ...
3
votes
4answers
52 views

Number of integral solutions of $\text{xyz}=3000$

I want to find the number of integral solutions of the equation $$xyz=3000$$ I have been able to solve similar sums where the number on the right hand side was small enough to calculate all the ...
3
votes
2answers
35 views

14 pencils handed out to 6 people. Each person has at least 1 pencil. Person 6 no more than 3 pencils.

We have 14 indistinguishable pencils and we want to hand out all of the pencils to 6 people and we want everyone to get at least one pencil. However, we do not want person 6 to get more than 3 ...
1
vote
2answers
38 views

How many different ways can 14 pencils be passed out to 6 different people? Some people are allowed no pencils.

There are 2 questions that are very similar and I have the same answer to both but I don't think that's correct. Can you help me see the difference between the 2 questions. We have 14 ...
5
votes
4answers
55 views

Proving that $\max(x_1, x_2, x_3) = x_1 + x_2 + x_3 - \min(x_1, x_2) - \min(x_1, x_3) - \min(x_2, x_3) + \min(x_1, x_2, x_3)$

$$\max(x_1, x_2, x_3) = x_1 + x_2 + x_3 - \min(x_1, x_2) - \min(x_1, x_3) - \min(x_2, x_3) + \min(x_1, x_2, x_3)$$ Is there a more elegant proof to this than just trying out all the possibilities and ...
3
votes
4answers
146 views

Four 6-sided dice are rolled. What is the probability that at least two dice show the same number?

Am I doing this right? I split the problem up into the cases of 2 same, 3 same, 4 same, but I feel like something special has to be done for 2 of the same, because what if there are 2 pairs (like two ...