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

Find a functional equation for the generating function whose coefficients satisfy the relation

Find a functional equation for the generating function whose coefficients satisfy the relation: $\qquad{}$ $a_n = 3a_{n-1} -2a_{n-2}+2, a_0=a_1=1$ When I solve this, I get the function ...
0
votes
2answers
34 views

Find the price of the bond using its book value

A n year 1000 par-value bond with 8% annual coupons has an annual effective yieled of i, 1+i >0 . The book value of the bond at the end of the third year is 990.92 and the book value of the bond at ...
1
vote
3answers
56 views

Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges. [closed]

Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges. Attempt: I know that i have to... prove that there must be TWO vertices with “red-degree” at ...
0
votes
1answer
27 views

Finding the probability of a random graph?

How do I approach this problem? I am new to the topic and I am having a hard time figuring this out. For Erdos-Renyi graphs on $3$ vertices with parameter p, find the probability there is an edge ...
0
votes
2answers
49 views

Craps probability: What value of x makes this a fair game?

You are playing Craps at the casino. In each round of Craps, two 6-sided dice are rolled. You place a bet as follows: You wager 1 dollar. If a 5 is rolled you win x dollars. If a 7 is rolled, you ...
3
votes
3answers
64 views

How to show that in a subset of [0,1] of measure greater than 0.5, there exist two points at distance exactly 0.1?

My attempt: Let's disregard isolated points as they do not contribute to measure. If our set is union (disjoint) of finitely many, say $n$ intervals, there must be at least ($n-1$) intervals of ...
4
votes
1answer
49 views

Steiner triple system with $\lambda \le 1$

What's the maximum number of 3-sized subsets of $[n]$ that can exist such that no two subsets contain more than one common element? When $n \equiv 1,3 \mod 6$ then this is equivalent to a Steiner ...
0
votes
1answer
18 views

Proof graph theory(length of a path)

In $G$ simple graph every vertex has the degree of $\delta$. Proof, that in $G$ graph there is at most one $\delta$ long path. I think that I should use in some way the Hamilton path, which says ...
2
votes
2answers
32 views

Interpretation of the unsigned Stirling number of the first kind.

Let $C_{2}, C_{3},\dots, C_{n}$ be the directed star graphs: the vertex set of $C_{j}$ is $\{1, 2, \dots, j\}$ and its edge set is $\{(j, i): 1\leq i <j\}$ . Let $c'(n,i)$ be the number of sets $X$ ...
0
votes
1answer
33 views

Single-element version of the Replacement Theorem.

Show that for each pair of bases $B$ and $B'$ of a finite-dimensional vector space $V$, there is a bijection $\phi: B-B' \rightarrow B'-B$ so that for each $x\in B-B'$, the set ...
0
votes
1answer
28 views

Colouring $K_{2s-1}$

Suppose we 2-colour $K_{2s-1}$ such that no vertex has more than one blue edge incident to it, prove that the graph contains a red $K_s$. I've never seen a Ramsey theory question like this and am ...
0
votes
1answer
37 views

There are 56 teams in a knockout tournament, then how many matches has to be played to select the champion?

''There are 56 teams in a knockout tournament, then how many matches has to be played to select the champion?'' I found this in a question paper, and I am stuck to solve this problem. I have ...
1
vote
2answers
14 views

Complete bipartite graph from 2 to m points

How can I show that $K_{2,m}$ is planar for all m? I can't even seem to draw $K_{2,2}$ without intersection and if I draw it as a square then it seems to fail to be bipartite as the second set lies ...
0
votes
1answer
24 views

Making a string with pieces of different length and fabric

You are making a string and have access to pieces of two different lengths, of length 1 inch and of length 2 inch. The 1 inch pieces come in 5 different fabrics and the 2 inch pieces come in 4 ...
1
vote
1answer
61 views

An interesting puzzle from Jiří Matoušek's book

There is an interesting puzzle from Jiří Matoušek's book Invitation to Discrete Mathematics, problem 1.2.8, which confused me lots of time. Divide the following figure into $7$ parts, all of them ...
1
vote
1answer
14 views

Number of faces of connected plane graph with cycles

Suppose $G$ is a connected plane graph with at least $g$ edges containing no cycles of length smaller than $g$, then if $f$ is the number of faces and $e$ is the number of edges then prove that $f ...
0
votes
1answer
21 views

Sampling with replacement

How-many distinct samples of size $n$ can be drawn with replacement from the population ${u_1, u_2,......, u_n}$ of $n$ units ? I have considered the number of ways in which $n$ units can occupy $n$ ...
1
vote
1answer
43 views

On the eigenvalues of “almost” complete graph ?!

Preliminaries: Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$. It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity ...
0
votes
2answers
30 views

UpMultiset Combination-choose 3

Today I saw this question in a book: There are $12$ objects, $3$ of which are alike and the remainder all different. In how many ways can a selection of $5$ be made? I tried to answer: $k=11, ...
0
votes
1answer
28 views

Multiset Combination

How many Combinations can you make with the set {1,1,2,3,4} taken 2 at a time? If I do this in the way I do in Permutation: C(5,2) / 2!, I end up in wrong answer. Actually, there are 7 Combinations: ...
0
votes
0answers
57 views

How to distribute $n$ balls of different kinds among $n$ baskets of different kinds? Non-trivial combinatorics/permutation task

I have a task that I don't know how to approach. There are $n$ baskets of four types; $n$>1000. Each basket fits exactly one ball. Number of balls equals number of baskets. Balls are of different ...
3
votes
1answer
33 views

Collecting integers puzzle.

Given a set of $n$ integers and a starting point, one has to collect all $n$ numbers moving at most a distance 1 from any number previous picked. For example if $n=5$ one solution would be: ...
-2
votes
1answer
50 views

Number of different groups given a list of repeating digits

Suppose that you are given the list[1,1,2,2] . The different groups that can be formed with this list are - ...
0
votes
1answer
55 views

Wood worm in a cube [closed]

A woodworm is sitting at the centre of a cube that's divided into 3^3 identical cubelets. The woodworm can go from the centre of one cubelet to the centre of another in any edge-parallel direction. ...
2
votes
1answer
21 views

Converting Permutations to Combinations: Simple Stats in Practise

In a popular text book there is a question that has bothered me that I am sure is very simple for others and I'm just missing something..... So image $100$ songs and we have $10$ as Beatles songs. We ...
2
votes
1answer
19 views

Probability of alternating colors of cards drawn from a deck

I'm supposed to find the probability that red and black cards strictly alternate when removing a number of cards from a deck, say 12. I've got that the probabilty of removing 6 red and 6 black without ...
1
vote
1answer
19 views

Distribution of linear combination of discrete variables

Assume $X,Y$ are discrete independent random variables with known distribution $P_X(x), P_Y(y)$ and $c_1, c_2$ constants. Can we determine the shape of the distribution of: $Z = c_1~X+c_2~Y$
0
votes
1answer
58 views

while reading $limits$ I thought of this $ \dbinom{x}{y}$ where $y \to x^+$

while reading $limits$ I thought of this $ \dbinom{x}{y}$ where $y \to x^+$, as per my opinion, I think the correct answer to be $undefined$ as $\dbinom{x}{y}$ is defined only when $x \geq y $ but ...
1
vote
1answer
11 views

Generate a unique combination from an index within the number of combinations

I'm writing a program which will use a genetic algorithm optimize neural networks to play tic-tac-toe (That's not related), and I've come across the following problem: I'm looping through every ...
1
vote
1answer
36 views

v1 deg out = zero?

My Attempt Yes it is true. There is one directed edge between two vertices and you can see that there is one vertex that the out-degree is zero. If you want to fix that, you can add a vertex and a ...
7
votes
0answers
84 views

The smallest number that if multiplied by 2 forms a permutation of itself

I am looking for the smallest number larger than $0$ which when multiplied by $2$, forms a permutation of itself. I quickly remembered that the number $142,857$ does that, as well as with all numbers ...
11
votes
0answers
175 views

Dynamically two-coloring a finite graph

Let $G=(V,E)$ be a finite graph whose vertices are going to be colored dynamically. More precisely, consider time periods $t \in \left\{0,1,2\ldots,\right\}$ and for each time $t$ and $i \in V$, let ...
0
votes
1answer
16 views

Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset [n]$, $|S_i\cap S_i|\le 1$ for $i\ne j$

Show ${1\over n}\sum|S_i|=O(\sqrt n)$ where $S_i\subset [n]$, $|S_i\cap S_i|\le 1$ for $i\ne j$. A previous question required showing $|E|\le {1\over 2}(\sqrt{t-1}n^{3\over 2}+n)$, for an $n$-vertex ...
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
28 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
48 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
67 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
208 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
31 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
14 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 ...