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
1answer
126 views

sequences of six digits (0-9)

How many sequences of six digits(0-9) contain at least one 3, at least one 5 , and at least one 8? Can someone please give me a hint?
2
votes
1answer
64 views

How do I do this summation? [closed]

$$\sum_{i=0}^{N-2}\frac{(N-2)!(i+1)(i+2)(i+4)}{2(N-2-i)!N^{i+1}}$$ The answer is N.
1
vote
1answer
26 views

calculate the number of different lottery columns

How many different lottery columns exist(of length $13$,with $1,2 \text{ or } X \text{ at each position}$) ? I have to use this theorem: Let $k$ a natural number and $E$ the set of all different ...
2
votes
3answers
50 views

Counting proof of choosing

I'm doing an exam review without any solutions. I don't know why this is true. $$ ∑_k^n 5^k\binom{n}{k} = 6^n$$
0
votes
1answer
11 views

A question on an asymptotic combinatorial expasion

Suppose we are given $(\lambda a + \bar{\lambda}b+O(\lambda^2))^{n}$, where $0 < \lambda < 1$ and $\bar{\lambda} := 1-\lambda$; also, $0 < a,b < 1$. $O(\cdot)$ is the traditional Big-Oh ...
0
votes
0answers
47 views

About partitions, majorization, and conjugates [duplicate]

I am trying to solve a question of a property of conjugation. What I am trying to show is that conjugation reverses the order of majorization. Let $\lambda$ and $\mu$ are partitions of n and ...
-1
votes
1answer
61 views

chosing between matrix theory and combinatroics

I have to take one more math course to finish my math minor , i am a computer science major and i want to know which course will benefit me more matrix theory or combinatorics and which takes more ...
2
votes
2answers
61 views

In how many ways we can choose $3$ subsets from set $|S| = 20$ …

In how many ways we can choose $S_1$, $S_2$ and $S_3$ from a set which consists of $20$ element, so that : $S_1 \cap S_2 \cap S_3 = \emptyset$
1
vote
1answer
334 views

Number of ways to add up to a number without repetition (order does not matter)?

I have a number x and want to find how many ways there are to add up to that number using the y numbers from numbers 1-z. for example, for x=15 y=3, z=9, there are 8 ways to add up to 15 using 3 ...
3
votes
1answer
86 views

Show the relationship between the trace and the number of 4-cycles

Let $G$ be a k-regular graph. Show the exact relationship between $tr(A^4)$ and the number of 4-cycles in $G$. I understand how $tr(A^4)$ tells us the total number of closed paths of length 4 in ...
2
votes
1answer
177 views

Combinatorics, expected value, drawing balls from a bag, and customer support

It's been a few years since I've done my CS combinatorics stuff so I'm having a major brain fart here. You put n red balls into a bag. Every t hours you select (n/100) balls from the bag. If a ...
0
votes
1answer
65 views

calculate the proportion of n-node trees whose root has only one or two subtrees.

Could we use combinatorics and generating functions to calculate the proportion of n-node trees whose root has only one or two subtrees? Here is what I tried: The combinatorial construction for the ...
1
vote
2answers
53 views

Is $n\binom{\epsilon n}{t}>t\binom{n}{t}$ for large $n$ and fixed $\epsilon$ and $t$

Let $\epsilon$ and $t$ be fixed numbers with $t$ and integer. I came across the following inequality in a counting problem. $$n\binom{\epsilon n}{t}>t\binom{n}{t}.$$ I want to show that for $n$ ...
1
vote
2answers
164 views

Different ways of picking a committee of $12$ women and $10$ men

$12$ women and $10$ men are on the faculty. How many ways are there to pick a committee of $7$ if (a) Claire and Bob will not serve together, (b) at least one woman must be chosen I'm not sure ...
4
votes
2answers
89 views

Calculation a closed form for the sum

Please help me to calculate this sum in a closed form: $$ \sum\limits_{1\leq i_1<i_2<\ldots<i_k\leq n}(i_1+i_2+\ldots+i_k). $$ Here $n$, $k$ are positive integer numbers; $k<n$. I think ...
0
votes
2answers
56 views

Calculating the number of subsets

Let A be a set with n elements. For which n do (exactly) subsets $B_1, \cdots, B_{2^{n-1}} \subseteq A$ exist, so $B_i \neq B_j, B_i \cap B_j \neq \emptyset$ for $1 \leq i < j \leq 2^{n-1}$ ...
4
votes
4answers
206 views

How to calculate the following sums?

I would like to know of a way to evaluate the following two for arbitrary $n$. $$\sum_{i=1}^ni!\,, \quad \sum_{i=1}^n \frac{n!}{i!}. $$
1
vote
0answers
101 views

Number of permutations with a given constraint

Let $\Pi$ be the set of all permutations of the set $\left\{1 \ldots n\right\}$. Of course I know the cardinal of $\Pi$ is $n!$. I am trying to compute the number of permutations $\pi = \left\{ ...
0
votes
1answer
20 views

choosing poker hand with a specific card

How many ways can you choose at least one A from a deck of card in a poker hand? I just wanted to double check my answer, would it be C(52,5)- C(48,5) Help is much appreciated,
0
votes
2answers
37 views

rolling dice 6 times, outcomes showing of 2 sixes

If 6 dices are rolled, in how many ways will exactly 2 sixes show up? I was thinking that it would be 6*6*5*5*5*5, am I right?
2
votes
1answer
77 views

How can we get this tricky sum of included and excluded elements?

Suppose that we have $n$ elements. Of these we pick $a$ elements that we must have, and $b$ elements that we must not have. Now, if we have a set of $m$ of the $n$ elements, we can follow the rules ...
2
votes
1answer
109 views

How does this amount change if we add to it?

We can iterate over the naturals, with zero included. Here the focus is on the numbers from $0$ to $2^s - 1$, inclusive, in binary. So we have the numbers as: $$0000, 0001, 0010, \dots 1111 \text{ ...
7
votes
1answer
542 views

An application of Pigeon Hole Principle

Prove that from any set of $11$ natural numbers, there exists 6 numbers such that their sum is divisible by $6$.
0
votes
1answer
82 views

How many ways of selecting from identical pairs?

My question is with regards to combinations and permutations. How many ways are there to select n unique objects from x number of identical object pairs? To make this question clearer, here is a ...
0
votes
2answers
118 views

Number of handshakes at a party [closed]

10 indian and 10 american couples meet at a party and shake hands. if no wife shakes hands with her husband and no indian wife shakes hands with a male, then the number of hand shakes that take place ...
0
votes
2answers
109 views

random shortest grid walk

Let $W$ be a random shortest grid walk from $(0,0) \to (20,20)$. Compute exactly a) the expected area above or to the left of $W$, b) the expected number of turns of $W$. Please help, give some ...
4
votes
1answer
73 views

Lines covering points on napkin

Suppose we place a $100\times 100$ napkin on an infinite lattice plane. What is the minimum number of lines that can always cover all the lattice points lying inside or on the border of the napkin, no ...
0
votes
2answers
112 views

Probability of selecting one of multiple sets of distinct items

Here is the problem I am having: You have a set of items; let's say colored stones. There are 40 stones. 3 Blue, 3 Red, 3 Green, 3 White, 3 Yellow, 3 Purple, 3 Orange, 1 Black, 18 Grey. Without ...
2
votes
1answer
110 views

Is my application of Burnside's Lemma correct in this combinatorial problem?

For a course in Combinatorics (I know very little group theory unfortunately), we've been tasked to use Burnside's Lemma on the following problem: Suppose you write a 5-digit number on a piece of ...
0
votes
1answer
337 views

Recurrence Relation Models

Find a recurrence relation for $a_n$, the number of ways to give away $1$, $2$, or $3$ for $n$ days with the constraint that there is an even number of days when $1$ is given away.
1
vote
0answers
49 views

Sperner's Lemma/Intermediate Value Theorem - odd number of crossings counting multiplicity

Suppose $f:[0,1] \to \mathbb{R}$ is not just continuous, but also smooth. Let $f(0)<0$ and $f(1)>0$. Is it true that the graph of $f$ crosses the $x$-axis an odd number of times, counting ...
1
vote
1answer
190 views

Permutation group of $2^n$ binary numbers

Let $R=\{0,1\}$ and let $D$ be the set of the $2^n$ binary numbers consisting of $n$ bits. Now we apply a permutation $\pi_{i_1i_2...i_n}$ in $D$ to each element $i_1i_2...i_n$ in $D$, which is ...
3
votes
1answer
91 views

A problem in Combinatorial Analysis

It's a question of a exercise list... Let A be a set with n points on the plane such that for each point P of A there are at least k points in A equidistant to P. Prove that $$k < \frac{1}{2} + ...
0
votes
1answer
38 views

Trying to revise a formula I was once given. How many rectangular prisms are in a $n \times n \times n$ cube?

I post it the other day. The only answer I got is that the total number of rectangular prisms in a cube is equal to ${n+1 \choose 2}^3$. But using $n=2$, I found the formula to be wrong. When counting ...
0
votes
1answer
56 views

What is 2 choose2?

2 choose 2 will result in a undefined answer, if computed using the binomial coefficient. For $\left(\frac{2!}{2!(2-2)!}\right)^2$ has 0 in its denominator. But then why the correct answer is 1.
0
votes
1answer
51 views

Number of $n$-bit strings that contain from none to $n/2$ zeroes

This is a problem that revolves around symmetry. I recognize that if there is a 4-bit string that it will have 1110 as an answer, but it will also have 0111 as an answer. The thing is, I'm not sure ...
0
votes
1answer
203 views

Finding the 'n'th k-permutation of a set, and finding 'n' for a given k-permutation (lexicographical ordering)

Suppose you have a set, and want to order the k-permutations of the set (for example, the permutations of 5 elements of the set {1, 2, 3, ..., 16}). Is there a fast way of finding 'n' (the ...
3
votes
2answers
135 views

Odds in Pascal's Triangle

Let $O(n)$ be the number of odds in rows $0-n$ in Pascal's triangle. Let $E(n)$ be the number of evens in rows $0-n$. I have heard the claim that the $\lim_{n \to \infty} \frac{O(n)}{E(n)}=0$. Does ...
8
votes
5answers
288 views

finding the coefficient of $x^{14}$ in the expression: $\frac{5x^2-x^4}{(1-x)^3}$

I have a homework question which requires me to find the coefficient of $x^{14}$ in the expression: $\dfrac{5x^2-x^4}{(1-x)^3}$ I have not figured out a way to do this (I believe this is because my ...
1
vote
1answer
54 views

Parity of Partition Function

Let $T(n)$ denote the number of partitions of $n$ into parts not congruent to $3$ mod $6$. Deduce that $T(n)$ is also the number of partitions of $n $ in which odd parts appear at most twice (even ...
2
votes
1answer
49 views

Rigorous proof of this assertion about Pascal's Triangle

I have noticed that it seems that there are no prime numbers in Pascal's Triangle that are not directly adjacent to the number 1. Is there a rigorous proof for this assertion?
-1
votes
5answers
7k views

Find the number of integers between 1 and 100 that are divisible by both 3 and 4.

Question in proofs homework in our "sets" unit. I'm not sure if I need to use unions/intersects. Just confused as how to begin to solve this question. Help please!
1
vote
1answer
78 views

Divisible by 11

How many divisors of $11$ are in a $9$ digit number containing distinct digits from $\{1,2,...9\}$ (no repetitition) My attempt : Let $e$, $o$ denote sum of digits at even and odd places. ...
0
votes
3answers
237 views

How many square based pyramids are in a bigger pyramids?

The biggest challenge to solve the problem is that I can't really picture a pyramid. And it is hard to make a model. The pyramids I am trying to find include those on all tiers.
1
vote
1answer
76 views

Painting a grid of squares.

Consider a $9\times9$ block of squares where each square is painted either black or white. If each square is adjacent to at most three black squares, what is the maximal number of black squares? Here ...
1
vote
1answer
78 views

A factorization problem involving Fibonacci and Lucas Polynomials

Consider a sequence of polynomial $\{w_n(x)|\, n\geq 0\}$ which are defined recursively by $w_n(x)=xw_{n-1}(x)+w_{n-2}(x)$. With $w_0(x)=0$ and $w_1(x)=1$, one gets the so-called Fibonacci polynomials ...
0
votes
2answers
106 views

Number of necessary stickers to complete a sticker album

I have the following problem, and I was hoping you guys could help me solve it: Consider a set of $t$ unique, collectable stickers (that accounts for the universe of collectable stickers, i.e., ...
0
votes
1answer
24 views

Combinatorics Drugs Distribution

Someone already asked this question but I wanted to know why the answer isn't $ {50\choose20} + {30 \choose 20 }+ {10 \choose 10 } $ instead it's $ {50\choose20} \cdot {30 \choose 20 } \cdot {10 ...
0
votes
1answer
312 views

Closed form for nth term of generating function

How would I find the closed form for the $n^{th}$ term of a sequence? Is there a general formula I can follow for these types of problems? Taking this sequence for example... $$\frac{x^5}{(1-x)^4}$$
0
votes
1answer
182 views

Counting and probability theory problems

(a) A professor designed his final exam as follows: There will be three sections in the exam. Each section has five questions. Students have to pick any two sections to answer, in any order. Within ...