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
1answer
16 views

Generating Series and Recurrence Relation

We have the following recurrence relation: $b_n=6b_{n-1}-9b_{n-2}$ and initial conditions $b_0=1, b_1=6$ I use the generating series method to solve as following: Let ...
0
votes
0answers
10 views

A question on the Lagrange Inversion Formula

I have to use the L.I.F. for \begin{align*} s\left(x,y\right)=\frac{1}{2}\left(1-x-y-\sqrt{1-2x-2y-2xy+x^2+y^2}\right) \end{align*} to obtain that \begin{align*} s\left(x,y\right) = ...
4
votes
1answer
25 views

Number of ways in which a batsman can score 14 runs in 6 balls not scoring more than 4 runs in any ball

Hello everybody my query is regarding the number of positive integral solution. In the sport of cricket, find the number of ways in which a batsman can score 14 runs in 6 balls not scoring more ...
0
votes
0answers
21 views

How to find the no. Of non negative integral solutions of a equation

I want to find the no. Of non negative solutions of $X+2y+3z=n$ I know how to find the non negative integral solutions of the equations of type $X+y+z=n$ using dividers method that is assume that ...
1
vote
1answer
15 views

Find number of circular arrangements possible

If 20 persons were invited for a party, in how many ways will two particular persons be seated on either side of the host in a circular arrangement? According to me the answer should be $17!.2!$. But ...
0
votes
2answers
9 views

partial DAG and number of linear orders

Let $>$ be a linear order relation over a set $A$. Consider the graph $G$ that represent the transitive closure of $>$. Obviously $G$ is directed and acyclic. Given a set of edges ...
1
vote
1answer
26 views

Approximation of combination $ {n \choose k} = \Theta \left( n^k \right) $?

Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it? Note: $k$ is not a function of $n$. Note: Observed it here (page 5): ...
-2
votes
0answers
22 views

Bivariate Discrete question [on hold]

Suppose we select with replacement n marbles from an urn containing 40 red marbles, 25 yellow marbles and 35 blue marbles. Let Y1 = the number of red marbles selected, Y2 = be the number of yellow ...
0
votes
1answer
13 views

How many different sets of 8 elements can I pick if I am picking from a bag of 1681 elements probability and counting [on hold]

I have 1681 points and trying to see how many different constellation of 8 points I can have to see if it is feasible to try out all possibilities to find the best. It's actually a Communication ...
1
vote
0answers
52 views

VERY Challenging Recurrnce Relation Problem

I am starting out with the following: $$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = \sum_{c=0}^n g(x)^{f(x)-c}\lambda_{n,c}(x) $$ Therefore: $$ \frac{d^{n+1}}{dx^{n+1}}[g(x)^{f(x)}] = ...
2
votes
1answer
32 views

Expected number of trails to get $n$ heads in a row with an increasing biased coin.

Assume that we have a biased coin with probability $p_1$ of getting H and $1−p_1$ of getting T on the first trial, $p_2$ of getting H and $1−p_2$ of getting T on the second trial and so on such that ...
1
vote
1answer
21 views

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

Let $[n+1]$ be the set defined by $[n+1]=\{1,2,\ldots,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 ...
2
votes
0answers
18 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 ...
2
votes
3answers
64 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 ...
3
votes
1answer
44 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
27 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
12 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
38 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
28 views

Number of functions $f:\{1, 2, \ldots, n\} \to \{0, 1\}$ that assign $1$ to exactly one positive integer less than $n$

**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
7 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
26 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 ...
4
votes
1answer
24 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 ...
3
votes
2answers
73 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,..) .
3
votes
1answer
69 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 ...
1
vote
1answer
51 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
20 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
15 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
45 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
10 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
17 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
35 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
32 views

Ho many nonnegative integer solutions does the equation $2x_1 + 2x_2 + x_3 + x_4 = 12$ have? [on hold]

How many nonnegative integer solutions are there to the equation: $2x_1 + 2x_2 + x_3 + x_4 = 12$?
0
votes
1answer
39 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
24 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 ...
3
votes
1answer
43 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
22 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
27 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
69 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 ...