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
2answers
39 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 ...
4
votes
1answer
67 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 ...
1
vote
2answers
43 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 ...
0
votes
1answer
42 views

Show $ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}$

I conjecture that $$ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}. $$ I know that it is always nonnegative, and equals $1$ for $n < p \le 2n$, ...
3
votes
0answers
16 views

Expectation of longest monotonic segment of a permutation

Consider for any $p \in P(n)$, the permutation group of order $n$, the function $L(p)$ defined as the length of the longest monotonic segment in $p$. By this I mean that $$L(p) \geq k ...
0
votes
1answer
330 views

Probability of picking exactly one correct from a pool of 6 incorrect and 4 correct

So as the question says. You have 6 incorrect objects and 4 correct ones. What are the odds that, when picking 3 of them at random, you end up with exactly one of them being correct. This seems to be ...
1
vote
0answers
40 views

Finding a closed form expression for $\sum_{k=\frac {n+2} 2} ^n \binom n k$

Find a closed expression for $\displaystyle\sum_{k=\frac {n+2} 2} ^n \binom n k$, $n$ is even. My attempt: $(1+1)^n = \displaystyle\sum_{k=0} ^ n \binom n k= \sum_{k=0} ^{\frac {n-2} 2}\binom n ...
8
votes
2answers
181 views

Minimizing over partitions $f(\lambda) = \sum \limits_{i = 1}^N |\lambda_i|^4/(\sum \limits_{i = 1}^N |\lambda_i|^2)^2$

I'm trying to characterize the behavior of the the quantity: $$A = \frac{\sum \limits_{i = 1}^N x_i^4}{(\sum \limits_{i = 1}^N x_i^2)^2},$$ subject to the constraints that $$ \sum \limits_{i = 1}^N ...
0
votes
1answer
298 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
4
votes
2answers
66 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
1answer
82 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
1answer
50 views

Another olympiad question related to External 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). ...
1
vote
1answer
31 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?
0
votes
2answers
38 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
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
0answers
119 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 ...
0
votes
2answers
17 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 ...
3
votes
0answers
61 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 ...
2
votes
2answers
127 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 ...
2
votes
3answers
103 views

How often does a one-dimensional lazy random walk end at the origin?

This seems like it's probably a solved problem, but I don't seem to be googling the right keywords. I want to know the probability that a lazy random walk on $\mathbb{Z}$ ends where it started. To be ...
0
votes
2answers
29 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 ...
4
votes
0answers
113 views

Is there a closed-form expression for Shapley value of glove game?

Suppose we have a coalition game with transferable utilities, with $m$ players having a right-handed glove and $n$ players having a left-handed glove. The value of a coalition is equal to the number ...
-1
votes
3answers
43 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 ...
1
vote
1answer
1k views

Predicting the number of orders from future customers

Tamara is reviewing recent orders at her deli to determine which meats she should order. She found that of 1,000 orders, 450 customers ordered turkey, 375 customers ordered ham and 250 customers ...
3
votes
5answers
15k views

Probability of winning a prize in a raffle

My work is having it's annual Christmas raffle today. 1600 tickets have been sold, and there are 40 prizes to win. I have bought ten tickets. What are the odds I will win a prize? While an initial ...
2
votes
3answers
25 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.
-1
votes
2answers
22 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 ...
2
votes
0answers
98 views

Balls and bins counting problem with some indistinguishable balls and cap on number of indistinguishable balls per bucket

Fix $T_1,\ldots T_m$ as pair-wise disjoint $k$-subsets of $\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$. For any $j\le k$, how many sets of the form $\{C_1,\ldots,C_m\}$ are ...
1
vote
1answer
24 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 ...
0
votes
0answers
25 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.
14
votes
3answers
2k views

How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, ...
1
vote
0answers
130 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
0answers
27 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 ...
12
votes
0answers
81 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 ...
0
votes
1answer
43 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
21 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
21 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
1answer
85 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 ...
0
votes
0answers
11 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
93 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
15 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 ...
-3
votes
0answers
15 views

Partially ordered sets - Exercise [duplicate]

I got this question and I'd be happy if someone could help figure it out.. http://i.imgur.com/jmt1wtM.png Thanks!
6
votes
0answers
67 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
votes
0answers
23 views

How to calculate different variations with possible repetitions

I work 4 days/week (or 30 hours) and can make my own schedule. It doesn't matter how many total days I work in a two week period, but the total hours worked at the end of a two week period must add ...
1
vote
1answer
429 views

What is number of perfect matchings in a bipartite graph

Let's $G=(U,V,E)$ be a random balanced Bipartite graph graph which $|U|=|V|=n$. What is the number of random graphs that has a perfect matching? I think that the number of possible graphs is ...
-2
votes
0answers
34 views

Combinarics, number of chains of specific subsets [duplicate]

Let n be even integer and m odd integer. a sequence of m sets S1,..,Sm in [n] ([n]={1,...,n}) is called super chain if: 1.S1 contained in S2 contained in S3 ... contained in Sm 2.for every i s.t. ...
1
vote
1answer
22 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 ...
5
votes
2answers
102 views

$\binom{n}{r} = 8$ Is there any way to find such $n$ and $r$?

Let ${{n} \choose {r}} = 8$. Is there any other choice of $n$ and $r$ except $8$ and $1$, $8$ and $7$ ? In general how to check that existence is guaranteed or not?
2
votes
4answers
135 views

Two children paradox: where is my reasoning wrong?

I hope here is the good place to be asking this. Apologies otherwise. The statement is as follows: "Ms Michu has two children. We know one of the two is a girl, we call that girl Ludivine. What is ...
14
votes
1answer
4k views

6-letter permutations in MISSISSIPPI

How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller ...