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





{\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}
is the corresponding counting function and






{\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 Cook-reduced 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).

View More On Wikipedia.org
  1. AndreasC

    I Problems involving combinatorics of lattice with certain symmetries

    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...
  2. R

    License Plate Combinations: Clarifying the Math

    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...
  3. A

    MHB Counting Problem: In a school 315 girls play at least one sports

    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?
  4. D

    I Counting Corners on a Moving Grid: Exploring a Fun Mathematical Problem

    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...
  5. J

    Is the length of a day actually increasing by 0.21 seconds?

    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.
  6. R

    Counting problem - how many ways....

    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)...
  7. S

    Determining the time interval in a radiation counting problem

    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...
  8. B

    MHB The Telephone Numbering Plan in North America: Counting Possible Numbers

    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 three-digit area code, a three-digit office...
  9. M

    Combinatorics: tennis game with 8 people

    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...
  10. M

    Counting problem -- Lining up colored marbles....

    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...
  11. M

    How Can I Master Complex Counting Problems Involving Multiple Principles?

    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...
  12. mishima

    Counting Problem (ways of choosing 3 with conditions)

    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...
  13. G

    Combinatorics - counting problem

    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...
  14. 22990atinesh

    Counting Problem : A code consists of at-most two....

    Homework Statement A code consists of at-most two identical letters followed by at-most four identical digits. The code must have atleast one letter and one digit. How many distinct codes can be generated using letters A-Z and digits 1-9. Homework EquationsThe Attempt at a Solution //One...
  15. PsychonautQQ

    Interesting 8x8 chess board counting problem

    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...
  16. C

    MHB More statistics: counting problem

    "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...
  17. A

    Calculating the Number of Ways to Make n with k Integers from Given Ranges

    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...
  18. M

    MHB Counting problem involving numbered cards

    How to solve ii (b) ? Thanks in advance.
  19. Y

    MHB Counting problem - Multiple choice test

    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...
  20. N

    Counting problem: 5-character ASCII strings containing at least one @

    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 inclusion-exclusion principle are relevant. The Attempt at a Solution The correct...
  21. Y

    MHB Solve 17 Difficult Math Problems: Proving At Least 2 Committees are Identical

    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...
  22. L

    Seating Arrangements in a Railway Compartment

    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...
  23. C

    Counting Ways to Place 8 Rooks on a Chess Board without Attacks

    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...
  24. M

    Counting problem (book wrong?)

    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...
  25. M

    Permutation/Combination Theorem: Solving Problem 46b & 47a

    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...
  26. M

    Solve the P6 Counting Problem: Unlock 10*365 Password Combinations

    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...
  27. Sudharaka

    MHB Nabeela Zubair's Question on Facebook (Counting Problem)

    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 2-color Comb. 3 6 10
  28. K

    How to Write a Counting Function in Lisp for a Data Structure of Pairs

    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...
  29. V

    Counting problem involving anagrams

    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...
  30. G

    Lines on a circle - a counting problem

    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...
  31. C

    Counting problem relatively hard I think.

    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...
  32. B

    Basic, but confusing, counting problem

    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...
  33. O

    Stat Mech : Balls in a box counting problem

    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 V-N are red. We place the balls inside a box so that V/2 balls are on each side...
  34. P

    Solving 8 Flag Placement Problem on 3 Poles

    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...
  35. P

    Combinatorics teaser (counting problem)

    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...
  36. R

    A counting problem (combinatorics)

    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...
  37. C

    Counting Problem Homework: 100 People into 10 Grps of 10

    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...
  38. C

    Solving a Counting Problem in Software Product Key Creation

    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...
  39. C

    Kinda tricky counting problem.

    Homework Statement A computer operating system allows files to be named using any combination of uppercase letters (A-Z) and digits (0-9) 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...
  40. C

    Permutation and counting problem

    Homework Statement Let r be a positive integer. For any number x, let (x)r = x(x-1)(x-2)...(x-r+1) Show that (-1/2)r = (-1)rr!2-2r(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...
  41. C

    Counting problem social security numbers

    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...
  42. L

    Fundamental Principle of Counting Problem

    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 A-Z with repeats can be used. How many plates are possible? Homework Equations My question is on...
  43. D

    Counting problem involving infinite

    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...
  44. S

    Counting problem with Mobieus function

    Homework Statement How can you get from this \frac {z(i-1) +i +1} {z(1-i) +i +1} to this = \frac { z-1 } {-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...
  45. P

    Combinatorial counting problem

    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 n-k) The Attempt at a Solution I've...
  46. P

    Counting problem posted by pcddizzle

    Evan pulls one marble randomly from a bag containing 6 red marbles, 3 green marbles, and 1 yellow marble. What is P(red or yellow)
  47. D

    How Many Possible Committees Can Be Chosen from a Group of 8 Men and 9 Women?

    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...
  48. T

    Counting problem involving picking delegates

    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...
  49. M

    Did I do this counting problem correct?

    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...
  50. D

    How to Solve a Faded Safe Code: Math Counting Problem Explained"

    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...