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
30 views

Let $A = \{1, 2\}$. How many subsets $X$ of $S$ are there so that $XRA$?

Let $S = \{1,2,3,4,5,6,7,8,9\}$. Define a relation $R$ on $\mathcal{P}(S)$ by: for any $X,Y \in \mathcal{P}(S)$, $XRY$ if and only if $X \cap Y \neq \emptyset$. Let $A = \{1, 2\}$. How many ...
0
votes
1answer
27 views

How many equivalence classes does this set have?

Let be $ \underline{7}$ ={1, 2, 3, 4, 5, 6, 7} $ $How many elements does the equivalence $\rho \subseteq \underline{7} \times \underline{7} $ have if (1) it consists of 2 equivalence classes, and ...
-1
votes
0answers
12 views

Combinations OR Decision tree ? Six Spices - Total flavors

this is a simple question for which I'm trying to reason. Suppose you have 6 spices, what is the possible number of flavors you can make ? You may assume that you can only combine one spice once to ...
0
votes
1answer
40 views

counting the number of possible results

It's a game I've seen and I know the algorithmic solution, but does it have a mathematical solution? You have a list of numbers 1-3 (for example) and two operators -,+. How many results can I get ...
3
votes
1answer
47 views

Number of vertices of a random convex polygon

Take $n>2$ random points, chosen independently with uniform probability on $[0,1]\times[0,1]$. What is the probability $P(n,k)$ that the convex hull of these points is a polygon with exactly ...
0
votes
2answers
65 views

Can anyone explain why does this solution to probability problem true?

Consider the general situation where a box contains $N$ balls, of which $r$ are red and $N − r$ are white, and where balls are drawn without replacement until n reds have been selected. We wish ...
2
votes
3answers
47 views

Proof: Sum of the combination of the these numbers are not equal.

You have a set (wallet) of 5 coins: $\{1, 5, 10, 50, 100\}$. Now there are clearly $2^5$ subsets of this set since the decision needed to build a subset is whether to include each element or not (can ...
0
votes
1answer
26 views

Partition of number $N$ such that smallest number in each partition is not less than $K$

For a given $N$ and $K$, we need to compute the number of partitions of $N$ such that the smallest number in each partition is not less than $K$.How can this can be accomplished using combinatorics ? ...
5
votes
3answers
207 views

If $x+y+z=3k$, where $x, y, z, k$ are integers, prove that $x!y!z! \geq (k!)^3$

If $x+y+z=3k$, where $x, y, z, k$ are integers, prove that $x!y!z! \geq (k!)^3$ Well I was able to prove this intuitively, but what i need is a rigorous mathematical proof. I shall explain my ...
1
vote
2answers
32 views

What is an intuitive explanation of the combinations formula?

I perfectly understand the permutations formula i.e. if you have $n$ things how many ways can you rearrange it if taken $k$ at a time (or if you have $k$ slots)? So you draw the following tree. And ...
1
vote
3answers
30 views

Generating function, determining coefficient

Here is a question I encountered the other day: Determine the coefficient of $x^{98}$ in the following generating function: $$f(x)=\frac{x}{(1-2x)^{21}}$$ I'm thrown off a bit by the large exponent ...
0
votes
3answers
66 views

What is wrong with calculating the probability this way?

A footbal team is playing a tournament of five matches. The probabilities that they win, draw or lose a match are $\frac{1}{2}, \frac{1}{6}$ and $\frac{1}{3}$ respectively. The result of a match is ...
0
votes
0answers
13 views

Euler circuit of complete graph

For a complete graph $K_p$ where $p$ is the number of vertices, then if $p$ is odd, every vertex has even degree and so every complete graph with an odd number of vertices has an Euler circuit. But ...
1
vote
0answers
15 views

Chromatic index of complete graphs using line graphs

I'm interested in computing $\chi'(K_n)$ from the relation $$\chi'(K_n)=\chi(L(K_n)),$$ where $L$ denotes the line graph operator. Is there a good argument to do this? (The answer is of course $=n-1$ ...
1
vote
2answers
93 views

8 character password

Everyone is asked to create a new 8 character password with at least one number and exactly one special character with the remaining characters being lowercase letters. How many possible passwords are ...
0
votes
2answers
31 views

Number of cycles of length 3 on n vertices. Cycles of length 4?

How many cycles of length 3 are possible for a complete graph with n vertices? Cycles of length 4? My first thought for both scenarios was $n \choose 3$ * $\frac{1}{2}$ ->(cycle lengths of 3) and $n ...
2
votes
1answer
22 views

Number of paths of length three in $K_4$

How many paths of length $3$ can be made from $K_4$ where $4$ represents the number of vertices? I believe the answer is $12$ just by counting the number of different combinations of paths with ...
0
votes
0answers
15 views

Find the number of triangles formed by the vertices of a polygon of $2n+1$ sides each containing the centre of the polygon.

Find the number of triangles formed by the vertices of a polygon of $2n+1$ sides each containing the centre of the polygon. I found that for $2k+1$ sides it is coming $1^2+2^2+3^2+..k^2$.I wanted to ...
3
votes
0answers
21 views

Writing a generating function

I came across the following question and it's a bit different from what I'm used to... Write a generating function for each of the following: 1) You are making an Easter basket with at most two ...
-2
votes
1answer
37 views

Number of paths of length 2 in a complete graph containing n vertices [closed]

How many paths of length 2 does $K_n$ have? Where n is the number of vertices. I initially thought it should just be $n \choose 2$ but was told that was incorrect? Is there something I'm missing ?
1
vote
2answers
19 views

A couple of inequality / similarity that don't make sense to me.

I was reading thru the proof for a combinatorics problem, but there were a couple places in there that gave me pause. In particular, one part of the proof had the following: $${n \choose ...
0
votes
2answers
11 views

Exponential generating function - what happens when there is a leftover term?

Find the coefficient on $x^2/2!$ in the following generating function: $$xe^{3x}-x^2$$ I got this far: $$x\sum_{n=0}^{\infty}\frac{3^nx^n}{n!}-x^2=\sum_{n=0}^{\infty}\frac{3^nx^{n+1}}{n!}-x^2$$ So, ...
1
vote
0answers
31 views

Proving the Pigeonhole Principle

I am looking to prove the Pigeonhole Principle by proving the following claim: Let $A$ be a set with $m$ elements, and let $B$ be a set with $n$ elements, where $m,n\in \omega$ and $m > n$. ...
0
votes
2answers
27 views

Probabilities of choosing specific members for a committee

Problem: From a 10-person group, a 3-member committee is to be formed. Let A and B denote two different people in the group. Find the probability that: (a) A is chosen (b) A and B are both chosen ...
0
votes
3answers
47 views

Explanation of an Easy Proof of Variance of Bernoulli Trials

I am taking a course in Combinatorics, and I've got two proofs I can use to support the Bernoulli trial variance formula, $\operatorname{var}(X) = np(1-p)$, and I would like to use the one where I ...
0
votes
2answers
19 views

The general expression of the possibility of n events union?

Suppose all the events are independent. $P(A \cup B \cup C)= P(A) + P(B) + P(C)- P(AB) - P(AC) - P(BC) + P(ABC)$ When there are $N$ events together, what's the general expression of the possibility? ...
0
votes
0answers
22 views

Understanding Ziv's proof of zero sum problem .

I was going through the proof of zero sum problem in one dimension as provided by Abraham Ziv. The problem statement is to prove that given a set of $2n+1$ integers, we can find at least $n$ integers ...
0
votes
1answer
19 views

number of ways to put N labelled balls in N labelled boxes so that labels don't match? [duplicate]

I have N distinct balls labelled 1 to N, and associated N boxes labelled 1 to N. How many different ways can I place all balls into the boxes (one ball per box) so that there is no ball-box label ...
0
votes
3answers
31 views

Solve the following recurrence relations

Solve the following recurrence relations: $\qquad$a) $a_n = a_{n-1} + 3(n-1), a_0 = 1$ $\qquad$b) $a_n = a_{n-1} + 3n^2, a_0 = 10$ I know that $a_n = a_{n-1} + f(n)$ = $a_0 + \sum_{i=0}^n ...
0
votes
1answer
18 views

Spectrum of Line graph of regular graph

Definition: Let $G$ be a graph, the line graph of $G$ denoted of $L(G)$ is defined as follows: -The vertices of $L(G)$ are the edges of $G$ -Two vertices of $L(G)$ are adjacent iff their corresponding ...
3
votes
0answers
24 views

How to call a partition of $X$ which consists of all singleton subsets of $X$? [duplicate]

In other words, if $X$ is a set, then how do we call $Y=\{\{x\}:x\in X\}$? $\{X\}$ is already named the trivial partition, so that cannot be it. Complete partition and total partition did not yield ...
0
votes
0answers
19 views

Fundamental Groups of a Simplicial Complex and the Underlying Space

Now I know how the fundamental group of a Simplicial Complex is defined, as well as that of a Toplogical Space. Could someone explain the process of how we prove that for a simplicial complex $X$ , ...
1
vote
1answer
32 views

Choosing spread out elements

Is there an explicit formula that I'm missing, for the total number of choices from a set $S = \lbrace 1, 2 , \dots , n \rbrace$ such that for every choice $C \subset S$ the following holds: $\forall ...
0
votes
1answer
47 views

How does $a_{n+1}-2a_n=2a_{n-1}$?

I'm solving non-homogeneous linear recurrences for my combinatorics class and my teacher skipped a bunch of steps in his notes, so I am trying to make sense of a particular "step" he took. We were ...
0
votes
1answer
30 views

In a large corporation withnsalespeople, every 10 salespeople report to a local manager, every 10 local managers report to a district manager…

In a large corporation with n salespeople, every 10 salespeople report to a local manager, every 10 local managers report to a district manager, and so forth until finally 10 vice-presidents ...
2
votes
1answer
44 views

How to prove that $\binom{X+L-1}{L-1} \ge (X-L\times N)^{L-1}$?

I would like to prove the following expression: $$\binom{X+L-1}{L-1} \ge (X-L\times N)^{L-1}$$ , where $X$, $L$ and $N$ are positive integers. Please help me to prove with the following case. $X\ge ...
0
votes
2answers
59 views

How to show that ($m,n\in \mathbb{N}, m>n$) ${\frac{ \left( m+n \right)^{m+n}}{m^{m} n^{n}}} > 2^{2n}$ [closed]

I would appreciate if somebody could help me with the following problem: Q: How to show that ($m,n\in \mathbb{N}, m>n$) $${\frac{ \left( m+n \right)^{m+n}}{m^{m} n^{n}}} > 2^{2n}$$ I try ...
3
votes
1answer
38 views

Distribution of 10 different books to three students.

Could someone confirm my solution to this combinatoric question? Question: In how many ways can 10 different books be distributed to three students so that each student receives at least three ...
4
votes
1answer
44 views

30 ball bearings, five are defective. Choose 10 probability.

Could someone confirm my solutions for a combinatorics question? Question: In a group of 30 ball bearings, 5 are defective. If 10 of the ball bearings are chosen, what is the probability that: ...
0
votes
2answers
34 views

Help deriving a probability

Let's say I have 6 balls and 3 containers which are initially empty (A, B, and C). If the 6 balls are distributed randomly across the 3 containers, what is the probability that a specific container ...
0
votes
0answers
13 views

Possible Combinations with unique sequences at positions

I'm trying to find all possible combinations of $n$ elements where the sequences $(n_i, n_{i+1})$ are unique at their positions and have literally no idea how to do that since my knowledge in ...
0
votes
2answers
37 views

How many subsets of four numbers from the set are there in which the sum of the largest and smallest number in the subset is 15?

How many subsets of four numbers from the set $2,3,4,5,6,7,8,9,10,11,12,13,14$ are there in which the sum of the largest and smallest number in the subset is $15$? The answer is: ...
0
votes
1answer
41 views

How many arrangements of letters in ORIGINATING have ALL of the following properties?

How many arrangements of letters in ORIGINATING have ALL of the following properties: (i) there are at least two letters between each I, (ii) begins or ends with an I (does NOT begin AND end with an ...
1
vote
1answer
51 views

Summing $n$ numbers so that they equal $0 \mod{n}$

Let $A_n=\{(a_1,a_2,\dots,a_n) :\sum_{i=1}^na_i=0\mod{n}\}$, where $a_i\in[n-1]$. How many elements are in $A_n$? My initial attempt was a stars-and-bars argument. For example, let $n=4$. Then we ...
1
vote
2answers
42 views

Lucas numbers proof

I'm running through some example problems and encountered this one: Define a sequence of integers $L_n$ by $L_1=1, L_2=3, L_{n+1}=L_n+L_{n-1}.$ Show that $L_n = a\cdot ...
1
vote
1answer
36 views

Bag of 24 distinct objects, four colors, six objects per color, select three (probability).

Could someone confirm my combinatorics solutions for this question? Question: A bag holds 24 different objects, of which 6 are orange, 6 are white, 6 are yellow, and 6 are red. If a juggler selects ...
1
vote
1answer
54 views

Exactly two vowels in an eight-letter string.

Could someone confirm my combinatorics solutions for this question? Part 1 How many eight letter strings of letters contain exactly two vowels? Solution: Choose two spots out of eight possible ...
5
votes
1answer
68 views

How can I get f(x) from its Taylor series ???

I know how to get a Taylor series when $f(x)$ is given. I have to find $f^{(k)} / k!$. But how can I get $f(x)$ from its Taylor series? The problem is $$f(x) = \sum_{n=0}^{\infty} C_n x^n,$$ where ...
1
vote
1answer
16 views

Finding the number of ordered pairs of integers (Discrete Maths)

Let $k$ and $n$ be positive integers such that $k\le n$ (i) How many ordered sequences of integers ($a_{1}$,$a_{2}$,...$a_{k}$) are there such that $a_{1}$,$a_{2}$,...$a_{k}$$\in $(1,2...n) (ii) How ...
1
vote
1answer
41 views

Must start with “M”, how you justify it?

Question: How many different letter arrangement can be made from the letters of "Mathematics" that must start with "M"? Answer is $907200$. My understanding is: Total $11$ alphabets Total $2$ ...