What is Counting problem: Definition and 58 Discussions
In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then
c
R
(
x
)
=

{
y
∣
R
(
x
,
y
)
}

{\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}
is the corresponding counting function and
#
R
=
{
(
x
,
y
)
∣
y
≤
c
R
(
x
)
}
{\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}
denotes the corresponding decision problem.
Note that cR is a search problem while #R is a decision problem, however cR can be C Cookreduced to #R (for appropriate C) using a binary search (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible).
I was reading about numerical methods in statistical physics, and some examples got me thinking about what seems to be combinatorics, an area of math I hardly understand at all beyond the very basics. In particular, I was thinking about how one would go about directly summing the partition...
I have a question and searched about at google and found an answer which I don't make sure. If there is 26 letters and 10 digits;
my answer is:
first letter: 1 way(which is A)
second letter: 26 way
third letter: 26 way
first digit: 1 way(which is 1)
second digit 1 way(which is 2)
third digit: 10...
In a school 315 girls play at least one sport. 100 play a fall sport, 150 play a winter sport, and 200 play a spring sport. If 75 girls play exactly 2 sports, how many play three?
Summary: interesting counting problem for fun
Imagine we draw a circle with diameter d and mark off sixty equal intervals like minutes on a clock. Then we draw two diameters perpendicular to one another and divide each in sixty equal intervals. Using the intervals on the diagonals we lay out a...
Since the length of day is greater by 0.21 seconds, thus the change in time = ##\frac{0.21*365*100}{60*60}## hours = 2.1 hours.
Here, I do not understand why the length of the day increases by 0.21 seconds instead of 0.2 seconds.
Homework Statement
Pamela has 15 different books. In how many ways can she place her books on two shelves so that there is at least one book on each shelf. (consider the books in each arrangement to be stacked one next to the other, with the first book on each shelf at the left of the shelf)...
Homework Statement
Given: Cn_dot = true event rate = 10 interactions/s
p(t')dt' = differential probability of an event
Homework Equations
p(t')dt' = Cn_dot * exp(Cn_dot * t') dt'
The Attempt at a Solution
[/B]
I want to sample the time interval using python. But I'm not sure how to go...
The Telephone Numbering Plan The North American numbering plan (NANP) specifies the format of telephone numbers in the U.S., Canada, and many other parts of North America. A telephone number in this plan consists of 10 digits, which are split into a threedigit area code, a threedigit office...
Homework Statement
8 friends are playing a tennis game together. How many different doubles games of tennis can they play?
Homework Equations
Combinations
The Attempt at a Solution
Well, I solved this problem by saying: we choose a group 4 people from 8 to play, so order is not important...
Homework Statement
I have 3 yellow and 7 blue marbles. I put those randomly in a line. What is the probability that no yellow marbles are next to each other?
Homework Equations
/
The Attempt at a Solution
Total amount of opportunities to put those marbles next to each other: 120
Total...
Homework Statement
Counting problems are a very tough subject to me, so if someone could give me tips, examples explaining what's really happening, that would be great.
Homework Equations
I know what permutations, variations, combinations, ... are. The problems involving only one of those...
Homework Statement
Given 9 good light bulbs and 4 defective light bulbs, how many ways can you select 3 such that you get exactly 1 defective bulb?
Homework Equations
C(n,r)
The Attempt at a Solution
I understand total ways to select is C(13,3)=286, and that total ways to select only good...
Homework Statement
An ice cream shop has a special on banana splits, and Xing is taking advantage of it. He’s astounded at all the options he has in constructing his banana split:
· He must choose three different flavors of ice cream to place in the asymmetric bowl the banana split is served...
Homework Statement
A code consists of atmost two identical letters followed by atmost four identical digits. The code must have atleast one letter and one digit. How many distinct codes can be generated using letters AZ and digits 19.
Homework EquationsThe Attempt at a Solution
//One...
A standard 8x8 chess board has but a lone rook in the bottom left corner. A rook a piece than can move any number of spaces either horizontally or vertically. If the rook can only move up and to the right, how many possible paths does it have to the top right corner?
I think it's a pretty...
"For years, telephone area codes in the U.S. and Canada consisted of a sequence of three digits. The first digit was an integer between 2 and 9, the second digit was either 0 or 1, and the third digit was any integer from 1 to 9.
(1) How many area codes were possible?
(2) How many area codes...
we have to make n with k integers.k integers will have to be choosen from k ranges.Every range has a minimum value and a maximum value.In how many ways we can make n
according to the conditions.For example,k=4,n=10
and the ranges are :
1 1
2 2
3 3
4 4
we can make n in only one way.Another...
A quiz has 4 questions with 3 choices for each answer.
If you guess every answer, in how many different ways can you complete this test?__________
How many students must take this test to guarantee that at least 3 identical answer sheets
are submitted?__________
I know how that the answer to...
Homework Statement
How many strings of five ASCII characters contain the character @ ("at" sign) at least once? [Note: there are 128 different ASCII characters.]
Homework Equations
The rule of product and inclusionexclusion principle are relevant.
The Attempt at a Solution
The correct...
There are 4 people in a class. Among them, they are to solve 17 difficult math problems.
They form 17 committees – one committee to deal with each of the 17 problems.
Prove that at least 2 of these committees contain exactly the same people.
PLEASE EXPLAIN HOW EACH STEP TO REACH TO THE...
Homework Statement
There are 8 seats in a railway compartment. In how many ways can 8 people be seated if 2 must have their backs to the engine and 1 must face the engine?
Homework Equations
The Attempt at a Solution
So 3 of them must be in those exact positions so I tried...
Homework Statement
How many ways can you place 8 rooks on a chess board so that no 2 rooks attack each other.
Assume the rooks are identical.
Chess board is 8 by 8.
The Attempt at a Solution
To place the first rook I would have 64 choices.
for the second rook I would have 49 choices...
Question and my solution is in the paint document.
Case 1  Case 3 represents all possible combinations of string of length 4 with exactly three 9's.
The d represents a digit that is not 9.
d = 0 or 1 or 2 or 3 or ... or 8: This is 9 options.
Notice that none of the cases 1  3 have identical...
Question 1:
My question is how do I know when to use the permutation theorem or comination theorem?
Theorem in paint document
I'm asking because I would have used permutation thm. on 46 but I was wrong.
Problem 46 b. and Problem 47 a. seem similar. The two main differences...
Im trying to find all combinations of P6. Book solution in paint doc.
My solution: Please tell me where I am going wrong.
P6: Password of 6 characters
1. Each password must contain at least one digit,
2. Each character of password can be a digit or uppercase letter.
Let P61 be defined...
Nabeela Zubair on Facebook writes:
How I can solve this problem?
Students are choosing 2 colors to be used as school colors. There are 10 colors from which to choose. How many different ways are there to choose 2 different colors?
Total Colors 3 4 5 6 7 8 9 10
# of 2color Comb. 3 6 10
Homework Statement
Write a function (count s x) that searches a data structure composed of pairs
(arbitarily nested) for a symbol x and returns the number of times it occurs.
Homework Equations
Assuming you have the correct function written, you should get the following:
(count...
Homework Statement
How many anagrams with 4 distinct letters and that have two of the letters "a", "b" and "c" can you make using the first ten letters of the alphabet?
Homework Equations
The Attempt at a Solution
First I assume that by anagram they mean letters arranged in any...
So over the course of yesterday and the day before that I've spent a few hours thinking about these problems;
1. Given a circle, place n points arbitrarily* on the edge and connect every point to every other point with a straight line. How many intersections do you get?
2. Given the same...
Homework Statement
For this problem assume that the 365 dates of the year are equally likely as birthdays.
b)Find the probability that in a group of n people, at least two have the same birthday.
Homework Equations
The Attempt at a Solution
Well I am not really sure what...
This is a pretty basic counting problem, but it is confusing me to no end. I know the answer (from the back of the book), but I just don't understand the answer.
Homework Statement
Find the probability of getting exactly 4 numbers correct in a lottery where 6 numbers are chosen from 49...
Homework Statement
I already have the solution to the problem. Just need some help deciphering the logic behind it.
There are V balls, which are identical except for their color. N of them are blue and VN are red. We place the balls inside a box so that V/2 balls are on each side...
How many ways can you place 8 distinct flags on 3 distinct poles if no pole can be empty.Im not sure how to approach this problem because writing out all the possibilities would take a lot of time
So I was thinking it would be something like
8C3 to select the three flags that have to be placed...
Homework Statement
A teaching event takes two days and involves n people. Some of the
people give a talk on day 1, some others give a talk on day 2.
Everybody gives at most 1 talk, and there can be some teachers who
do not give a talk in either of the two days. At the end of the event, a...
Hi everyone, I want to make sure if I solved this problem correctly. Thanks in advance.
Homework Statement
Rachel invited her friends to dinner. She has 10 friends, but only 6 places to sit them in her (circular) table.
a) Count the ways to sit the guests if order is not important.
b) If...
Homework Statement
100 hundred people are to be divided into 10 discussion groups with 10 people in each group
how many ways can this be done.
The Attempt at a Solution
So if we think of it as people on a 10 by 10 grid their are 100! ways of populating the grid and then 10! ways or...
Homework Statement
A software company uses a 20 character product key that new buyers of their
product must use during installation to successfully install the software in their
computers. The structure of these product keys is as follows. Repetitions are
allowed unless explicitly...
Homework Statement
A computer operating system allows files to be named using any combination of uppercase letters (AZ) and digits (09) But the number of characters is at most 4 , And there must be at least 1 letter in each file name.
The Attempt at a Solution
So I break this up into 4...
Homework Statement
Let r be a positive integer. For any number x, let
(x)r = x(x1)(x2)...(xr+1)
Show that
(1/2)r = (1)rr!22r(2r take r)
Homework Equations
by "2r take r" I mean what is usually denoted by (n / r) (written like a fraction but without the bar) and is calculated...
Homework Statement
social security number is a 9 digit number.
the first digit may be 0
a. How many numbers are available
b. How many are even
c. How many have all of their digits even
d. How many read the same forward and backward
e. How many have none of their digits equal to...
Homework Statement
A license plate has three letters followed by three numbers. Suppose the digits from 0...9 can be used, except all three digits cannot be zero, and that any letter from AZ with repeats can be used. How many plates are possible?
Homework Equations
My question is on...
I was confonoted with the following problem today, and thought it was interesting enough to discuss it here:
Homework Statement
You have a box with balls numbered 1,2,3...n.
Suppose you began, by taking out balls numbered 1–100
and then put ball 1 back. Suppose you then removed balls...
Homework Statement
How can you get from this
\frac {z(i1) +i +1} {z(1i) +i +1}
to this
= \frac { z1 } {z i}
?
The Attempt at a Solution
SageMath does not simplify the result any further from the beginning.
The equivalence is based on some high Math.
I am not sure how you...
Homework Statement
Show that there is a one to one correspondence between even and odd subsets of the set {0, 1...n}.
Homework Equations
They want a combinatorial proof so basically a proof based on counting?
Perhaps (n choose k) = (n choose nk)
The Attempt at a Solution
I've...
Homework Statement
A committee of seven is to be chosen from 8 men and 9 women.
a) how many possible committees are there?
b) how many committees contain at least 6 woment?
c) if bob and alice cannot be on the same committee because they cannot work together well, how many committees are...
Homework Statement An organization of 100 members, 6 of whom are officers, plans to elect delegates to attend a convention. There are to be 2 delegates; one must be an officer and the other cannot be an officer. In addition, an alternate delegate, either an officer or not, will be elected and...
Homework Statement
The question says:
A chain of stereo stores is offering a special price on a complete set of components (reciever, compact disc player, speakers). A purchaser is offered a chocie of manufactuer for each component:
Reciever: Kenwood, Onkyo, Pioneer, Sony, Yamaha
Compact...
To open a safe, 4 number buttons must be pressed, in the correct order. Over time, the 4 numbers buttons of the code fade. A thief notices the faded buttons, so knows that the code consists of those 4 numbers.
How many possible codes are there?
4 numbers can be arranged in 4! different...