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)

1
vote
1answer
43 views

Ways to buy marbles (Arrangement)

A boy wishes to buy exactly six marbles. There are four different colours of marbles available. In how many ways can he buy the six marbles?
7
votes
5answers
260 views

Is this combinatorial identity a special case of Saalschutz's theroem?

When I solved a question, the following combinatorial identity was used $$ \sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}. $$ But to prove this identity is ...
1
vote
1answer
47 views

Why do the probabilities not match?

I came up with this problem myself: There is a deck of 52 playing cards. A hand contains 5 of them. You pull a hand from deck. What is the probability of no Queens in it? You pull a hand from deck. ...
0
votes
1answer
101 views

Another olympiad question related to Extremal Principle (regarding geometry problem)

Into how many parts at most is a plane cut by $n$ lines? (b) Into how many parts is space divided by $n$ planes in general position First i was thinking about the approach (not able to find it). ...
0
votes
2answers
41 views

Explanation for solution of a combinatorial problem

The given problem is: An ordinary deck of cards is dealt to four people: Joe, Bob, Jim, and Larry. If Larry has exactly one ace, what is the probability that Jim has all the remaining aces? My ...
1
vote
1answer
127 views

Arrange the number

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate ...
0
votes
2answers
61 views

How many unique combinations you can have when pairing 17 designs into a 7 set?

Following situation: You have 17 designs for a packing box and you want to create a set where you put 7 of them into box. The sort is not important, but the set has to be unique and no double designs ...
4
votes
2answers
87 views

Graphs with 12 edges over the vertices $\{1,2,…,12\}$ have two vertices with a degree of 5

How many graphs with 12 edges over the vertices $\{1,2,...,12\}$ have two vertices with a degree of 5? The two vertices aren't neighbours: $\binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2$. ...
1
vote
2answers
49 views

The number of cases $(0, 0)$ moves by either $(1,1)$ or $(1,-1)$, in $2n$ steps, without touching $x$-axis again.

I was solving combinatorics problems when I ran into this shady statement: The number of cases $(0, 0)$ moves by either $(1, 1)$ or $(1, -1)$, in $2n$ steps, without touching $x$-axis again is ...
3
votes
0answers
67 views

'Randomness' of inverses of $(\mathbb{Z}/p \mathbb{Z})^\times$

Suppose you are given the group $(\mathbb{Z} / p \mathbb{Z})^{\times}$, where $p$ is prime. Let $A_p$ denote the sequence whose $j$th element is the inverse of $[j]$. For instance, if $p = 7$, the ...
4
votes
1answer
85 views

Combinatorial interpretation of identity

I recently came across the identity $$\sum_{k=0}^m\dbinom{m}{k}\cdot \frac{(-1)^k}{n+k+1}=\dfrac{n!\cdot m!}{(n+m+1)!},$$ while working on evaluating $$\int_0^1 x^n(1-x)^m\, dx.$$ I ended up ...
0
votes
2answers
43 views

Expressing the expected value in a simpler form

We randomly set numbers $(1, 2,\ldots, n)$ in the sequence $(a_1,\dots,a_n)$. Let $N$ be the largest number such that for $2 \le k \le N$ we have $a_k>a_{k-1}$. Find $\mathbb{E}N.$ Lets start ...
-1
votes
3answers
55 views

Given 26 balls - 8 yellow, 7 red and 11 white - how many ways are there to select 12 of them?

I'm interested in knowing and understanding the solution to the following problem: given 26 balls - 8 yellow, 7 red and 11 white - how many ways are there to select 12 of them (all balls of the same ...
2
votes
3answers
41 views

Show that one cannot make a 8×8 square using 15 T-tetrominoes and 1 square tetromino

Show that one cannot make a 8×8 square using 15 T-tetrominoes and 1 square tetromino. Its a coloring problem. Unable to solve. please help.
0
votes
1answer
69 views

what is the number of pairs of partitions of fixed length with a fixed number of like elements

Given a labeling of the set of partitions of $n$ with $k\leq n$ parts (numbering choose$(n,k)$), and comparing all pairs of partitions from this set (numbering choose$(n,k)^2$ since we allow a ...
-1
votes
2answers
38 views

I need your help for this simple statistics problem.

I need help for the following problem: In a summer reading program for youth, there is a six week period where the seven Harry Potter books are available. (1)If only three books can be read during ...
1
vote
1answer
69 views

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$. My attempt: Induction, for $k=1$ it's obvious. Suppose for $k-1$ and we'll ...
1
vote
0answers
34 views

How is Wythoff's Theorem proved?

Specifically, how does one prove the following? Suppose $(a,b)$ is not of the form $(A_n,B_n)$, where $A_n=\lfloor n \phi \rfloor$ and $B_n= \lfloor n \phi^2 \rfloor$. Then there is a move in ...
0
votes
0answers
29 views

How many closed knight's tour are possible in a $8\times 8$ chessboard? [duplicate]

How many closed knight's tour are possible in a $8\times 8$ chessboard? I hae no such idea. Please give me the proof of it.
2
votes
0answers
39 views

An art gallery problem

An art gallery has the shape of a simple $n$-gon. Find the minimum number of watchmen needed to survey the building, no matter how complicated its shape be. I failed to solve the problem. Please help ...
2
votes
3answers
86 views

Number of n-words such that a and b are not neighbors.

Question:How many n-words from the alphabet {a,b,c,d} are such that a and b are never neighbors? 1.There are $4^n$ ways to arrange the four letters. 2.There are $(n-1)$$2^{n-1}$ ways of ...
0
votes
0answers
54 views

How do I prove that Ramsey Number r(3,6)=18?

How do I prove that Ramsey Number r(3,6)=18 ? I've tried doing so directly by showing there are 9 red vertices and 7 blue ones, and then divided to cases, but is there an easier, more direct way than ...
1
vote
2answers
28 views

Permutation with constrained repetititons

The question is as follows: How many ways can 12 identical white and 12 identical black pawns be placed on the black squares of an 8 x 8 chessboard My answer was $\frac{32!}{12!*12!}$ But the ...
0
votes
0answers
14 views

The image of a a vector in the edge space when multiplied by it's incidence matrix.

Consider a graph $G=(V,E)$ and it's incidence matrix $M$. Let $\textbf{x}$ be the characteristic vector for a standard basis vector in $\mathcal{E}$ (a vector corresponding to the one element edges ...
1
vote
1answer
54 views

$\frac{(-1)^n}{2\cdot 4\cdot \cdot\cdot2n}=\frac{(-1)^n}{2^n\cdot n!}$

$$\frac{(-1)^n}{2\cdot 4\cdot \cdot\cdot2n}=\frac{(-1)^n}{2^n\cdot n!}$$ $$\frac{(-1)^n}{3\cdot 5\cdot \cdot \cdot(2n+1)}=\frac{{(-2)^n} \cdot n! }{(2n+1)!}$$ can anyone tell me if these are true or ...
0
votes
0answers
130 views

Arrow’s Theorem

Suppose $k ≥ 3$ Recall that Arrow’s Theorem shows that any function $F:(S_k)^n\to S_k$ (the input is composed of n permutation of $[k]$ and the outcome is a single permutation of $[k]$ that satisfies ...
3
votes
2answers
150 views

Why is ${n\choose k}$ is always a product of the primes of $n$ for all $n>k$? [closed]

Let $n, k$ be two positive integers such that $n>k$. Why is ${n\choose k}$ always divisible by a prime dividing $n$ (or even a product of such primes)? Please help me understand why. I cannot seem ...
0
votes
1answer
95 views

Tournament Graphs

Given a partially ordered set (i.e. poset) $P$, let $PC(P)$ be the smallest number of chains that cover all the elements of $P$ . Let $PC'(P)$ be the smallest number of pairwise disjoint chains that ...
1
vote
0answers
28 views

Rook Polynomials with Symmetrical Overlap (Count Permutations Restricted by Distance)

Consider the cardinality $P(n,d)$ of permutations where elements can move up to distance $d$; for example, the permutation $\binom{012}{102}$ with $d = 1$ would be valid but $\binom{012}{201}$ would ...
6
votes
0answers
118 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
1
vote
1answer
104 views

Prove or disprove: for every P we have PC(P) = PC'(P)

Given a partially ordered set (i.e. poset) $P$, let $PC(P)$ be the smallest number of chains that cover all the elements of $P$ . Let $PC'(P)$ be the smallest number of pairwise disjoint chains that ...
1
vote
0answers
139 views

Assume n is an even integer. For an odd integer m, a sequence of m sets S1,…,Sm ⊆ [n] is a graceful chain of length m if…

Assume $n$ is an even integer. For an odd integer $m$, a sequence of $m$ sets $S_1, \dots, S_m \subseteq [n]$ is a graceful chain of length $m$ if: $S_1 \subset S_2 \subset \dots \subset S_m$ For ...
1
vote
1answer
32 views

Combinations and arrangement

Twelve people are to travel by 3 cars, each of which holds four. Find the number of ways in which the party may be divided if two people refuse to travel in the same car. My attempt, I know the ...
2
votes
0answers
60 views

Fill a rectangle with squares

How many ways are there to fill a $m\times n$ rectangles with squares that have integer side lengths. Both $m$ and $n$ are integers.
2
votes
0answers
43 views

Find the probability that between 5 random digits appear two differents.

I have the following exercise; Find the probability that in five random digits appear; a) two differents. My approach was the following. I consider for example the vector $(1,1,1,1,0)$ and noted ...
1
vote
2answers
94 views

Marbles Combinations problem

Martin’s bag of marbles contains two red, three blue and five green marbles. If he reaches in to pick some without looking, how many different selections might he make? I do not know how to ...
3
votes
1answer
50 views

Fixed Point with Permutation

I have this homework question I'm kind of stumped on... "A permutation of the numbers $(1,2,3,\ldots,n)$ is a rearrangement of the numbers in which each number appears exactly once. For example, ...
0
votes
5answers
155 views

If I have 10 different pairs of socks and have washed 10 socks, what are the chances that none will match?

I have 10 pairs of different types of socks. I randomly (let's just assume it was true randomness) washed 10 individual socks. It turns out none of them match! What are the chances of this? I've ...
15
votes
1answer
190 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
4
votes
2answers
72 views

Number of graphs such that two sides remain connected after some edges are removed

This problem was actually from a programming problem, but it has more of a math flavor, so I am asking on Math stack exchange! Problem: Initially, you are given a graph as in the first image, ...
1
vote
1answer
42 views

Maximal Distance of a graph

So I have the following graph $G = (V, E)$ with $V = [d]^n$ and $E = \{\{(a_1,\dots , a_n), (b_1, \dots , b_n)\} | a_2 = b_1 a_3 = b_2, \dots a_n = b_{n-1}\}$. That is called a $(n, d)$-dimensional ...
0
votes
2answers
35 views

Recurrence formula for no 3 consecutive successes in $n$ throws

Let $Q_n$ be the probability that no $3$ consecutive heads appear on $n$ throws of a fair coin. Show that the following recurrence formula is true: $$Q_n = \frac12 Q_{n-1} + \frac14 Q_{n-2} + \frac18 ...
1
vote
1answer
160 views

Average patients waiting time in dental office

At a Dental Office, patients come in at the rate of 20 per hour and, on average, are processed at the same rate. Patients wait in a queue till they are called up to the counter for registration. After ...
0
votes
4answers
109 views

Number of two disjoint subsets from the an n-set $\{x_1, x_2,…,x_n\}$.

In how many ways can you select two disjoint subsets from the an n-set $\{x_1, x_2,...,x_n\}$?
1
vote
1answer
21 views

Generating function for a bin that has either no elements or 2 only?

What is the generating function for a bin that has either zero elements or 2 only? We start with: $(1+x^2)$ which if it had an $x$ it would translate to $\frac {1-x^3}{1-x}$ So I thought maybe I ...
1
vote
1answer
28 views

generating function as english statement

An ordinary enumerator is given as $(1+x+x^2)^p$. This is being understood as follows: There are 2 each of p kinds of objects.The ordinary enumerator for selecting none (or) one (or) both the ...
0
votes
0answers
20 views

Finding a closed formula for a summation containing elementary symmetric function

Let $i$ and $n$ be non negative integers and let $X=(x_1,x_2,...,x_n)$ be a finite sequence of variables. The expression $S_i(X)$ is then defined as follows: If $i>n$, then $S_i(X):=0$, Otherwise ...
1
vote
1answer
31 views

A little problem with a binomial identity

I have to compute the quantity $\sum\limits_{k=0}^{n-1} \binom{n}{k} \frac{k}{n-k}$. Using the identity $k\binom{n}{k}=n\binom{n-1}{k-1}$ and reindexing the sum, it's easy to see the previous sum ...
-1
votes
1answer
65 views

Two new binomial identities [closed]

I have to compute the following values: $$ 1) \sum\limits_{k=0}^{n-1} 2^k \binom{n-1}{k} \frac{k}{n-k} $$ $$ 2) \sum\limits_{k=0}^{n-1} 2^{n-k} \binom{n-1}{k} \frac{k}{n-k} $$ How can I solve them? ...
3
votes
3answers
113 views

Fountains of Coins and Fibonacci Numbers

I recently came across a problem in Herbert Wilf's Generatingfunctionology book that I can't come up with an elegant solution to and can't find any solutions online. The problem statement begins on ...