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
votes
0answers
17 views

To write the sum of the given series

$\sum_{r=1}^{y}\left(\begin{array}{c} x-1 \\ r \end{array}\right) \left(\begin{array}{c} y-1 \\ r-1 \end{array}\right) a^r * b^{N-r-1} $ where x+y=N
2
votes
2answers
23 views

a multiset where two consecutive numbers must be dissimilar

I am currently looking for a solution of following problem: Let us assume that we have found types, e.g., S = {1, 2, 3, 4} and we are planning to create a multiset, M, by picking values from S with a ...
1
vote
0answers
11 views

3 cards of 52, Making Straight or better with 2 imaginary wild Jokers

Random shuffled 52-card deck, 3 cards are dealt. Find a probability of making 5-card Straight or better with imaginary 2 wild Jokers. In order to make Straight or better, we need the three cards to ...
0
votes
1answer
18 views

How many ways to order 26 letters so that the strings lift and graph are not included?

I just need to subtract the letters used by the strings? or is just removing the ordering of the words?
0
votes
3answers
42 views

How many functions $f: A \rightarrow \mathbb{N}$ are there that satisfy the equation

How many functions $f: A \rightarrow \mathbb{N}$ are there with $A:= \{1,\dots,5\}$ where the following equation is satisfied: $$f(1) + f(2) + f(3) + f(4) + f(5) = 20$$ How can I find the number ...
0
votes
1answer
31 views

Difference between “distribution” & “arrangement”.

Number of ways of Arrangement of $n$ different things into $r$ different groups is $$n!\binom{n - 1}{r - 1}$$. Number of ways of distribution of $n$ different things into $r$ different groups is the ...
0
votes
2answers
19 views

Can someone explain how to find the number of equivalence classes and elements?

I am struggling so much with this topic. Trying to do some practice questions but I don't seem to get it. What I'm working on is Let $A = \{ 1, 2, 3, \dots, 2014 \} = \{ x \mid 1 \le x \le ...
0
votes
1answer
9 views

Does the principle of De Bruijn sequences extend to non-repeating combinations?

The basic principle of the De Bruijn sequence is that for an alphabet of $k$ letters all combinations of $n$-letter words can be found in a sequence of length $k^n$ letters. For example, given the ...
2
votes
1answer
18 views

Summation to count number of strings over N characters?

How many different strings of five characters are there if only lower-case letters or numbers can be used in creating these strings? Here is my solution: There are 26 letters in the alphabet ...
0
votes
0answers
9 views

Permutations containing a given subsequence

Let $f(n)$ denote the number of $4n$-long strings formed from $2n$ a's and $2n$ b's, such that the string contains, as a (possibly non-consecutive) subsequence, a pattern containing $n$ a's and $n$ ...
2
votes
2answers
18 views

Probability of sorting at least one correctly

If I have 5 balls label 1 through 5, to put one in each of 5 boxes also labeled 1 through 5. What is the probability of putting at least one ball in it's matching box? My first approach was to ...
2
votes
1answer
22 views

Questions concerning elements in $F = \big\{f: \{1, 2, 3\} \to \{1, 2, 3, 4, 5\}\big\}$.

a) Find and simplify the number of functions $f \in F$ so that $f(1) = 4$. My attempt: there is $1$ choice for $f(1)$, and $5$ choices for $f(2)$ and $5$ choices for $f(3)$, thus $1\cdot 5\cdot 5 = ...
0
votes
0answers
11 views

Complementary pair of sets

My book repeatedly uses the phrase "contains one of each complementary pair of sets" and I am wondering what do they mean by that exactly? An example, let $(Y,Z)$ be any partition of $X$. Then at ...
1
vote
1answer
22 views

How to solve this equation containing $P(n,r$)?

$P(n,r) := \frac{n!}{ (n-r)!}$ The equation is: $P(n,r) = 42 P(n,3)$ I need to clear the variable $n$. It doesn't matter that it has to be expressed as a function of $r$. I cannot pass the step: ...
1
vote
4answers
80 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. ...
2
votes
1answer
29 views

How many seven digit numbers with distinct digits contain a $3$ but not a $6$?

How many $7$-digit numbers with no repeated digits contain a $3$ but not a $6$? The number does not start with zero. $$7 \cdot P(8,6) = 7 \cdot 20160 = 141120$$ because $3$ can be in $7$ positions, ...
0
votes
1answer
19 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
26 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
71 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
29 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
86 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
17 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
28 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
30 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 ...
-1
votes
0answers
33 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
29 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
24 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
29 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
12 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
427 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?
1
vote
0answers
15 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
21 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
21 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
39 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
20 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
46 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
41 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
30 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
32 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
29 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 ...