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

How many different three-digit house numbers could be made?

a shopkeeper sells house numbers. she has a large supply of the numerals 4, 7 and 8, but no other numerals. how many different three-digit house numbers could be made using only the numerals in her ...
0
votes
1answer
36 views

3 cards are drawn from a deck of 52. how many hands are possible if exactly 2 are black cards and exactly 1 is an ace?

3 cards are drawn from a deck of 52. how many hands are possible if exactly 2 are black cards and exactly 1 is an ace? I'm not sure how this works. Never seen a question quite like this.
1
vote
3answers
134 views

Stumped - How would I solve this probability question?

This question was merely a fun online math problem to see how many people could solve it, but I haven't been able to since last week and it's begiing to drive me nuts. The question: A man has 7 math ...
4
votes
0answers
50 views

Algorithm to find shortest path to net values across nodes

I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$. Each node $v$ has an associated number $n_v \in \mathbf{Z}$ Let us define for any two nodes $v, w \in V$ connected by an edge $e ...
3
votes
3answers
239 views

Proof for coloring combinations problem. (color vertices of pentagon)

While studying, I found a problem in my book that read: "Each vertex of convex pentagon ABCDE is to be colored with one of seven colors. Each end of every diagonal must have different colors. Find the ...
1
vote
1answer
37 views

Maths challenge problem: Why is the number of teams which require 4 substitutions 32?

I came across the following problem on a UKMT senior maths challenege: A hockey team consists of 1 goalkeeper, 4 defenders, 4 midfielders and 2 forwards. There are four substitutes: 1 goalkeeper, 1 ...
2
votes
1answer
20 views

Let $n$ be a positive integer and $S$ the set of points $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers such that $x + y < n$.

Let $n$ be a positive integer and $S$ the set of points $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers such that $x + y < n$. The points of $S$ are colored in red and blue so ...
7
votes
2answers
40 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
0
votes
1answer
14 views

Expectation of size of bootstrapped sample

Lets say we have a sample $\mathbf{X} = \{x_1, x_2, \dots, x_N\}$. We draw $N$ points from $\mathbf{X}$ with replacement (do a $\textit{bootstrap})$. What is the expectation of size of bootstrapped ...
3
votes
2answers
33 views

A grasshopper starts at the origin and is equally likely to hop north,s,e,w. What is the probability that it's coordinates will be 0,0 after 4 hops?

The grasshopper must hop in all $4$ directions (North, South, East, and West) to get back to the origin after $4$ hops. Therefore, I did: $\frac{(4 \cdot 3 \cdot 2 \cdot1)}{4^4} = .09375$. However, ...
3
votes
0answers
22 views

Given $100$ coplanar points, no $3$ collinear, then at most $70$ percent triangles formed using these points are acute-angled

(IMO-$1970$) Given $100$ coplanar points, no $3$ collinear, prove that at most $70$ percent of the triangles formed using these points are acute-angled. I know that one solution proceeds by ...
3
votes
2answers
25 views

Number of ways to select subsets

In how many ways can two distinct subsets of the set $\text{A}$ of $k$ $(k \geq 3)$ elements be selected so that they have exactly two common elements? I started by choosing two elements (that ...
0
votes
2answers
58 views

Powerset with constraints

I have two sets $NUMBERS$ and $LETTERS$ with: $ NUMBERS = \{1, 2, 3, 4, 5\} \\ LETTERS = \{ A, B, C, D, E\}$ No I want the power-set of my sets, i.e. the set of subsets of elements from both ...
2
votes
0answers
44 views

Number of games required such that two arbitrary players play together and against each at least once.

There are $2N$ players to form two teams of $N$ players that play against each other in a game. How many games are required such that two arbitrary players play together and against each other at ...
1
vote
2answers
45 views

How to solve this combinations with repetitions problem using generating functions?

Find the number of solutions to : $$x_1 + x_2 + x_3 + x_4 + x_5 = 10$$ where none of the variables can be the number $3$. I can solve this with Inclusion-Exclusion Principle, but I really love ...
0
votes
0answers
11 views

Optimization problems with combinations of a finite set as the feasible area?

For example: Provided that $S\subset \Re$ is a known finite set ($n\leq |S| < \infty$), number $k$ is known, and $1 \leq k<n$ minimize $f(x_{1},\ldots, x_{n}) = \sin (\sum_{1\leq i\leq ...
3
votes
1answer
81 views

Expected value when die is rolled $N$ times

Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
0
votes
0answers
15 views

subsets with predefined sequences

I have a set $N=\{m,m+1,m+2,...,n\}$ And there are some generating functions of the format : $f(x,k) = (x^2 -1) \mod k$, where $k \le \sqrt m$ and $k$ is in the form $(6i+1)$ or $(6i-1)$, $\forall ...
0
votes
1answer
19 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, ...
3
votes
1answer
67 views

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

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

Fundamental principle of counting? [on hold]

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? ...
0
votes
1answer
47 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 ...
1
vote
1answer
38 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 ...
1
vote
1answer
40 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 ...
1
vote
1answer
29 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
117 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
16 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
50 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
25 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. ...
1
vote
1answer
17 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 ...
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
47 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. ...
4
votes
1answer
22 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 ...
1
vote
1answer
34 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. ...
-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 ...
0
votes
1answer
19 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$ ...
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 ...
0
votes
1answer
29 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
votes
1answer
58 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 ...
1
vote
0answers
36 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 ...
4
votes
0answers
59 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)!$, ...
0
votes
1answer
50 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]$. ...
1
vote
1answer
48 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 ...
2
votes
1answer
50 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 ...
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 ...
0
votes
3answers
34 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) ...
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
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 ...
2
votes
1answer
42 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 ...
0
votes
1answer
23 views

Counting functions and stirling numbers

Let S= { f | f: A $\rightarrow$ B, |Image(f)|=k}. |A|=m, |B|=n. where k $ \le n, k \le m $ |S|=$ {n \choose k} $ S(m,k) k!. where S(m,k) are the striling numbers of the second kind. What I can't ...