Tagged Questions
1
vote
1answer
49 views
number of ways to make $2.00
How many different ways can you make $2.00 using only 1 cent, 5 cent, 10 cent, and 25 cent pieces, and 1 and 2 dollar bills (there are 100 cents in a dollar)? I have worked out an equation:
$$p + 5n ...
1
vote
2answers
48 views
Is my solution correct? Generating functions question: How many non-negative solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
so we began studying this subject, and I tried solving this question: How many non-negative and whole ($\in \Bbb Z$) solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
I would like to ...
2
votes
5answers
66 views
Finding the number of non-neg integer solutions?
How would I find the number of non negative integer solutions to this problem?
$$x_1 + x_2 + x_3 + x_4 = 12$$ if $0 \leq x_1 \leq 2$.
2
votes
3answers
58 views
Ball-counting problem (Combinatorics)
I would like some help on this problem, I just can't figure it out.
In a box there are 5 identical white balls, 7 identical green balls and 10 red balls (the red balls are numbered from 1 to 10). A ...
0
votes
0answers
22 views
The calculation of partitions p(n) [duplicate]
Can anybody help me with this in any sense.
Prove that $ p(n+2)+p(n)\ge 2p(n+1)$.
This question is from Biggs book on discrete maths but must have read the chapter so
many times and can't figure it ...
2
votes
1answer
29 views
Counting flower and committee questions
$1$) You want dozen roses. The florist has white, pink, red, and violet roses. How many possible ways could you make the order?
$2$) There are $35$ men and $15$ women. Committee needs to have four ...
3
votes
2answers
26 views
Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem
So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...
1
vote
1answer
17 views
Even weighted codewords and puncturing
My question is below:
Prove that if a binary $(n,M,d)$-code exists for which $d$ is even, then a binary $(n,M,d)$-code exists for which each codeword has even weight.
(Hint: Do some puncturing ...
10
votes
3answers
132 views
Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
Prove
$$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$
I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement ...
2
votes
3answers
57 views
How many numbers between 1 and 10,000,000 don't have the sequence 12? Inclusion-exclusion problem
I got the following question:
How many numbers between 1 and 10,000,000 don't have the sequence 12? This is an inclusion-exclusion problem. Sadly I didn't fully understand its concept, so I tried ...
1
vote
1answer
140 views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
Moderator Note: This is a current contest question on codechef.com.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i ...
1
vote
1answer
44 views
binary circle - difficult question
I ran into this question and I'm not really sure how to start.
we are looking at 100 0/1's that are written arround a circle. for a binary sequence $w$,
we'll define $n_{w}$ as the number of times ...
1
vote
1answer
28 views
Combinatorial Techniques: Putting two and two together
This is a $3$-part question. I got the first two parts, but could not get the third part (which uses the first two parts):
Pick sequence of $8$ coins from sack of $40$ coins, containing $10$ pennies, ...
1
vote
1answer
50 views
to find disconnected graphs
We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
0answers
28 views
is the $d$-dimensional arrangement of Trees still $NP$-hard?
The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
1
vote
3answers
61 views
The number of bijections $f$ of $\{1, 2,…, n\}$ such that $f(i) \ne i$ for any $i$
Show that the number of bijections $f$ of $\{1, 2,..., n\}$ such that
$f(i) \ne i$ for any $i$ is equal to $$\sum_{j=0}^{n}(-1)^j\frac{n!}{j!}.$$
Can I get some help for the above problem? I am ...
3
votes
1answer
35 views
Dividing vertices into pairs
Given a graph with $2n$ vertices. Every vertex has got a degree at least $n$. Prove that we can divide vertices into pairs which in each pair each vertex is connected with it's neighbor.
Thanks for ...
3
votes
1answer
66 views
A combinatorial identity with Pochhammer's symbol
Let $m,k$ be an positive integers with $k\le m$. I am trying to prove $$\sum_{j=0}^k{\frac{1}{2}\choose k-j}\frac{2^{2j}(m+j)!}{(m-j)!(2j)!}=\frac{P(n,k)}{(2k)!}$$
where $n=2m+1$ and ...
2
votes
1answer
59 views
A combinatorial identity related to Chebyshev differential equation
Let $m,k$ be an positive integers with $k\le m$. Does anyone have a proof that $$\sum_{j=k}^m {2m+1\choose 2j+1}{j\choose k}=\frac{2^{2(m-k)}(2m-k)!}{(2m-2k)!k!}?$$
This is related to Chebyshev ...
8
votes
1answer
152 views
Function mapping challange
For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant
mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$
and $f(k) = f(f(k + 1))$.
This is ...
1
vote
0answers
30 views
Non-independent two consecutive draws from two urns
Suppose there are two urns: in urn A, there are r red balls and w white balls. In urn B, there are b black balls.
Suppose we do the following experiment: draw k balls from urn A. Among those k balls, ...
7
votes
2answers
180 views
maximum number of edges to be removed to possess a property
I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
1
vote
2answers
38 views
Could graph theory aid in the understanding of comparison sorting algorithms?
I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.
Up to $n=15$, we know how many comparisons between elements one must make to ...
3
votes
1answer
130 views
diameter and radius of a regular graph
I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
2
votes
1answer
30 views
Number of circular combinations with no adjacent members.
Suppose I have to place 3 identical letters on a circular table which has 7 slots in such a way that no two letters are in consecutive slots. In how many ways can I do this?
Can this be generalized ...
2
votes
2answers
41 views
Counting problem: Assigning students to dorm rooms
This was a question on a recent test and I was hoping for a conclusive answer and reasoning behind it.
A local university housing office has a problem. It has 11 students to squeeze into 3 dorm ...
2
votes
2answers
41 views
Number of rectangles with odd side lengths on a chess board?
Given an 8x8 chess board, how do we find the total number of rectangles with odd side lengths?
(Both sides have odd length).
In general, what would be an elegant method to deal with problems like ...
1
vote
2answers
49 views
Monotonic Lattice Paths and Catalan numbers
Can someone give me a cleaner and better explained proof that the number of monotonic paths in an $n\times n$ lattice is given by ${2n\choose n} - {2n\choose n+1}$ than Wikipedia
I do not understand ...
1
vote
1answer
31 views
Generating functions of partition numbers
I don't understand at all why:
\begin{equation}
\sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1}
\end{equation}
Where $p_n$ is the number of partitions of $n$. Specifically ...
2
votes
2answers
38 views
Seating Multiple People at Multiple Tables
In how many ways can we seat 100 people around 20 different circular
tables in such a way that there are five people per table?
Am I right in assuming that we're only considering unique ...
2
votes
2answers
40 views
Probability of Choosing a Card from a Deck
There were quite a few deck of cards probability problems and I went through a few but couldn't find anything close so please forgive me if this is a repeat.
The question is as follows:
Two cards ...
0
votes
2answers
23 views
How to Count Possible Orderings of Digits with Required Substrings
The question is as follows:
How many orderings of the digits from 1 to 8 contain the sub-strings 12,
23 or 34? For example, 57238614 is one such ordering since 23 appears, and
12345678 works, ...
2
votes
1answer
50 views
Permutation Formula
I am having difficulty with one minuscule detail of the permutation formula:
$$n(n-1)(n-2)\cdots(n-r+1)$$
I understand that if we proceed with an $r$-permutation, then we have $r$ amount of slots, ...
1
vote
2answers
38 views
Ordinary generating functions - I can't understand this
I'm trying to understand ordinary generating functions. I've been looking for any tutorial or some explanations about the topic but I haven't found anything useful and - what's more important - well ...
3
votes
3answers
37 views
Discrete Math, anagram combinatorics
Find the number of anagrams for the word "ALIVE" so that the letter "A" is before the letter "E" or the letter "E" is before the letter "I". By before we mean any letter previous, not just immediately ...
0
votes
0answers
21 views
Help with functions, confirming if I'm correct.
Let $\mathscr F$ denote the set of all functions from {1, 2, 3, 4} to {1, 2, 3, ... , 10}.
a) Find and simplify the number of functions $f \in \mathscr F$ so that f(1)=1 and f(2)=2.
b) Find and ...
0
votes
1answer
37 views
Help proving and counting functions.
Let $\mathscr F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$.
a) Of the two following statements, one is true and one is false. Prove the true statement. Write out the ...
2
votes
2answers
42 views
How many bit strings of length 8 start with 00 or end with 1?
How many bit strings of length 8 start with 00 or end with 1?
I know about product rule and sum rule but I'm unsure how to incorporate it into this.
Would it be like this?
x being either 1 or 0.
...
2
votes
1answer
65 views
Short proof of Hall's theorem
Studying the proof of Hall's theorem in my book I started to wonder if there is a shorter way to prove it. Following is an attempt that I think works but (being short) makes me wonder if I made a ...
2
votes
2answers
53 views
eccentricity in vertex transitive graphs
I am trying to prove the following..
If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1
vote
1answer
29 views
Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices
I need help to prove the following statement.
There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
3
votes
1answer
30 views
Smallest subset of $\{1,2,…,4n\}$ with a certain property
Fact 1: Let $A\subseteq\{1,2,...,2n\}$. If $n+1\leq |A|$, then there exists 2 elements $a,b\in A$ such that $a+b=2n+1$.
Proof: This can be shown by writing $\{1,2,...,2n\}$ as the union of $n$ ...
1
vote
1answer
79 views
Counting The Number Of Ways To Seat People At A Table
How many ways are there to seat six people around a circular table where two seatings are considered the same when everyone has the same two neighbors without regard to whether they are right or ...
1
vote
2answers
42 views
Inclusion & Exclusion: In how many permutations of the digits $0,…,9$ there's no continuity of 7 digits or more?
In how many permutations of the digits $0,...,9$ there's no continuity of 7 digits or more?
(Ex. the number 203456789 1 should not be counted)
I believe that the basic case, for the inclusion ...
1
vote
1answer
38 views
Combinatorics riddle: Sorting people in a cinema line.
Say i want to go to the cinema. There are two types of movies.
Action movie.
Drama movie.
Because action is more interesting it costs 50$. And the cost for drama is 10€.
There are 200 people ...
1
vote
1answer
32 views
8 friends, 7 nights, invite 4 every night, all of the friends must be invited, how many options?
Assume I have 8 friends, I want to invite 4 friends each night for 7 night so everyone will be invited at least once. How many combinations are there to do it?
I think I'm supposed to use the ...
0
votes
1answer
42 views
How many ways are there to sit $n$ couples on a bench when every couple sits together?
How many ways are there to sit $n$ couples on a bench with $2n$ sits, when every couple sits together?
How many ways are there to sit the couples so that none of the couples will sit together?
2
votes
2answers
44 views
New to generating functions - how do I get the function from the sequence defined by $a_n= n$ for $n\geqslant 0$?
I'm given: $a_n= n$ for $n \geqslant 0$.
I'm quite good at recursive generating functions, but I haven't came across a simpler one like this, so I'm sure I'm just overlooking something really basic.
0
votes
2answers
43 views
Finding Integers With Certain Properties.
How many positive integers between 100 and 999 inclusive
e) are divisible by 3 or 4?
For this problem, I understand that one has to employ the inclusion-exclusion principle.
Those integers ...
2
votes
1answer
44 views
self-centered property of complement of a self-centered graph
I was working out on a problem. Came out with a result that $C_n$ is self centered graph, its complement is also self centered, infact 2-self-centered. Worked out on other few graphs which are self ...
