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

permutations vs combinations on slot machines with repeating elements on each reel

For a slot machine with 5 reels where there are repeated elements on each of the reel. Example: Reel 1 [ 1, 1, 2, 1, 3, 5, 6 ] Reel 2 [ 1, 2, 3, 4, 5, 5 ] Reel 3 [ 2, 2, 3, 2, 4 ] Reel 4 [ 1, 2, 3, ...
0
votes
1answer
32 views

Interesting Combinatorial Identities; e.g. $\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}$

I came across the following combinatorial identity: $$\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}$$ Here's the kind of proof which caught my interest: $\sum_k {n \choose k}^2 = \sum_k {n \choose ...
10
votes
2answers
278 views
+50

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
0
votes
1answer
42 views

Probability a blackjack dealer will bust if you know their score and know the exact deck?

If you know the exact cards left in a deck, and the score of the dealer, how can you calculate the exact probability that they will bust? The dealer behaves as follows: If the dealer's score is less ...
2
votes
1answer
315 views

Probability of a slot having exactly $K$ elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
1
vote
3answers
68 views

Exponential generating function for the number of binary strings of length $n$

I know that the generating function of the sequence counting the number of binary strings of length $n$ is $e^{2x}$. But my book doesn't explain why this is the case. Could you give me a little more ...
0
votes
2answers
290 views

Formula to determine total coin combinations problem?

This question was asked in an aptitude test and was meant to be solved within 2-3 minutes.I know how to solve it by Bruteforce method, but its time-consuming.So, is there any strategic way/shortcut to ...
-7
votes
0answers
33 views

Fundamental principle of counting?

How many three-digit even numbers are there such that 9 comes as a succeeding digit in any number only when 7 is the preceding digit and 7 is the preceding digit only when 9 is the succeeding digit? ...
1
vote
1answer
37 views

How many surjective functions $f: X \to \{1,…,j\}$?

How many surjective functions $f: X \to \{1,...,j\}, |X|=j \cdot k.$ can be defined if they must satisfy: $$ |\{x\in X: f(x)=r\}|=|\{x\in X: f(x)=s\} \forall r,s\in \{1,...,j\} $$ My attempt: From ...
0
votes
1answer
38 views
+50

Modeling, Measuring, and Maximizing “Mixedness”

Background: My class has $10$ students and $3$ tables; naturally, the students are distributed with $3, 3,$ and $4$ seated at the individual tables. On the second day of class, students sat in the ...
3
votes
5answers
97 views

Why count it this way?

This is a very very elementary problem solving technique I was taught some time back. I have been using it but now looking at it, I find it kinda strange why it should be this way. Typically, the ...
1
vote
1answer
38 views

Number of distinct necklaces using K colors

I have a task to find the number of distinct necklaces using K colors. Two necklaces are considered to be distinct if one of the necklaces cannot be obtained from the second necklace by rotating ...
0
votes
2answers
223 views

Counting the number of diagonals?

In a heptagon not more than two diagonals intersect at any point other than the vertices, then the number of points of intersection of the diagonals is (excluding the vertices of this heptagon)....??? ...
-4
votes
3answers
1k views

Number of squares on a rectangular board that are neither in the 4th row nor in the 7th column

A rectangular game board is composed of identical squares arranged in a rectangular array of $r$ rows and $r+1$ columns. The $r$ rows are numbered from $1$ through $r$, and the $r+1$ columns are ...
1
vote
1answer
25 views

maximal matching in graph theory

if we have a graph $G = (V,E)$ and the four values $\beta_1(G)$, $\alpha_1(G)$, $\beta(G)$, $\alpha(G)$, where $\beta_1(G)$: Edge independenth number. The maximal number of independent edges in the ...
5
votes
2answers
113 views

Determine the number of subsets

How many distinct subsets of a set $\text{A}$ are there, containing at least $9$ elements, where the total number of elements in set $\text{A}$ is $18$ ? I've solved it by making cases of either ...
0
votes
0answers
15 views

Knight paths on homothetic polyominoes

A while back I made the following conjecture : Let $P$ be an arbitrary polyomino .Let a polyomino be good if there exist a path of a knight on it which passes through each little square exactly once ...
0
votes
1answer
42 views

How to interpret the Generalized Version of Inclusion-Exclusion Principle

This is a follow-up question on the previous post. Let's say there are $n$ properties which are numbered $1,\cdots,n$. And let $A$ be a set of elements which has some of these properties. Then the ...
1
vote
1answer
24 views

The number of ways to draw boundaries of constituencies, subject to constraints

A state comprises 45 counties arranged as 5 rows, running east and west, of 9 counties each, the nine colums of 5 running north and south. They're connected horizontally and vertically, i.e. ...
5
votes
1answer
405 views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
4
votes
3answers
367 views

Students in a class, girls sitting with boys and boys sitting with girls

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
1
vote
1answer
15 views

Numbers written into a square grid

I was working on a problem from The Art and Craft of Problem Solving by Zietz, in the chapter called 'The extreme principle.' Here is the problem: "The integers from 1 to $n^2$ are written into a ...
0
votes
2answers
22 views

How many n-permutations have no substrings of the type (j,j+1)?

How many n-permutations have no substrings of the type $(j,j+1)$? $$1\leq j\leq n-1 \text{ and } n\geq 2$$ For example, let n be 5: [3 2 1 5 4] is one of the permutations we have to count. [4 ...
2
votes
2answers
25 views

Special case on counting in a string of 7 letters

I have the following question: Suppose $S_7$ is the set of all strings of length seven that can be formed with the letters $A, B, C, D, E, F$ and $G$ when repetitions are allowed. How many strings ...
-4
votes
0answers
46 views

Recall structures made from legos [on hold]

Recall structures made from legos. We do not see these as just one lego brick after another, we see substructure. Try to find some substructure in the following lines of proof. Assume r is in Q. ...
1
vote
1answer
45 views

Number of elements in discrete $n$-dimensional simplex such that $x_1 \leq \ldots \leq x_n$

For positive integers $n,d$, how many elements are there in the set $S = \{(x_1,\ldots,x_n) \in \mathbb{Z}^n\ |\ 0 \leq x_1 \leq \ldots \leq x_n \wedge \sum_i x_i = d \}$? I'm hoping that the order ...
4
votes
1answer
21 views

Arrangement of any number of objects from $n$ objects

Prove that the total number of arrangements of objects by taking any number of objects from $n$ different objects is $\lfloor e \times n! - 1 \rfloor$, where $e$ is the natural base. I tried it ...
10
votes
4answers
1k views

N gunmen in a field

Let n be an odd integer. In some field, n gunmen are placed such that all pairwise distances between them are different. At a signal, every gunman takes out his gun and shoots the closest gunman. ...
-1
votes
1answer
57 views

Counting the maximum number of intersections.

Let $n$ be a positive integer. Points $A_1,A_2, \cdots, A_n$ lie on a circle. For $1 \le i <j \le n$, we construct $\overline{A_iA_j}$. Let $S$ denote the set of all such segments. Determine the ...
14
votes
3answers
435 views
+200

Finding real money on a strange weighing device

You have 50 coins which each weigh either 20 grams or 10 grams. Each is labelled from 0 to 49 so you can tell the coins apart. You have one weighing device as well. At the first turn you can put as ...
-2
votes
0answers
21 views

How many ways shuffle $n_1$ and $n_2$ balls when we but them together?

I have $n_1$ white balls and $n_2$ black balls, and I want to know how many ways I can make a distinct arrangement from them. For example , $n_1 = 2$, $n_2 = 1$ then there are three distinct ...
4
votes
2answers
69 views

Simplifying a combinatorial expression

Find \begin{eqnarray} \sum_{i=1}^{k-1}i(2k-2-i)\binom{2k}{2i+1} \end{eqnarray} I know how to find $\sum_{i=1}^{k-1}a_i\binom{2k}{2i+1}$ if $a_i$ is linear in $i$, but got stuck when $a_i$ is ...
0
votes
1answer
18 views

Counting weakly connected graphs with outdegree of exactly one.

If we count all graphs of $N$ labelled vertices, where each vertex has an outdegree of exactly $1$ with no self-loops allowed, we'll find that there are exactly $(N-1)^N$ of them (for every of $N$ ...
1
vote
1answer
33 views

Is this a binomial or multinomial question?

You can donate to a company: $10$ dollars , $20$ dollars or nothing. In a mall there are $70$% young people and $30$ % old people. $50$% from the old people aren't donating anything. ...
6
votes
1answer
3k views

The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts

This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
2
votes
2answers
40 views

Erin rolls 4 four-sided dice all at once, then can roll a subset of her choosing a 2nd time. What is the probability of getting all the same number?

Here's what I have so far: All 4 same on first try = (1/4)^4 * 4 3 same, then get 4th on 2nd roll = 4 * (1/4)^3 * (3/4) * (4!/3!) Here's where I'm confused: 2 same = 4 * (1/4)^2 * (3/4)(2/4 :to ...
2
votes
1answer
46 views

How do I calculate these sum-of-sum expressions in terms of the generalized harmonic number?

I know that $$\sum_{m=2}^k\sum_{n=1}^{m-1}(nm)^{-s}=\frac 12((H_k^s)^2-H_k^{(2s)})$$ and $H_k^s=\sum_{n=1}^kn^{-s}$ But, how would I go about finding identities in terms of the harmonic number like ...
1
vote
4answers
122 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
0
votes
1answer
181 views

King and Devil problem

On a unlimited two-dimensional plane, the plane is separated into two-dimensional grid point by line $x=k$, $x=-k$, $y=k$, $y=-k$ ($k$ is integer). There is a game like this : A king could move to any ...
2
votes
3answers
1k views

Bell numbers (number of partitions of set of cardinality n) recurrence relation proof

Let $X$ be a set of cardinality $n$. How many partitions does it have? The users on the website found that these are the so called bell numbers. hey also pointed out the following recurrence relation: ...
0
votes
1answer
28 views

Numbers of factors of (n)(n+1)/2 is product of exponents?

I was trying to find the number of factors of $n(n+1)/2$, and I read this blog article, and it says that the number of factors of it is the product of its prime factor's exponents with one added to ...
1
vote
0answers
35 views

How to Evaluate this Summation to Find a Closed Form

While taking the incomplete Bell Polynomil of $x^a$ i found out that: $$ B_{n,k}^{x^a}(x) = x^{ak-n} \sum_{m=0}^k \frac{(am)!(-1)^{k-m}}{m!(k-m)!(am-n)!} $$ Now, what i am wondering is, what is the ...
2
votes
1answer
39 views

Distribution of K balls in N Cells with limitations

In how many ways can i distribute $k$ balls in $n$ numbered cells with the following limitations: 1.Each cell has different number of balls in it 2.Given each cell has more balls than the cell ...
3
votes
0answers
50 views

Stirling transform of $(k-1)!$

While reading about combinatorial mathematics, I found this article about the Stirling transform which caught my attention. So, if I wanted to find the Stirling transform of, for instance, $(k-1)!$, ...
2
votes
3answers
36 views

Probability theory combinatoric problem

A total of $n$ bar magnets are placed end to end in a line with random independent orientations. Adjacent ends with equal polarities repel each other, and adjacent ends with opposite polarities ...
0
votes
0answers
37 views

Prove the function is nondecreasing

Lets take: $A_1,...,A_n$ family of finite, nonempty sets. Define: $$f(t)=\sum_{k=1}^n\left( \sum_{1\le i_1<...<i_k\le n}(-1)^{k-1}t^{|A_{i_1} \cup ... \cup A_{i_k}|} \right)$$ for $t \in [0,1]$. ...
0
votes
3answers
31 views

Combinations and Double Factorials

In a village, there are 10 boys and 10 girls. The village matchmaker arranges all the marriages. In how many ways can she pair off the 20 children, if homosexual marriages (male-male or female-female) ...
2
votes
1answer
28 views

Combinatorics strategie for order

At the moment I have to deal a bit with Combinatorics but I have some problems with it. Let's say I have following situation: Spend 1500 Euro to 4 people so that everyone has a multiple of 100 ...
1
vote
2answers
87 views

How to prove even subsets equal to odd subsets? [duplicate]

There is question that I don't know how to prove. we have set $A=\{1,2,3,\ldots,n\},\; O=\{B\mid B⊆A,\text{ odd }B\},\; E=\{B\mid B⊆A,\text{ even }B\}$ it ask to prove that subsets even equal to ...
4
votes
3answers
69 views

Number of subsets with even number of elements [duplicate]

Let $|X|=n$. How to find all number of subsets $X$ consisting of an even number of elements?