4
votes
1answer
66 views

No. of integral solutions of $x_1+x_2+x_3+x_4=20.$

I've to solve a no. of questions of this type but don't get how to do it: Determine the no. of integral solutions of $x_1+x_2+x_3+x_4=20.$ given the constraint that $$1\leq x_1\leq ...
1
vote
0answers
29 views

no. of regions a plane is divided into by $n$ lines in general position

My notes state the Counting process for knowing no. of regions a plane is divided into by $n$ lines in general position := Let $h_1(n)=$ No. of parts a line is divided by $n$ distinct ...
2
votes
1answer
24 views

Distinct elements in the Union and Intersection of A and B

Take a set $x$ with $10$ distinct elements. Rule: Everytime you have two subsets, $A$ and $B,$ you also have $A\cup B$ and $A \cap B.$ What is the maximum number of subsets you can have such ...
0
votes
2answers
27 views

Lottery problem - Chance of 4 out of 5 balls matching?

In a lottery, an urn contains 40 balls that are numbered 1, 2, ..., 40. Each week, 5 balls are drawn from the urn without replacement. To enter, one chooses 5 numbers. Anyone who correctly predicts ...
1
vote
1answer
20 views

How many words can be formed by taking 4 letters at a time from the letters of the word 'MORADABAD'?

What I tried was: (9P4)/3!*2! This gave me a wrong answer (since the answer is 626). I'm unable to make use of the hint provided in my book: "make cases". Any help would be appreciated. :)
1
vote
1answer
28 views

raBinomial distribution with dependent trials?

I need your help with following problem: String with n characters is given. For each character in string there is probability p that it is wrong. Now you take a sliding window of length k, k<= n, ...
2
votes
1answer
60 views

Set of numbers that add up 1 to n

I am currently trying to solve the following problem: Given a number $n \in \mathbb{N}$, find the size of a set $S$ of positive numbers $s_1, \ldots, s_k\in \mathbb{N}$, such that $\sum_{i=1}^kS_i ...
2
votes
1answer
62 views

Stair flight problem

A stair flight has 10 steps. A kid can move in jumps of 1, 2 or 3 steps. Assume the kid starts on the floor (step 0), and always has to end in step 10 because there is a door that needs to be open. In ...
5
votes
2answers
55 views

Putting objects in a line.

I'm working on a project outside of school, and I've run into a bit a problem. I thought, maybe there are some problem solvers on the internet who would enjoy this. I have 8 balls, 3 red cubes, and ...
0
votes
1answer
76 views

Acceptable Arrangements

A flagpole has spaces for seven colored flags arranged in a vertical line. Two of the flags are yellow, two are green, one is red, one is orange, and one is brown. Flags are to be placed on the pole ...
3
votes
0answers
39 views

A question on combinations of a set of numbers

I have the set of the first $n$ primes $\{2,3,5,\ldots,p_n\}$. There are $n^n$ ways of selecting $n$ numbers from this set. Each combination has a number ($C_k$) associated with it and it is the ...
0
votes
2answers
30 views

Simple Word problem question with boxes and bottles

Bottles are either packed in boxes of 6 *OR* 12. The number of small boxes must atleast be half the number of big boxes. If 240 bottles need to be packed, what's the minimum mumber of boxes needed? ...
4
votes
1answer
88 views

Can someone please clarify combinations vs permutations?

I see similar questions asked on here and obviously I did some research and read my book, but it seems like every explanation contradicts another in some way. There are basically infinite scenarios ...
0
votes
2answers
49 views

Ways to add a number using just 1's, 5's, 10's, 25's, 50's

given the set $\{1, 5, 10, 25, 50\}$, in how many ways, can you combine this numbers to get a specific number. For example, 11 can be shaped as $1\cdot11$, or $5\cdot112 + 1\cdot111$, or $10\cdot111 + ...
2
votes
2answers
78 views

Find $\max_{\sigma \in S_n}\sum_{i=1}^n|\sigma(i)-i|$ where $S_n$ is the group of permutations on $n$ letters (Greedy algorithm shows up?)

Find $\max_{\sigma \in S_n}\sum_{i=1}^n|\sigma(i)-i|$, where $S_n$ is the symmetric group of permutations of $n$ symbols. So, the story goes like this: When I first saw the problem, I thought the ...
2
votes
0answers
93 views

Please help me remembering a problem on $n!$ [closed]

I couple of years ago a friend of mine gave me a problem about the digits of $n!$, I never solved it and I also forgot what the question was. It asked you to prove some fact about the digits of $n!$ ...
0
votes
0answers
58 views

Matheletics '13 challenges

I was trying to solve the challenges proposed on Matheletics '13. I'm having trouble solving Hockey Classics, Special Arrangement and Permutation. Can anyone point out the idea I can't see, pls?
0
votes
1answer
47 views

What kind of formula would I use to get all possible outcomes?

I am into a CCG, and I got a question come to mind "how many possible out comes are there for deck combinations?" The game is broken into three: Main Character (6 cards available, only one deck), ...
3
votes
1answer
47 views

How many (linear) order types are there on a set of n elements?

Given number $n$ variables $a_1, a_2, \dots, a_n$. How many way can we place $>$, $=$ between them ? For example, for $n = 3$ (Let's call $a_1 = x, a_2=y, a_3=z$ for convenient). There are 13 way: ...
1
vote
1answer
65 views

English question regarding pigeonhole principle classic question.

Mr. and Mrs. Smith invited four couples to their home. Some guests were friends of Mr. Smith, and some others were friends of Mrs. Smith. When the guests arrived, people who knew each other ...
1
vote
1answer
60 views

Pigeonhole Principle to solve question straightforward

A store wants to celebrate its anniversary and will give a $200 shopping certi cate to the first customer to enter the store whose birthday is the same as that of two other previously admitted ...
1
vote
1answer
198 views

Probability of two dice rolls

If two standard 6 sided dice are tossed what is the probability that a 3 is rolled on at least one of the two? How do I solve this without listing out the possibilities?
2
votes
3answers
216 views

Probability of winning the game 1-2-3-4-5-6-7-8-9-10-J-Q-K

A similar question to mine was answered here on stackexchange: Probability of winning the game "1-2-3" However, I am unable to follow the formulas so perhaps someone could show the ...
14
votes
3answers
301 views

On a Putnam's 2009 problem [duplicate]

Find all even natural numbers $n$ such that the following is true: There is a non-constant function $f : \Bbb{R}^2 \longrightarrow \Bbb{Z}_2$ such that for any regular $n$-gon $A_1...A_n$, $f(A_1) + ...
1
vote
1answer
62 views

What is the relative strength of each of the players in this game?

This is a real life problem. A group of people meet once a week to play a game between two teams. Each round 2 people are randomly appointed captains. Each captain takes turns picking people to be on ...
1
vote
1answer
54 views

Days that cashier will work [duplicate]

A cashier wants to work five days a week, but he wants to have at least one of Saturday and Sunday off. How many ways can he choose the days he will work?
-1
votes
2answers
132 views

Sophomore + Junior + Senior

A class is attended by $n$ sophomores, $n$ juniors and $n$ seniors. In how many ways can these students form $n$ groups of three people each if each group is to contain a sophomore, a junior, and a ...
2
votes
1answer
418 views

Ways to place n non-attacking rooks on an $n^2$ square board.

How many ways are there that we can place n number of non-attacking rooks on an $n \times n$ chess board?
5
votes
2answers
188 views

Combinatorial Proof of ${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$

How do prove the following identity combinatorially? $${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$$ Any help or hints would be great!
4
votes
1answer
171 views

Board $7\times 7$ problem

An aid in this problem: On a board of $7 \times 7$ each box is painted red or blue so that any square on the board has at least two neighboring boxes blue. determine as little blue boxes that can be ...
1
vote
1answer
74 views

Finding the least number of equations for which that $S-1$ is a component.

Let $S=\sum w$, summed over all words $w=\{x,y\}$ with the same number of $x$'s and $y$'s. Let $\phi$ be the abelianization operator. We know that $$\phi(S)=\sum_{n\geq1}{2n\choose ...
3
votes
1answer
166 views

Partition Proof

Let $\lambda$ be a partition of $N$ of rank $r$. How can I show that: $$\sum_wx^\lambda(w)=f^\lambda(-1)^{t(\lambda)}\prod^r_{i=1}(\lambda_i-1)!(\lambda'_i-1)!$$ where $w$ ranges over all ...
3
votes
2answers
150 views

choosing $5$ non consecutive books from a shelve of $12$

In how many ways can you pick five books from a shelve with twelve books, such that no two books you pick are consecutive? This is a problem that I have encountered in several different forms ...
2
votes
1answer
46 views

Number $e(n)$ of trees with $n+1$ unlabeled vertices $n$ labeled edges

How do I find the number $e(n)$ of trees with $n+1$unlabeled vertices $n$ labeled edges. We're suppose to give a simple bijective proof, I guess? Help appreciated!
1
vote
3answers
118 views

Distinguishable telephone poles being painted

Each of n (distinguishable) telephone poles is painted red, white, blue or yellow. An odd number are painted blue and an even number yellow. In how many ways can this be done? Can some give me a ...
14
votes
2answers
161 views

Simplifying $\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$

How do I simplify: $$\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$$ Should I use modulos or should I factor them? Or any I suppose to use combinatorics? Any one have a ...
1
vote
1answer
66 views

Power series of $f(x)=\sqrt{\frac{1+x}{1-x}}$

How do I find the power series form of $\,f(x)\,$: $$\displaystyle f(x)=\sqrt{\frac{1+x}{1-x}}$$ I tried to multiply the fraction by $\,\dfrac{1+x}{1+x}\,$ but it didn't help...
3
votes
2answers
1k views

In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other?

In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other? I tried to draw diagrams onto a $8\times8$ square but I'm only getting $16$ ...
20
votes
4answers
351 views

Ways to fill a $n\times n$ square with $1\times 1$ squares and $1\times 2$ rectangles

I came up with this question when I'm actually starring at the wall of my dorm hall. I'm not sure if I'm asking it correctly, but that's what I roughly have: So, how many ways (pattern) that there ...
2
votes
5answers
752 views

Different ordered triples $(a,b,c)$ of non-negative integers

How many different ordered triples $(a,b,c)$ of non-negative integers are there such that $a+b+c=50$? I tried to list the possibilities but the list is way too long, I know how to find the ordered ...
4
votes
1answer
105 views

creating a more complex sudoku (69x6)

I would like to know if its possible to create a "sodoku" with this rule: in a table $69\times 6$ i want to put in the numbers from $1$ to $46$ repeated $9$ times, each numbers HAS to stay in the same ...
3
votes
2answers
65 views

How to solve the non homogeneous equations

I am looking for the proof of the following I have the following equations $x_1^2+x_2^2+x_3^2+....+x_n^2=1$, $x_1+x_2+x_3+........+x_n=1$ $0 \leq x_i\leq 1$ for-all $i$ I believe that the only ...
12
votes
5answers
1k views

Proving identities like $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially

I have to give a combinatorial proof of $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$ I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have ...
5
votes
3answers
109 views

Closed formula for linear binomial identity

I have the following identity: \begin{equation} m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1} \end{equation} I solved for the values and learned of the interpretation of W, X, Y, and ...
2
votes
2answers
586 views

Combinatorial restriction on choosing adjacent objects

I am having trouble understanding an approach to the following problem. Suppose 14 books are aligned in a bookcase. How many ways can we choose 5 books so that no adjacent books are chosen? I think my ...
1
vote
1answer
54 views

Counting Card hands with various restrictions

I would like to know if my solutions are correct for the following three combinatorial card questions. In each question, assume we have a standard deck of cards (13 ranks, and 4 suits). How many ...
11
votes
3answers
521 views

Arc sums for a circle of $k$ positive integers whose total sum is $n$

This problem got me thinking about the following more general scenario: Suppose you have $k$ positive integers with total sum $n$, and you arrange them in a circle. Given such an arrangement, you ...
15
votes
2answers
383 views

Why are braid numbers of the form $Q_h^2$ or $2 \times Q_h^2$?

Consider two piles of $h$ playing cards each, all distinct. Repeatedly take one of the cards on top of one of these two piles and move it on top of one of two new piles, until both of the new piles ...
3
votes
1answer
1k views

Putnam 2012 B3 - Tournament combinatorics

A round-robin tournament among $2n$ teams lasted for $2n-1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ ...
7
votes
2answers
274 views

Mean and Median in a Classic River Crossing Problem

Consider the following classic problem: Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the ...