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
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 ...
1
vote
2answers
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" ...
0
votes
2answers
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 ...
1
vote
3answers
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)$ ...
2
votes
1answer
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 ...
0
votes
3answers
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 ...
0
votes
2answers
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 ...
3
votes
3answers
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 ...
5
votes
1answer
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 ...
8
votes
1answer
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 ...
3
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
338 views

Why does Pascal's Triangle give the Binomial Coefficients?

An exercise in chapter 2 of Spivak's Calculus (4th ed.) talks about how Pascal's triangle gives the binomial coefficients. It explains this by saying that the relation $\binom{n+1}{k} = ...
4
votes
0answers
99 views

Extracting Taylor coefficients of a quotient

I was wondering if anybody has come across functions of the form $$\Phi_n(z):=\frac{f(z)^{n+1}}{zf'(z)-f(z)}\quad (n\geq 1).$$ Here, $$f(z)=\sum_{k=0}^{\infty} a_kz^k$$ is holomorphic on the open unit ...
4
votes
2answers
991 views

How many combinations of $3$ natural numbers are there that add up to $30$?

How many combinations of $3$ natural numbers are there that add up to $30$? The answer is $75$ but I need the approach. Although I know that we can use $_{(n-1)}C_{(r-1)}$ i.e. $_{29}C_2 = 406$ but ...
1
vote
1answer
93 views

Number of some zero-one matrices

Let $a_n$ be the number of $n\times n$ zero-one matrices such that in any row and any column there are exactly two 1. What is the value of $a_n$ in terms of $n$ ?
1
vote
1answer
68 views

Counting the number of binary partitions of k elements

I have a k elements which I'd like to partition in two groups. Those two groups will be used for decision tree, where each branch is subsequently evaluated. I have a textbook that says the number of ...
5
votes
1answer
156 views

Jacobi-Trudi Identity - Enumerative Combinatorics

The Jacobi-Trudi Identity states that: Let $\lambda=(\lambda_1, \ldots ,\lambda_n)$ and $\mu=(\mu_1, \ldots ,\mu_n)\subseteq \lambda$. Then, $s_{\lambda/\mu} = \det(h_{\lambda_i -\mu_j ...
1
vote
1answer
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, ...
2
votes
0answers
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 ...
6
votes
4answers
11k views

A fair 6 sided dice is rolled 4 times. What is the probability that at least 3 of the numbers will be either 1 or 6?

I'd really love a sanity check here as I walk through what I believe is the solution. Total possible outcomes = $6^4 = 1296$ Possible combinations of 3 rolls being either 1 or 6 = $({}_4C_3)\cdot2 = ...
3
votes
2answers
1k views

number of possible password combinations

There is a computer password , whose restriction is that it . 1)Each character is an upper case alphabet (A...Z) or a digit (0 to 9)) 2) It should be of length 6 3) It should have at least 1 ...
1
vote
1answer
98 views

Pair Permutation of the set of Natural Numbers

Given the set of natural numbers $N$ is it possible to preform a series of operations that would result in a set with all of the different permutations of pairs? Something like: ...
2
votes
1answer
43 views

One graph a subgraph of another?

Consider a graph $G$ on $n$ vertices with minimum degree $\delta$ and with its largest independent set $a>\delta$. Consider the graph $\bar{K}_a \otimes K_{n-a-1}$ (in other words, take a set of ...
3
votes
2answers
57 views

Is there a “natural” way to define a group operation on the set of size-$n$ subsets of a finite set?

It is easy to define a group operation on the set of all subsets of a given finite set S of size n: merely take the exclusive-or (disjoint sum) of the two sets. This is associative, the empty set is ...
0
votes
1answer
379 views

Number of item distributions in buckets of different sizes

Say you've got $B$ buckets, each having a particular discreet capacity $c_b, 1\leq b\leq B$. Then you want to distribute all of $I$ of identical items. How many possible combinations do you have. For ...
1
vote
1answer
68 views

Understanding proof of a theorem

I was going through the cartesian product of graph. There I read the following theorem.... First part of the proof is clear to me. Can anybody explain the converse part to me? I can't get it as ...
2
votes
1answer
50 views

Combination problem with teams.

I am working on the following problem. There are $8$ teams who are going to have $4$ games with every other team. How many games are there going to be in total ? Assuming that a pair is required ...
11
votes
0answers
272 views

Symmetric polynomials

I've got a seemingly simple question that I've become curious about as a result of supervising some undergraduate research. Let's suppose we have some sequence of polynomials $f_0, f_1, f_2, \cdots ...
-1
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
202 views

Problem with proving Catalan number

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 ...
5
votes
0answers
268 views

Which unordered partition of $n$ gives rise to the largest number of ordered partitions?

A quick look at the wikipedia article on partitions of $n \in \mathbb{N}$ shows that the number of ordered partitions is $2^{n-1}$, and the number of unordered partitions is asymptotically $ \sim ...
0
votes
2answers
53 views

Intuition for counting number of pairs

If we have two groups of $15$ students, how can I intuitively see that the number of ways to pair them is $15!$, if we DO consider $(S_i, S_j)$ different from $(S_j, S_i)$?
1
vote
0answers
36 views

Possible number of endofunctors

The discrete category with countably many objects and morphisms has uncountably many endofunctors (= the number of functions from $\mathbb{N}$ to $\mathbb{N}$). Which categories with countably many ...
3
votes
0answers
103 views

Shortest way to convert two formulas using associative and commutative steps

You have two formulas in which you add $n$ variables. The variables in the two formulas are the same, but they may be in a different order and the parenthesis may be different. As an example I will ...
3
votes
1answer
188 views

How to write $K$ as sum of $N$ integers?

How to write integer $K$ as sum of $N$ positive integers with minimum variance? Obviously when $N|K$ the solution is each of integers being $\frac KN$ and the variance would be zero. But how about ...
5
votes
0answers
176 views

How to partition $S$ in this way?

Assume: $$ P =\{p_1,p_2,\cdots,p_K\}\subset \{1,2,\dots,N\},\quad |P| = K, \qquad x \in \mathbb{R}_+^K , \qquad w = e^{-j\frac{2\pi}N} $$ and, $$ f(l) = \sum_{i=1}^K \sum_{j=1}^K x_i x_j ...
2
votes
2answers
408 views

inclusion and exclusion practice exercise

This is a practice question. I understand Inclusion and Exclusion but I am having a terrible time setting questions up correctly. This is on of the practice questions in the text. At a flower shop ...
15
votes
1answer
410 views

How find the “how many good dyeing” method

$A_{1},A_{2},\cdots,A_{2013}$ are $2013$ different points placed on the circumference of a circle. Each point is dyed one of three colors: red, blue and green. We call a dyeing method good, if for any ...
5
votes
1answer
178 views

Board $7\times 7$ problem

An aid in this problem: On a board of $7 \times 7$ each box is painted red or blue so that any square on the board has at least two neighboring boxes blue. determine as little blue boxes that can be ...
0
votes
2answers
203 views

Proving that a map formed by a closed curve is always 2-colorable

I need to prove that a closed curve on the plane, which forms a map using its intersections with itself, forms a 2-colorable map. How to approach this problem? I'm thinking of proving that the graph ...
1
vote
1answer
56 views

How many sets give different answers?

Consider a set $S$ of integers taken from $[n]$ and a given threshold $k$. A query $x$ returns true if there exists an $s$ in $S$ such that $s-k \leq x \leq s+k$ and false otherwise. Say that two ...
1
vote
2answers
435 views

When is the number of lattice paths from $(1, 1) \to (x, y)$ divisible by $3$?

Let $S$ be the set of $\{(1,1), (1,−1), (−1,1), (1,0), (0,1)\}$-lattice paths which begin at $(1,1),$ do not use the same vertex twice, and never touch either the $x$-axis or the $y$-axis. Let ...
13
votes
4answers
560 views

Showing that $Q_n=D_n+D_{n-1}$

Let $T_n$ be the set of permutations of $\{1,\cdots,n\}$ which do not have i immediately followed by i+1 for $1\le i\le n-1$, so $T_n=\{\sigma \in S_n: \sigma(i)+1\ne\sigma(i+1)$ for $1\le i\le ...
2
votes
1answer
81 views

Counting the number of distinct integers in a range that fit a specified pattern

I've been thinking about primorials in the context of the twin prime conjecture. I am seeing this primarily as an exercise to improve my intuition about primorials and prime patterns more than the ...
1
vote
0answers
155 views

Generating Function for edge-rooted labelled trees

Let $T_v(z)$ be the (exponential) generating function for vertex-rooted (non-plane) trees. Im trying to construct the generating function $T_e(z)$ for edge-rooted trees from this. I know the ...
1
vote
1answer
92 views

Proof of Nonnegativity Inequality

Prove the Inequality: $$\sum_{i,j}\left ( (PAQ)_{i,j}\frac{B_{i,j}^2}{A_{i,j}}- (PBQ)_{i,j}B_{i,j}\right ) \geqslant 0$$ Given that: $P$ and $Q$ are $n$x$n$ and $m$x$m$ symmetric matrices, $A$ ...
1
vote
0answers
37 views

Routing in a faulty hypercube

Suppose I colored a fraction (say $e$) of the edges of the $n$-dimensional hypercube. (the set $\{0,1\}^n$, with edges between points which differ by a single coordinate) Let $c<0$ be some ...