This tag is for basic 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
3answers
29 views

What is the relationship between the some of the first n natural numbers and the number of unique pairs in n+1

The sum of the first $n$ natural numbers is $\displaystyle\frac{n}{2}(n+1)$ $\displaystyle {n+1 \choose 2}$ is $\displaystyle\frac{n}{2}(n+1)$ Obviously they are equal, but how should I think ...
3
votes
1answer
23 views

How many functions? [duplicate]

How many into and onto functions are there from [k] to [n]? a) If k > n? Thus far I have S(k,n)n! However, I don't know how to calculate that. b) If k <= n?
0
votes
0answers
27 views

Is it possible to solve problems about finding the number of solutions to a linear equation with the multinomial coefficient?

I have an exercise in combinatorics: There are $6$ white balls, $8$ red balls, $4$ yellow balls and $6$ black balls. In how many ways can I pull $6$ balls? Is it possible to solve it with the ...
1
vote
1answer
21 views

combination of choosing dinner menu

Suppose I have $5$ vegetarian options to choose from, and $4$ options of meat, and I have to select three entries for dinner, which should contain at least one vegetarian option. How many types of ...
0
votes
1answer
66 views

What is the probability that at least two people have the same birthday in the same year?

Find a formula for the probability that out of n millenials, at least two will have the same birthday, where "same birthday" means same month, data, AND year. Millennials are born from 1980-1995. ...
0
votes
2answers
36 views

Find the generating function for the finite sequence 0,0,0,1,2,3,4,5

I have the sequence $\{0,0,0,1,2,3,4,5\}$ and I need to find a generating function. I found the answer to be $\sum n x^{n+2}$. However to find the nth term, I would use $n-2$, correct? But then for ...
3
votes
2answers
48 views

Average number of trials until drawing $k$ red balls out of a box with $m$ blue and $n$ red balls

A box has $m$ blue balls and $n$ red balls. You are randomly drawing a ball from the box one by one until drawing $k$ red balls ($k < n$)? What would be the average number of trials needed? To ...
0
votes
0answers
25 views

Combination repetition

What is the difference between combination with repetition and combination of identical objects? Really having a hard time determining the differences between the two and understanding when to use the ...
0
votes
1answer
20 views

How to calculate Permutations if you have more places than distinct objects

I'm having trouble using a Permutation formula for finding out how many different ways there are to seat 264 people at 481 desks. The trouble I'm having is that in the Permutation formula (nPr = n! / ...
0
votes
1answer
29 views

The number of non-surjective functions between 4-element sets

Could someone explain to me how I go about answering this question? I know it might be simple, in which case I be quite embarrassed, but I've looked online for the past while and have not found a good ...
0
votes
2answers
59 views

Stroeker Problem: Sum of consecutive cubes being a perfect square

I encountered to following textbook problem in the book 'Introduction to probability' (p.34) by Blitzstein and Nwang. NO homework, but self-study ! Part a) is no problem, but b) struck me down. ...
3
votes
1answer
56 views

What are you if you specialize in combinatorics

If you specialize in number theory or in computer science (this for cryptology) you are a number theorist, a computer scientist, a cryptologist. But how do you call someone who specializes in ...
0
votes
1answer
40 views

Chance on pairs when picking 'Sinterklaas tickets'

In the Netherlands, we have a tradition called Sinterklaas. He's a saint, lives in Spain, comes with a steamboat to the Netherlands somewhere in the end of November, and on the 5th of December he ...
0
votes
2answers
32 views

How many decimal strings of length 55 contain exactly ten 7s?

Some more questions, I believe I have them right but I have no way to check my answers. How many decimal strings of length 55 contain exactly ten 7s? The way I think this one is answered is by ...
0
votes
0answers
95 views

What is the sum of the divisors of 14,601,359?

What is the sum of the divisors of 14,601,359? $$14,601,359^2 -1 = 213,204,941,168,520$$ I'm not too sure if my calculation or logic is correct.
1
vote
4answers
37 views

How many sets of size five are there from the natural numbers 1-100 that contain exactly two odd numbers?

Hey I would like to know the correct approach to this problem. I think I'm close but I'm confusing myself. How many sets of size five are there from the natural numbers 1-100 that contain exactly ...
1
vote
2answers
75 views

Candidates in an exam

443 candidates enter the exam hall. There are 20 rows of seats I'm the hall. Each row has 25 seats. At least how many rows have an equal number of candidates. My attempt Seat 25 in the first row 24 ...
0
votes
3answers
32 views

Mrs Reed safe combination

Mrs Reed forgets the number combination to her safe. The combination has $4$ numbers each is a $1$ digit number. The $4$ digits add up to $10$ and there are no zeros. How many times does Mrs Reed have ...
1
vote
1answer
376 views

Divide a set of $n$ elements into $k$ subsets having equal sum

Given $n$ ( $n$ <= 20) non-negative numbers. Is there / Can there be an algorithm with acceptable time complexity that determines whether the n numbers can be divided into $k$ ( $k$ <= 10) ...
3
votes
1answer
73 views

Expected value of the longest run of red balls

Suppose there's an urn containing $r$ red balls and $b$ blue balls. At each trial, I'm drawing a ball at random from the urn, without replacement. Let $R$ denote the event of drawing a red ball, and ...
0
votes
1answer
35 views

prove binomial multiplication less than 1

please show me how to prove the following. Given $m >= n,n\geq2$ prove $\binom mn$ $\cdot \frac{1}{n^m} < 1$ ------UPDATE-------- Given the inequalities: $(\frac{m}{n})^n \le \binom mn \le ...
0
votes
2answers
42 views

Combination Counting puzzles me…

A test has $6$ questions with $4$ possible answers for each (a,b,c,d), plus $5$ more true or false questions. How many students are required to take the test to guarantee that $2$ write down the ...
5
votes
0answers
197 views

Minimal number of moves needed to solve a “Lights Out” variant

Lights Out was a popular puzzle in which all lights in some device had to be turned off by pressing on them, which turned off all neighbouring lights as well. We consider instead the same variant ...
1
vote
1answer
29 views

Combinatorics: Using a Generating Function to Count the Number of Ways of Selecting a Hand From a Triple Deck

Use a generating function to determine the number of ways to select a hand of m cards from a triple deck, if there are n distinct cards in a single deck. Verify that your expression produces the ...
1
vote
1answer
29 views

Checking whether to use a permutation or combination

So I'm studying for my Discrete Math final tomorrow and wanted to make sure I had a clear understanding of permutations versus combinations - it's my understanding that you use permutations when order ...
1
vote
1answer
39 views

Number of overlapping columns

Consider an $m \times n$ matrix $A$ with $m<n$. It is well-known that number of ways of choosing $k$ columns out of $n$ from $A$ is $\binom{n}{k}$, where ($k<m<n$). What is the number of ways ...
2
votes
1answer
38 views

Combinatorics: Number of Six-Card Hands That Can Be Dealt from r Combined Decks

I am having trouble solving this combinatorial problem dealing with the number of different card hands possible from multiple decks of identical cards. Here is the exact question: Use a combinatorial ...
0
votes
2answers
41 views

Combinatorics: pick 2 from group A with 5 elements and 3 that stay in order from group B with 6 elements?

So basically: how many way are there to pick 2 elements from group A which has 5 elements, and pick 3 elements from group B which has 6 elements, provided the 3 elements stay in order in the new 5 ...
1
vote
2answers
32 views

How to prove that all of pascal's triangle is composed of integers.

I want to prove that all of n choose k values, i.e. pascal's triangle values are integers. It is pretty obvious, since it is a recursive definition with each term being the sum of its preceding ...
2
votes
1answer
63 views

Average number of linear factors in a monic polynomial of degree $n$ over $\mathbb{F}_p$

Let $p$ be a prime and $P_n$ the set of all monic polynomials with coefficients in $\mathbb{F}_p.$ I am interested in the average number of linear factors of polynomials in $P_n.$ In an exercise in ...
1
vote
2answers
27 views

ordinary generating function of some sequence

What is the ordinary generating function of the sequence whose general term is $a_n = {n+k \choose k}$?. I cannot find it in the list given in the book generatingfunctionology, by Herbert S. Wilf. Is ...
0
votes
1answer
43 views

Cocktail Party/Graph Theory Problem

15 people are at a party. If in every group of 3 people, at least 2 do not know each other, what is the greatest possible number of pairs of people that know each other? I've been working on this for ...
1
vote
0answers
23 views

a problem with computing binomial coefficients

I have a problem with computing the binomial coefficient in polynomial algebra. Let we have $a=(a_1,...,a_n)$ and $b=(b_1,...,b_n)$ as an n-tuples such that $ (0,...0) \leq a ,b \leq ...
1
vote
0answers
38 views

Abiguous dates such as $8/3/2007$

How many ambiguous dates are there in a year? An ambiguous date is one like $8/3/2007 $ which could either mean the $8$th of March or the $3$rd of August. Is it right to say that $1/1/2007$ must mean ...
1
vote
2answers
29 views

seat arrangement possibilities

What could be possible arrangements for the below? A, B, C, D and E are sitting on a bench. A is sitting next to B, C is sitting next to D, D is not sitting with E who is on the left end of ...
0
votes
0answers
15 views

Calculating ONeill prices in combinatorial auctions using the dual (Linear programming)

I am trying to calculate the O’Neill prices[1] for the individual atoms in a combinatorial auction. The method is: Solve the IP to find the optimal allocation for the auction. Remove the integer ...
1
vote
2answers
30 views

Simple Combinatorial Proof [duplicate]

$$ \sum_{i=0}^n {n \choose i} i = n2^{n-1} $$ I am having trouble formulating a combinatorial proof. An algebraic proof is quite simple, where one expands $(1 + x)^{n}$ and then takes the ...
0
votes
1answer
15 views

Possible combinations for this example

I'm currently writing about databases and superkeys and I need a little help with the following issue. For one element: Elements: A Combinations: A For two ...
0
votes
0answers
40 views

Expected number of days on which at least two of 50 people were born

Question A group of 50 people are comparing their birthdays. Find the expected number of days in the year on which at least two of these people were born. Answer $$ ...
0
votes
1answer
48 views

Subset sums and conditions

For a given $n$-element set $N$, how can I find all $r$-element subsets of $N$ such that sum of all elements of $r$ is: $(i)$ less than $a$ $(ii)$ greater than $a$ $(iii)$ equal to $a$ ? Further ...
1
vote
1answer
40 views

how to generate rook polynomial

I've encountered rook polynomials. I just can't seem to understand how to generate them by hand for small examples such as 3x3 boards. Take for instance: $$\begin{matrix} 1 & 1 & 0 \\ 1 ...
1
vote
1answer
23 views

Question about a method in elementary combinatorics.

I'm reading Martin's: Counting: The Art of Enumerative Combinatorics. How many ways are there to arrange the letters in NASHVILLETENNESSEE with the first N precending the first S and with the ...
0
votes
2answers
51 views

Combinatorics - Am I doing this properly?

I'm working on an assignment and I'm not sure if I'm doing it properly so I figured I'd ask and make sure. The question is, a university gives each student a 6 digit code for a student number. a) ...
0
votes
2answers
60 views
0
votes
1answer
41 views

Combinatorics, marks to students

please am I right in my solutions for these problems ? There was a test in a school, but teacher lost all the completed tests. He has to give some points to studens. a)How many possibilities are ...
1
vote
0answers
17 views

Permutations with repeated elements [duplicate]

Say you have n digits and you want to see how many different numbers you can form with these digits (i.e. all possible numbers, not only the ones that are n digits long). These digits however aren't ...
1
vote
3answers
61 views

Amount of binary strings

i `ve got this problem, can you help me ? I can solve subquestion a) but i really don`t have a clue how to find recursive formula. S_n is the amount of binary strings with size n, which don’t ...
0
votes
1answer
23 views

Calculating the probability of a combination with repetition

If I have n colors, (Let's say n=3 , blue=0, red=1 and green=2). And we have r boxes (Let's say r=5). So we have these combinations (with repetition). ...
0
votes
1answer
47 views

Digit sum of natural numbers in interval

can you help me with this problem ? How many natural numbers $n$, $1 ≤ n ≤ 10^4$, with digit sum $= 7$, can you find ?
3
votes
2answers
120 views

Calculating the number of combinations we can put people in a queue with some restrictions

Suppose we have $n$ number of persons, all with different heights. We need to stack them such that only $x$ are seen from the front and $y$ are seen from the back. Smaller people are hidden behind ...