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
0answers
12 views

Bob starts with \$20. Bob flips a coin. Heads = Win +\$1 Tails = Lose -\$1. Stops if he has \$0 or \$100. Probability he ends up with \$0?

I'm working on the extra credit for my Discrete Structures homework, but so far I have been unable to get a handle on the problem, even with help from 3rd parties, so I've decided to turn to you guys. ...
0
votes
1answer
18 views

Finding algorithm to design combinatorics formulae per input data

Problem: calculate how many unique "words" can be made using the letters of your a) name (Kateryna - 8 letters, letter 'a' used twice) b) lastname (Atamanchuk - 10 letters, letter 'a' used 3 times) ...
0
votes
1answer
24 views

Probability of choosing a combination [on hold]

A person has $8$ red pills and $8$ blue pills. He chooses $8$ pills at random. What is the probability that the chosen pills are $4$ red and $4$ blue?
3
votes
2answers
59 views

Problem in deducing the number of onto functions

Let $A, B$ have $m, n$ elements ($m > n$). Therefore, the number of onto functions from $A$ to $B$ is: $$\sum_{k = 0}^n (-1)^k \binom{n}{k} (n - k)^m.$$ How can one use the IE (Inclusion/Exclusion) ...
0
votes
1answer
26 views

Question about counting cards

A standard deck of cards contains $52$ cards divided into four suits: the red suits, hearts and diamonds, and the black suits, clubs and spades. Each suit, in turn, is divided in 13 ordered ranks: ace ...
2
votes
1answer
25 views

Tower of Hanoi variation from Concrete Mathematics - possible arrangements

From Concrete Mathematics, there is a problem that describes a variation of the Towers of Hanoi, where the disks can not move directly from peg $A$ to peg $B$, but must go through a middle peg. ...
2
votes
1answer
59 views

Combinatorics - Integer sided triangles with integer median

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

Binomial distribution tail inequality

Let $X \sim \mathrm{Bin}(n,p)$ does there exist $l$ ideally $l=f(n)$ such that $P(X<l)=o(1)$ in the limit $n\rightarrow \infty$? I'd be looking for the largest possible $l$.
0
votes
0answers
25 views

At a step, we either increment or decrement $t$. If $|t| = x$, the program halts. What is the chance of the program still running after $n$ steps? [on hold]

We start with $t = 0$. At each step, we either increment $t$ with probability $p$ or decrement $t$ with probability $1-p$. If $|t| = x$, the program halts. What is the chance of the program still ...
0
votes
1answer
26 views

How many ways to assign 10 digits to 6 containers.

So if we had 6 containers eg (a,b,c,d,e,f) how many ways could we assign the digits 0-9 to these containers. For example one way might be: a = 4 b = 5 c = 0 d = 3 e = 8 f = 7 Is there a ...
0
votes
0answers
32 views

Forbidden Positions [on hold]

How would you go about doing forbidden positions on a rectangular chessboard? For example, we have a chessboard with $9$ rows and $3$ columns. The first column has $2$ forbidden positions ($X$) in ...
1
vote
1answer
27 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 ...
1
vote
1answer
16 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
16 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
35 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
22 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
28 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
11 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 ...
0
votes
3answers
424 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
11 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
20 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
20 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
20 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
21 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
37 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
42 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
37 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
28 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
31 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
28 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
24 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
46 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
8 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
32 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
34 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
28 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
64 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
25 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
40 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
30 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
26 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
64 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
79 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
38 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 ...