# Tagged Questions

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.

126 views

### derangements practice question 3

This is a practice question for derangements. The text I have only has half a page on derangements and that doesn't help me solve this question. For positive integers $1,2,3\cdots(n-1),n$ there are ...
100 views

### Combinations in application - “smooth order”

I have a long winded question here, so I will state the final question first - then my long explanation: Is there a program, method, code, calculation in which I can determine a complete "smooth" ...
181 views

### Probability in ball coloring

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ...
644 views

### Prove that $P(X)$ has exactly $\binom nk$ subsets of $X$ of $k$ elements each.

Let set $X$ consist of $n$ members. $P(X)$ is power set of $X$. Prove that set $P(X)$ has exactly $$\binom nk = \frac{n!}{k!(n-k)!}$$ subsets of $X$ of $k$ elements each. Hence, show that $P(X)$ ...
85 views

### new definition in graphs

I was reading a topic on wikipedia. There a product "corona product" was defined as : Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and ...
421 views

### Ramsey's theorem [closed]

I'm reading introduction to combinatorics and encountered an exercise I couldn't answer Let S be a set of six points in the plane, with no three of the points collinear. Color either red or blue each ...
150 views

### GRE test prep question [LCM and divisors]

Let $S$ be the set of all positive integers $n$ such that $n^2$ is a multiple of both $24$ and $108$. Which of the following integers are divisors of every integer $n$ in $S$ ? Indicate ...
44 views

### Dividing to exclude order in counting

I was studying up on counting. I came across this document, which says: If you choose two things separately and multiply, your answer will include order. If you don't want that order, you either ...
927 views

### Show that triangle-free planar graphs are four-colorable

Prove that every planar graph without a triangle (that is, a cycle of length three) has a vertex of degree three or less. Then, prove that all planar graphs without triangles are four-colorable ...
157 views

### Theorem 1 chapter 8 of Fulton's Young Tableaux

I am reading Theorem 1 on page 110 of Fulton's Young Tableaux and have several questions on it. Let $E$ be a free module on $e_1,\ldots,e_m$ (for our purposes $E$ being a finite dimensional complex ...
88 views

### a basic doubt about definition in graph theory

Friends, I have a very basic doubt about neighborhood of a vertex. I was going through some pdf and their it was written about i-th neighbor of v, $v \in V(G)$. Can anybody explain me the term i-th ...
86 views

### Sets of subsets on $n$ objects

Given a number $n$, I want to have all the sets of subsets of $n$ elements in a way that adding all of them include all $n$ elements. Let's say a set has 2 elements: $\{a,b\}$. For here we can have ...
338 views

181 views

### Yahtzee Bar Game

A bar near where I work has a game where you pay $5$ dollars which gets you two chances of rolling $5$ dice and if roll results in all of the dice having the same number you win the running pot, ...
108 views

### Optimizing a Dynamic Balanced Tournament

I would like to create a schedule for a set of players to play a tournament. The players are divided into a number of teams, and each round consists of the matches between these teams. The type of ...
11k views

91 views

### Simple Paths Along Vertices

Let $v$ and $w$ be distinct vertices in $K_n$, $n\geq 2$. Show that the number of simple paths from $v$ to $w$ is $$(n-2)!\sum_{k=0}^{n-2}\frac{1}{k!}.$$ A path with no repeated vertices is called a ...
82 views

### What is the probability that the robot steps on the bomb?

Suppose a robot is initially placed at $0$ on the number line, and is programmed to take steps of integer length in the positive direction between $1$ and $k$, inclusive, where $k$ is a positive ...
641 views

### Negative binomial distribution - deriving of the p.m.f. combinatorially

Let $X$ be the number of trials preceding the $k$th success in a sequence of independent Bernoulli trials each with probability of success $p$. Then $X$ has a negative binomial distribution with ...
This is how my professor derived it: Taking the case of all valid arrangements of $n$ '(' and $n$ ')', he says that for every invalid arrangement, there will be a ')' at some $k^{th}$ position where ...