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)

1
vote
2answers
132 views

How many ways can 8 children facing each other in a circle change seats so that each faces a different child.

Need some help with this problem. A carousel has eight seats each representing a different animal. Eight children are seated on the carousel but facing inward, so each child is staring at another. In ...
5
votes
4answers
118 views

${{p-1}\choose{j}}\equiv(-1)^j \pmod p$ for prime $p$

Can anyone share a link to proof of this? $${{p-1}\choose{j}}\equiv(-1)^j(\text{mod}\ p)$$ for prime $p$.
0
votes
1answer
52 views

How to show is the following sum zero

Let $E_N = \{ (e_1, e_2, ... , e_N): e_j \in \{-1, 1\} \}$. Now for each fixed $e = (e_1, e_2, ... , e_N) \in E_N$ there are $\binom N 2$ products of the form $e_ie_j$ for $i \neq j$. Note that each ...
0
votes
1answer
20 views

Confusion related to the tractability of an integral

I have this confusion related to the tractability of an integral. In the attachment given below for equation 3 why is it intractable. Further in equation 4 they have said that there are $K^n$ ...
0
votes
1answer
254 views

The number of non-negative integral solutions to the equation $4x_1+x_2+x_3=n$

We know that $x_1+x_2+x_3=n$ has ${{n+2}\choose{2}}$ solutions, but how do we calculate the solutions to an equation such as $4x_1+x_2+x_3=n$? Please do explain! Thanks!
4
votes
3answers
335 views

Partitions of $n$ into distinct odd and even parts proof

Let $p_\text{odd}(n)$ denote the number of partitions of $n$ into an odd number of parts, and let $p_\text{even}(n)$ denote the number of partitions of $n$ into an even number of parts. How do I ...
3
votes
0answers
76 views

Find all distinct binary de Bruijn sequences

Messing around with numbers has lead me to the following problem, which I am struggling with. (No, not a homework question, just a problem I've thought up myself): A binary De Bruijn sequence of ...
0
votes
3answers
39 views

Simple combinatorics help including boxes and objects

How many ways are there to distribute $k$ balls into $n$ distinct boxes ($k < n$) with at most one ball in any box if (a) The balls are distinct? (b) The balls are identical? My ...
0
votes
0answers
24 views

Closed form for generating function [duplicate]

How do I find the closed form for the generating function $$G(x) = \sum_{n \geq 0} c(n,k) \frac{x^n}{n!} $$ where $c(n,k)$ is the number of $n$-permutations with $k$ cycles.
1
vote
1answer
64 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
2answers
307 views

What is the probability of of drawing at least 1 queen, 2 kings and 3 aces in a 9 card draw of a standard 52 card deck?

The title problem is just one specific example of a more generalized problem that I'm trying to solve. I'm trying to write an efficient algorithm for calculating the probability of at least k ...
2
votes
4answers
330 views

Round Table Adjacent Seats Problem

If there are 10 seats in a round table and 7 people are already sitting in some random pattern(edit: uniform distribution, thank you for the correction) what is the probability that the next two ...
13
votes
1answer
306 views

Enumerative Combinatorics

Sam has $255$ cakes, each labeled with a unique non-empty subset of $\{1, 2, 3, 4, 5, 6, 7, 8\}$. Each day, he chooses one cake uniformly at random out of the cakes not yet eaten. Then, he eats that ...
3
votes
1answer
275 views

The question about the word of “Mathematics”.

I have got a problem that contains three things; i) How many different words can be formed by a rearrangement the letters of the word "mathematics"? ii) How many of these words begin and end with t? ...
0
votes
1answer
61 views

A new restaurant has opened. They have 100 items to chose from! Of those items…

I need some help with this problem. A new restaurant has opened. They have 100 items to chose from! Of those items… 45 are fattening 45 are gross 44 are ice-cold 10 are both fattening and gross 18 are ...
0
votes
0answers
16 views

Overlap with infinite binary vectors

Assume we have an infinitely long vector with binary values $0$ and $1$, called $A$. Assume that there is infinitely many of both values in $A$. Make a new vector $A$ by removing the first value of ...
2
votes
2answers
42 views

Giving 4 types of presents to 5 children.

I have five children: Jackie, Tito, Jermaine, Marlon and Michael. I am going to give each of them a present. The available presents are: A candy, a paperback, a dolly, or a Mercedes. I can't give ...
0
votes
1answer
81 views

Finding a combinatorial proof of this identity: $n!=\sum_{i=0}^n \binom{n}{n-i}D_i$

Can someone prove this. Let $D_n$ be the number of derangements of $n$ objects. Find a combinatorial proof of the following identity: $$n!=\sum_{i=0}^n \binom{n}{n-i}D_i$$
2
votes
0answers
66 views

Maximum bin load for $\alpha n$ balls into $n$ bins

In a paper I am reading the author writes: A standard result concerning balls and bins shows that if we throw at least $\alpha n$ balls into at most $n$ bins, then the maximum bin load is ...
2
votes
2answers
89 views

I have ten professors, and need to pick four of them for a committee.

I have ten professors, and need to pick four of them for a committee. It is a bad idea for Hatfield and McCoy to serve together. It is a bad idea for El and Luthor to serve together. How many possible ...
2
votes
1answer
96 views

Sampling with replacement events vs. fraction coverage of a specified set

This question is related to a previous one of mine: Sampling with replacement events vs. probability of coverage Here, we are again provided a deck of $N$ cards, when $k \leq N$ of the cards bear a ...
2
votes
2answers
548 views

How many ten letter words are there with no repeated letters that contain neither the word ERGO nor the word LATER?

How many ten letter words are there with no repeated letters that contain neither the word ERGO nor the word LATER? I am thinking that there are 26^10 words with ten letters and 26P10 10 letter words ...
0
votes
1answer
43 views

Solution Verification - Combinatorial Card-Picking

I have a problem as such: How many ways are there to choose nine cards out of a standard deck of 52 cards in such a way that every suit is represented in the selection at least twice? Here's my ...
0
votes
1answer
33 views

Hanging Paintings in a Line

I am hanging ten paintings in a nice straight line. I don't want the Van Gogh to hang next to the DaVinci. I don't want the DaVinci to hang next to the Warhol. In how many ways can I hang my ...
0
votes
0answers
73 views

parity of powers of prime factors

lets consider the prime factorisation of a number N let the powers of the primes in this factorisation be a,b,c ....and so on. Is there a way to determine whether the number of powers that are even ...
1
vote
2answers
85 views

Why do we subtract 1 when calculating permutations in a ring?

$10$ persons are to be arranged in a ring shape. Number of ways to do that is $9!.$ I wonder why we subtarct $1$ in all such cases. I can imagine that if A,B,C,D are sitting in a row then ...
0
votes
1answer
39 views

Probability/counting problem.

In an experiment E, nine people are asked their birth MONTH, and the nine responses are then written down. All outcomes are equally likely. Find the probability of the event B = {NO TWO people are ...
0
votes
0answers
27 views

evaluation of $b_{n}$ in $\sum_{r=0}^{2n}a_{r}\cdot (x-100)^r = \sum_{r=0}^{2n}b_{r}\cdot (x-101)^r$ .

If $\displaystyle \sum_{r=0}^{2n}a_{r}\cdot (x-100)^r = \sum_{r=0}^{2n}b_{r}\cdot (x-101)^r$ and $\displaystyle a_{k} = \frac{2^k}{\binom{k}{n}}\forall k\geq n\in \mathbb{N}$. Then $b_{n} = $ ...
0
votes
1answer
1k views

Find probability when drawing marbles

Two marbles are drawn randomly one after the other without replacement from a jar that contains 8 red marbles, 8 white marbles, and 8 yellow marbles. Find the probability of the following events. ...
3
votes
2answers
179 views

Combinatorics help. Palindromic 6 letter sequences.

The genetic code can be viewed as a sequence of four letters T, A, G, and C. There were two parts to the question: (a) How many 6-letter sequences are there? I just said $\binom{4}{1}^6$, or ...
1
vote
0answers
73 views

Probability of two adjacent seats at a round table being available

There are Fifteen seats at a round table. There are three people already seated, their locations chosen uniformly at random. Three people wish to join the table and sit next to each other. What is ...
1
vote
1answer
158 views

About counting number of n-tuples

Let n-tuples be $(x_1,x_2,x_3,...x_n)$ and $0\le x_i<q$ ($x_i$ is integers) for $i=1,2,3,...,n$. First part of the question was about the number of n-tuples. I got this part right, (number of ...
1
vote
1answer
62 views

Probability when flipping a coin

A warped coin has probability of 0.5 of landing Heads, probability of 0.4 of landing Tails, and probability 0.1 of landing on its Edge. It is flipped 5 times. What is the probability that more Heads ...
0
votes
1answer
28 views

Sampling with replacement events vs. probability of coverage

I have a deck of $N$ cards, when $k \leq N$ of the cards bear a mark. I sample from the deck uniformly and with replacement until I find a marked card. I then erase the mark, and place the card back ...
0
votes
3answers
50 views

Counting more strings with 7 letter

Already made one sort of like this earlier (Counting strings with 7 letters), but I'm still not getting into the mindset required for this kind of tasks. Anyway, I'm given the letters A-G and.. I ...
1
vote
1answer
122 views

Combinatorics question about couples sitting around a table

I have confirmed the solution and posted below.
0
votes
1answer
89 views

Number of Young Tableaux of size n with a given number of rows and a distinct number of boxes in each row

I would like to know if there is a formula for the number of Young tableaux of size $n$ with a given number of rows, each row having a distinct number of boxes. I have seen the Hook length formula ...
0
votes
1answer
510 views

Balls and bins probability problem

$k = \sqrt n$ balls are thrown into $n$ bins. The bins are standing in a row and numbered from 1 to $n$. What is the probability that there are no two balls in the same bin or in adjacent bins??? In ...
2
votes
1answer
658 views

Counting ways to partition a set into fixed number of subsets

Suppose we have a finite set $S$ of cardinality $n$. In how many ways can we partition it into $k$-many non empty subsets? Example: There is precisely one way to partition such a set into $n$-many ...
0
votes
1answer
39 views

Unlimited Exercise

I have 5 groups with 3 different exercises (i.e. group 1 has pushups, pull-ups and dips). I am to choose one exercise from each group to make a "round". So how many rounds can I come up with using ...
0
votes
0answers
25 views

numbers on circles and combination of sums of some neighboring numbers

Let $n$ be a natural number and place $n$ numbers on a circle. For example, if $n=5$, the figure is similar to a pentagon with numbers on each vertexes. Does there always exists the way to place $n$ ...
0
votes
2answers
156 views

Find number of solutions of the equation x1+x2+x3 = 41, where x1, x2 and x3 are odd and non negative integers

There are two constraints to this problem: 1) x1, x2 and x3 are non negative integers 2) x1, x2 and x3 are odd If there had been just the first constraint (non negative integer), i would have ...
2
votes
2answers
222 views

BOX Problem A combinatorics question

A big box contains 10 small boxes. Each of these small boxes is either empty or contains 10 boxes which are even smaller. Again, each of these smaller boxes is either empty or contains 10 boxes ...
2
votes
1answer
36 views

Arranging Prime Factors to form Integer Solutions

I have a problem as such: How many solutions in positive integers are there to the equation $x_1 \cdot x_2 \cdot x_3 \cdot x_4 = 2^{20} \cdot 13^{13}$? Let $x_1,\ldots,x_4$ all be distinguishable, ...
3
votes
1answer
101 views

pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
0
votes
2answers
57 views

Probability distributing ice cream satisfying the taste of each person.

Distributing randomly 5 vanilla ice-creams and 5 chocolate ice-creams to 10 people among which 3 prefer vanilla, 2 prefer chocolate and the others do not have preference, what is the probability that ...
0
votes
0answers
49 views

Borsuk Graph and chromatic number

For a positive real number $\alpha < 2$, let $B(n+1,\alpha)$ be the (infinite) Borsuk graph with $S^n$ as the vertex set and with two points connected by an edge iff their distance is at least ...
1
vote
1answer
1k views

What is the probability of of drawing at least one king and one ace in a five card poker hand?

The title problem is just one specific example of a more generalized problem that I'm trying to solve. I'm trying to write an efficient algorithm for calculating the probability of at least k ...
0
votes
1answer
103 views

How many ways are there to travel from the top left corner to the bottom right corner?

Came up with this question when studying combinatorics. How many ways are there to travel from the top left hand corner to the bottom left hand corner of a $m\times n$ block if: (1) in every moves ...
0
votes
3answers
65 views

Problem with permutations

The problem says: We have strings formed by two letters, followed by two digits and then followed by three letters. In each group repetitions are not allowed, but the last group of three letters ...