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)

0
votes
0answers
4 views

Shortest grid walks which

On a grid, $G = (0,0)$, $E = (3,3)$, $F = (6,9)$, $ H = (9,6)$, $ J = (10,12)$. What is the number of shortest grid walks form G to J which: a) go through H but not E b) go through neither E nor F ...
2
votes
1answer
21 views

Number of anagrams of MISSISSIPPI that begin with $2 P$'s

I'm checking solutions for one of my math homeworks and it says that the # of anagrams of MISSISSIPPI that begin with $2 P$'s is $\frac{10!} {4! \cdot 4!}$ My approach to this was to take out the $2 ...
1
vote
0answers
17 views

Combinatorics - Integer sided triangles with integer median

The original problem states: "How many integer-sided triangles $(a,b,c)$ with an integer median $m_{c}$, with $a \leq b \leq c \leq N$ exist for a given $N$?". I've managed to get it down to a ...
0
votes
1answer
12 views

Use induction to figure out the number of handshakes in a party

Every arriving guest shakes hand with everybody else at a party. If there are n guests in the party, how many handshakes were there? Proof by using induction. My approach to this problem was to write ...
0
votes
0answers
11 views

How to count the number ways to place `k` identical balls in `n` bags when order matters?

I understand that to count the number of s selections from r possibilities, disregarding order, we can use the formula ...
1
vote
2answers
32 views

How would you go through this combination/ permutation problem

A market has 30 different pants and 12 different hats. You want to to get 3 different pants and 2 different hats. How many ways can you make this purchase? I assume this is a combination, but stuck ...
2
votes
0answers
14 views

computing characteristic polynomial of hyperplane arrangement

The following problem comes from Richard Stanley's $\textit{Enumerative Combinatorics}$ vol. 1, 2nd ed. It is problem 114 (c) in Chapter 3. Let $\mathcal{A}$ be a hyperplane arrangement in ...
-4
votes
0answers
23 views

Finding the modulo of 801 [on hold]

If $d_{k}(m)$ is the number of divisor of m that are congruent to $k$ modulo $4$. How can I find $d_{1}(801)$ and $d_{3}(801)$ .
0
votes
0answers
10 views

Help needed for statistical analysis of pitch class sets

Within Music Analysis, there is a quite mathematical type of analysis which looks at pitch class sets ($pcs$), not surprisingly known as pitch class set analysis. See ...
1
vote
3answers
201 views

How would I prove this strange combinatorial identity?

I came across a combinatorial identity today but have no idea how to handle the $\frac{1}{i+1}$ term: $$\sum_{i=0}^m {m \choose i} (-1)^i \frac{1}{i+1} = \frac{1}{m+1}$$ How would I prove it?
0
votes
0answers
8 views

Self-Avoiding Walk incorporating diagonals

How many paths are there between $(0,0)$ and $(n,n)$ if you include all eight common cardinal directions: North, East, South, West, Northeast, Northwest, Southeast, and Southwest. The only condition ...
2
votes
2answers
18 views

Proving cycles in graph

I have the problem: Let $d>1$ be an integer. Prove that if every vertex of a graph $G$ has degree at least d, then G contains a cycle of length at least $d + 1$. I'm pretty sure this can be done ...
2
votes
2answers
18 views

Number of Partitions in which the Two Largest Parts are Equal

Show that for any positive integer $n$, the number of partitions of $n$ in which the two largest parts are equal is $p(n) − p(n − 1)$. What I have so far: We can construct a bijection from the set ...
0
votes
1answer
12 views

Applying multiplication principle to counting subsets

In my textbook MP is strictly reserved to counting lists. Does what I do below to count subsets work? Consider $3$ men(Ace, Bob, Corry) and $3$ women(Ann, Beth, Candace). Suppose we need to choose a ...
0
votes
0answers
16 views

Lower bound for the chromatic number of $\mathbb{R}^n$

I'm going through a proof that of the following lower bound for the chromatic number of $\mathbb{R}^n$: $$\chi(\mathbb{R}^n) \geq (1.2 + o(1))^n$$ At some point in the proof we get that ...
0
votes
1answer
18 views

Representing a positive $x$ with a generating function

If we want to find the integer solutions of $x_1+x_2+x_3=n$ such that $x_1$ is positive using a generating function. We would first make the parentheses for each $x_i$, for $x_{2,3}$ it would be the ...
2
votes
2answers
35 views

Trying to understand the formula for counting multiset permutations

In how many ways can we plant $5$ red, $3$ yellow and $2$ white flowers in a row? The answer is $\frac {10!}{(5! \cdot 3! \cdot 2!)}$. So it looks like we are dividing out the redundant ...
3
votes
1answer
19 views

Selecting “either representative” Permutation

A Chess club consisting of $14$ Math majors, $11$ EE majors and $11$ CS majors. In how many ways can the club select a president and vice president if either the president or the vice president must ...
4
votes
1answer
36 views

Permutations and Combinations exam question

Before I proceed with my queries I think it's best to present the question at hand. A class consisting of 4 males and 12 females in randomly divided into 4 groups of 4. What is the probability ...
0
votes
2answers
32 views

Probability to get from point A to point B.

In the photo each dot is a city and each blue segment a road. Each road is blocked with probability 1/3 and free with probability 2/3 (independence among all roads). What is the probability that it is ...
2
votes
1answer
23 views

How to deduce the formula “distribution” in groups? What is the difference between “distribution” & “arrangement”?

The number of ways in which $n$ different things can be distributed into $r$ different groups is $$r^n - \binom{r}{1} (r - 1)^n + \binom{r}{2} (r - 2)^n + \ldots + (- 1)^{r - 1} \binom{r}{r - 1}$$. ...
2
votes
2answers
30 views

binomial sum binomial (a + k , a)

Anyone know a way to compute such a sum : $$S = \sum_{k=0}^{n}\binom{a+k}{a} $$ I encountered this sum in a problem in which $a=7, n=7$. In this case the sum can be computed by hand, but I was ...
2
votes
1answer
26 views

How to deduce the formula for arrangement in groups?

The number of ways in which $n$ different things can be arranged into $r$ different groups is $$n! \cdot \dbinom{n - 1}{r - 1} $$. This is the quote from my book. However, it didn't offer any ...
4
votes
0answers
19 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
2
votes
1answer
44 views

How many odd numbers can be formed using the digits $0, 4, 5, 7$?

How many odd numbers can be formed using digits $0,4,5,7$. I am getting answer $12$ but the actual answer is $14$.
1
vote
0answers
7 views

Partitioning a graph such that size of cut is maximum for number of vertices odd

Given a graph $G$ with $n$ vertices and $m$ edges, a cut $C$ of the graph are two disjoint subsets of the vertices $V_1$ and $V_2$ such that number of edges from $V_1$ to $V_2$ is maximum. This number ...
2
votes
0answers
10 views

Nice embedding of the permutohedron of order $n$ in ${\mathbb R}^{n-1}$

The permutohedron $P_n$ of order $n$ ($n\geqslant 2$) is the convex hull of the points $P_\pi=(\pi(1),\dots,\pi(n))$ where $\pi$ ranges over all permutations of $\{1,2,\dots,n\}$. Obviously, since ...
1
vote
2answers
29 views

Probability - very difficult combinatorial question - don't have the theoretical background

Combinatorics - a (very) old question (which I hope I have remembered correctly) from a Cambridge Math Tripos. "A student sits 6 examination papers, each worth 100 marks. In how many possible ways can ...
-2
votes
0answers
23 views

How to evaluate this counting problem

40 slips of paper numbered 1 to 40 are placed in a hat and two are drawn out. How many different unordered pairs of numbers can be drawn. I assume this is a combination type of prob since order is ...
-2
votes
1answer
23 views

number of strings of length n with an odd number of 0's

I need to find the number of strings of length n from the alphabet {0,1} that contain an odd number of 0's. Can anyone help? Thanks!
2
votes
3answers
33 views

Steiner Triple System

A Steiner Triple System, denoted by $STS(v),$ is a pair $(S,T)$ consisting of a set $S$ with $v$ elements, and a set $T$ consisting of triples of $S$ such that every pair of elements of $S$ appear ...
2
votes
1answer
27 views

Four different green balls and red balls

In how many ways can $4$ different Green balls and $4$ different Red balls be Distributed to $4$ persons equally such that each will get balls of same color. My Try: Let Green balls be $G_1$, $G_2$, ...
2
votes
1answer
59 views

composition of an integer number

Given two positive integers $m$ and $n$. I would like one special non-negative solution to the following system (which is related to a composition of an integer number): $$\begin{cases} \sum a_i = m ...
-1
votes
1answer
24 views

Combinatorial Proof with Integer Partitions

Give a combinatorial proof of the equality $p_{n}(2n) = p(n)$. I know I have to do some kind of bijection, but I am new to integer partitions and I do not have a book for this class... ...
1
vote
2answers
38 views

Circular arrangements of identical objects [duplicate]

Q> In how many ways can 5 identical red beads, 3 identical green beads and 2 identical blue beads be arranged in a necklace?
2
votes
2answers
29 views

Compute Using Binomial Theorem [duplicate]

$$\sum_{k=1}^{10} \binom{10}{k} $$ I know the answer is $2^{10} - 1$ but I don't know how to get to the answer.
2
votes
1answer
25 views

Changing order of summation including a min in the summation

Lets say I have the following expression: $$ h(x) = \sum_{k=1}^n \sum_{v=1}^{\min\{k,j\}} \frac{(-1)^{n-k}k!}{(k-v)!} {n \brack k}f(x)^{k-v} B_{n,v}^f(x) $$ Now my goal is to have the $v$ ...
2
votes
2answers
55 views

What is the probability of a randomly chosen bit string of length 8 does not contain 2 consecutive 0's?

Just what the title says, I'm trying to determine the probability of a randomly chosen bit string of length $8$ containing $2$ consecutive $0$'s. I've determined the total number of possible bit ...
2
votes
3answers
78 views

Number of functions verifying $f(f(x))=f(x)$.

Find the number of functions $f:\{1,2,3,4\}\to \{1,2,3,4\}$ that verify $f(f(x))=f(x)$. I'm not sure if the answer is $41$ or $29$.
-2
votes
0answers
21 views

Ribbon and colours [on hold]

A ribbon is composed from 9 square fabric pieces (i.e. is $1\times9$ rectangle). How many different ribbons can be made if there are fabrics of two colors and $5$ cells should be red and $4$ cells ...
0
votes
1answer
35 views

Recurrence relation for a mortgage

Find a recurrence relation for the amount of money outstanding on a \$40,000 mortgage after n years. The interest rate on the mortgage is 10% and the yearly payment is \$2,000( the yearly payment is ...
-2
votes
0answers
28 views

Polya theorem and necklaces [on hold]

How many $10-$ bead necklaces can you make out of $2$ red bead, $3$ blue beads and $5$ white beads $|G| = |D_{10}| = 20 $
2
votes
1answer
22 views

Combinatorics/Probability unordered lists

I don't really understand these unordered lists problems such as... Q: John goes to a store and buys 10 pieces of fruit from the selection of apples, bananas,peaches and pears at random. What is the ...
-1
votes
1answer
31 views

Pigeonhole principle subsets question [on hold]

A set X has 11 elements. Prove that in any 10 4 element subsets which can be formed from X, some two subsets must have two common elements.
2
votes
1answer
37 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
-1
votes
1answer
39 views

To add the following pair of combinatorials

How to write sum of these combinatorials as one combination term $$\binom{N-1}{y} + \binom{N-2}{y-1}$$
2
votes
1answer
15 views

number of weak compositions modulo prime $p$

For $n\in \mathbb{N}$ and some prime $p$, consider $(\mathbb{F}_p)^n$. Is it known how many weak compositions $$x_1+x_2+\ldots +x_n\equiv 0 \pmod p$$ in $\mathbb{F}_p$ there are, where $(x_1, \ldots, ...
1
vote
1answer
16 views

How can we tell from looking at a problem that multiplication principle fails to solve it? And why does MP fail(?) in the first place?

Three officers—a president, a treasurer, and a secretary— are to be chosen from among four people: Ann, Bob, Cyd, and Dan. Suppose that Bob is not qualified to be treasurer and Cyd’s other ...
5
votes
0answers
49 views

In how many ways can $1000000$ be expressed as a product of five distinct positive integers?

I'm trying to solve the following problem: "In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?" Here is my attempt: Since $1000000 = 2^6 \cdot ...
0
votes
1answer
22 views

Rectangle tilling with smaller rectangles

To find the no of ways a rectangle of size 2 $\times $ n can be filled using 1 $\times $ 2 and 2 $\times$ 2 pieces. $$\quad$$ I tried to solve it as a recurrence relation, $a_{2 \times (n+2)} = a_{2 ...