This tag is for basic 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)

2
votes
1answer
18 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 ...
5
votes
0answers
78 views

I managed to prove this … Can it be used for anything?

I managed to show: $$ x = \sum_{k=1}^{\infty} \sum_{r=1}^{\infty} \mu (k) x^{kr} $$ where $ \mu(k) $ is mobius function and $ x $ belongs from (-1,1) Can this be used for anything?
1
vote
0answers
15 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 ...
4
votes
2answers
45 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
1answer
13 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,
1
vote
2answers
25 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
4answers
164 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!}. $$
0
votes
2answers
22 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?
1
vote
0answers
37 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
2answers
46 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}$ ...
0
votes
1answer
26 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
0answers
28 views

Golf combinatorics

A family friend is organizing a trip, with the following constraints: ...
0
votes
0answers
10 views

Transformations on a $4\times4$ matrix

Let's say a company produces chips containing $16$ elements, ordered in a $4\times 4$-matrix: $$\begin{bmatrix} \hline ...
0
votes
0answers
14 views

Collecting terms of a hard linear equation

I need to collect the $\Pr(\cdot)$ terms of the following expression: $\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left( 1-\theta \right) }\right) ^{m}}\left[ ...
0
votes
2answers
42 views

Number of handshakes at a party

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
1answer
22 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 ...
5
votes
2answers
83 views

Line Spectra in Hydrogen atom

Suppose you have a collection of large amount of Hydrogen atoms in $n$th state($n-1$th excited state). They have to go to their ground state($n$=1). Going from $n_1$ to $n_2$ makes a unique spectral ...
0
votes
2answers
29 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
39 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 ...
2
votes
1answer
24 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 ...
1
vote
0answers
23 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
2answers
34 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$ ...
3
votes
1answer
41 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} + ...
3
votes
6answers
369 views

How do I begin proving this binomial coefficient identity?

This is a homework question. I'm asked to prove the identity: $${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$ (The sum ends with ${n\choose n} = 1$, with the sign of the ...
0
votes
1answer
27 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
49 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
0answers
12 views

combining continuous distributions

If we have several continuous distributions, for example ten Beta distributions, how we can combine them by the linear and log-linear opinion pool methods? I know how to combine discrete ...
0
votes
1answer
30 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 ...
4
votes
1answer
39 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 ...
1
vote
1answer
25 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 ...
-1
votes
5answers
63 views

Sum of 4 digit numbers

What is the sum of all the numbers of 4 different digits that can be made using digits 0,1,2,3? How do you solve such problems? I am only familiar with basic combinatorics problems
6
votes
1answer
435 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
30 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 ...
2
votes
1answer
29 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?
3
votes
2answers
50 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 ...
1
vote
1answer
45 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 ...
0
votes
0answers
15 views

Invariance of vectors under permutation?

Suppose that there are 10 individuals and that only 4 of them are males. Assume that we label the males 1,2,3,4 and the females 5,6,7,8,9,10. Let $W_j$ be a $10\times 1 $ vector collecting the ...
1
vote
1answer
24 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
0answers
24 views

Probability bound using Markov and Chebyshev's Inequalities for a 400 coin flip?

Let random variable X = number of heads. Find expectation and variance of X if you bound the probability X >= E(X) + 30 using Markov and Chebyshev's. So if X~Bin(1/2) E(X) = np = 400(1/2) = 200 and ...
0
votes
2answers
40 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 ...
0
votes
1answer
18 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
0answers
51 views

Basic Couting Picking Sequence of Letters

How Many ways are there to pick a sequence of two different letters of the alphabet that appear in the word MATHEMATICS My idea is that it will be the number of permuations of all letters as if ...
0
votes
0answers
21 views

How many ways can we divide 30 students of three types, namely A (8 students), B (10), C (12) into groups of 2?

I have read other questions on splitting groups into subgroups, for example Problem : Permutation and Combination : In how many ways can we divide 12 students in groups of fours. but my case is ...
0
votes
0answers
26 views

Problem on combination - counting the size of event space

(a) How many odd numbers between $10000$ and $99999$ have distinct digits? Five ways to pick the last digit, which defines the parity (in this case, odd) of the number. Eight ways to pick the ...
0
votes
0answers
32 views

In the lottery there are 49 balls. How many different combinations has consecutive numbers?

In the lottery there are 49 balls. How many different combinations has consecutive numbers? First I calculate all posible combination: $\frac{49!}{6!(49-6)!}=13'983,816$ Now, I want to know the ...
0
votes
0answers
35 views

is there a method for generating functions to construct recurrence relations?

I am starting to read about combinatorics and generating functions and generally I see they use generating functions to get a closed form formula for a recurrence relation. I have some questions about ...
0
votes
1answer
48 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 ...
4
votes
2answers
79 views

Prove that ax+bx+ay+by ≤ 300.

Let $a,b,x,y$ be positive numbers satisfying: $ax ≤ 100, bx ≤ 100$, $ay ≤ 100, by ≤ 50$. Prove that $ax+bx+ay+by ≤ 300$. Can someone help me ??
3
votes
2answers
36 views

Problem on combination - ways to form a committee

There are 10 men and 7 women working as supervisors in a company. The company has recently decided to form a committee to represent all the employees. The committee has to consist of 3 members, all of ...
0
votes
1answer
44 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}$$