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
172 views

A multiple choice question.

A club with $x$ members is organized into four committees such that $(a)$ each member is in exactly two committees, $(b)$ any two committees have exactly one member in common. Then $x$ has $(A)$ ...
1
vote
1answer
416 views

Solving an Equation involving Factorials and Exponents.

Is it possible to find the value of $n$ in: $$\Large{\frac { (_{ 365 }{ P }_{ n }) }{ { \left( 365 \right) }^{ n } } \quad \approx \quad \frac { 1 }{ 5 }}$$ Please help! Thanks for your answers in ...
1
vote
1answer
31 views

Seperate the numbers into pairs

With how many ways can we separate the numbers $\{ 1,2,3, \dots, 2n\}$ into $n$ pairs, when: We don't care about the order of the pairs We care about the order of the pairs $$$$ At the case when ...
0
votes
1answer
36 views

With how many ways can we choose cards?

With how many ways can we choose, from usual pack of cards with $52$ cards(that are separated into $4$ colours and $13$ kinds) $5$ cards, $2$ of which should be red($\diamondsuit$ or $\heartsuit$) ...
0
votes
2answers
33 views

Find out in how many ways the operation can be performed?

i) In how many ways can a committee of $5$ or more be formed from 12 persons? ii) In how many ways can a committee of $5$ be formed from 12 persons if only two of a group of $3$ persons must always ...
1
vote
2answers
120 views

How many messages in the Morse code?

A message in the Morse code is a finite sequence(a word) with dots, dashes and gaps. How many different messages can be made with $7$ dots,$3$ dashes and $2$ gaps? And how many if it is not allowed ...
0
votes
2answers
200 views

Telephone Numbers without repeated digits

In a city with telephone numbers with $6$ digits,how many telephone numbers exist without repeated digits?What does this mean? That my telephone number shouldn't have twice the same number or that my ...
1
vote
1answer
69 views

Choosing cards from a deck

In how many ways can you choose $5$ cards from a deck of $52$ playing cards such that exactly $2$ denominations are same and all suits are available? My attempt : $^{13}C_4 \times \text{} ^4 C_1\...
0
votes
2answers
49 views

Question about the number of subsets

Given a set $S$ of size $25$, let $x$ be an element in $S$. What is the number of subsets of $S$ that contain $x$? Why am I stuck on this? The number of subsets that don't contain $x$ is $2^{24}$, ...
0
votes
1answer
141 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?
1
vote
1answer
65 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
0answers
139 views

“Dual cardinality” in the graphs $(V_\alpha,\in_\alpha)$

04-25-2014 Enriched with more details Let define the graphs $(V_\alpha,\in_\alpha)$ in $ZFC$ $V_\alpha$ can be finite too $\in_\alpha \subseteq V_\alpha \times V_\alpha$ and $\in_\alpha:=\{(a,b):a ...
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 ...
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 $...
3
votes
1answer
93 views

Labeling the vertices of a polygon with 0's and 1's

Suppose $P_n$ is the regular polygon with n vertices ($n\geq 5$). Let $V=\{v_1,\ldots,v_n\}$ be the vertex set. I would like to define a labeling function $\ell:V\to \{0,1\}$ so that $\sum_{i=1}^{n}\...
7
votes
1answer
311 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
0
votes
2answers
56 views

partitioning numbers from 1 to n in 4 non-empty subsets so no subset has 2 consecutive numbers.

Attempt: We have to find the number of ways to partition the numbers 1 to n into four non-empty subsets so that none of them are empty. let $f(n)$ be the way to do that and let $f'(n)$ be the way to ...
0
votes
0answers
48 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 $\lambda$...
2
votes
2answers
63 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
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 ...
-1
votes
3answers
137 views

How to interpret $(2n)!$

It's all in question: how to interpret the factorial from $2n$? Is $(2n)!$ equal to $n!\times n!$ ? The problem is in Combinations if the combinations is $\binom{2n}3$. P.S. The main problem is ...
3
votes
1answer
88 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 $G$,...
1
vote
1answer
362 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
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
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,
1
vote
2answers
191 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
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!}. $$
0
votes
2answers
39 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
105 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\{ \pi_1,...
0
votes
2answers
57 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}$ and ...
0
votes
1answer
85 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
123 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
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 ...
6
votes
2answers
249 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
127 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
113 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
192 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
51 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
55 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
96 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
1k views

How do I begin proving this binomial coefficient identity: ${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$

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
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 ...
4
votes
1answer
74 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
55 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
4answers
431 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
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
208 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 "...