Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially 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.

0
votes
1answer
46 views

How many paths are possible there?

Consider following triangle $$\begin{matrix} x_1 \\ x_2 & x_3 \\ x_4 & x_5 & x_6\\ x_7 & x_8 & x_9 & x_{10} \\ x_{11} & x_{12} & x_{13} & x_{14} & x_{15}\\ x_{...
0
votes
1answer
41 views

Candy bar combinations

A local mart sells 6 kinds of candy bar. You want to buy 15 candy bars. How many possibilities are there if you want more than 5 bars of any one of the kinds? Is there any hint to solve this ...
0
votes
2answers
39 views

Ramsey number: why is R(s, t)=R(t, s)?

So let's assume that $s \leq t$, and we use the following definition: the Ramsey number $R(s, t)$ is the smallest value of $N$ such that under every red-blue coloring of $K_{N}$, there is a red $K_s$ ...
0
votes
1answer
36 views

Finding $E \left[\frac{1}{\bar{X}} \right]$ for $X_1, …,X_n \sim_{iid} Geo(p)$

I am trying to prove that the estimator $\hat{p}=\frac{1}{\bar{X}}$ is unbiased. Since the $X_i$ s are iid geometric, I know that $Y=\sum_{i=1}^n X_i$ is negative binomial. So what I want to do is ...
1
vote
0answers
22 views

Asymptotics of the probability of passengers on wrong airplane seats

In this answer Jack D'Aurizio asserts that the probability $W(s,k)$ of $k$ passengers taking wrong seats on a plane capacity of $s$ seats, or the generating function coefficient $[x^k]g(s,x)$, ...
2
votes
1answer
49 views

binary number maximum 1's

If we are given a binary number we have to find the number of maximum ones that can be obtained if we can invert( $ 1\rightarrow0, 0\rightarrow1$ ) exactly $x$ number of bits in one iteration. We can ...
3
votes
2answers
146 views

Why are there $\frac{(A+1)(A+2)(B+1)}{2}$ triangles in this grid?

Suppose we are to find the number of triangles that exist from the given figure I found one solution that says we let $A$ equal the number of internal lines from the top vertex, $B$ equal the number ...
2
votes
3answers
50 views

Probability- 6 digit number that is built from the numbers 2,5,6,9

A random 6 digit number is picked that is built only from the numbers $2, 5, 6, 9.$ What is the probability that the number can be divided by $3$? What is the probability that the number can be ...
4
votes
4answers
344 views

Combinatorics problem 25 students problem

A class with 25 students, 15 women and 10 men. A committe will be formed by 3 students, a president, a vice president and public relation manager. How many mixed committee can be formed? So, what I ...
0
votes
1answer
30 views

Consider piles of red, blue, and green balls where each pile contains at least 10 balls…

Consider piles of red, blue, and green balls where each pile contains at least 10 balls. In how many ways can $10$ balls be selected if at most $1$ red ball is selected? I've seen answers to similar ...
1
vote
0answers
28 views

Coins in pocket probability problem

In total there are 10 coins: 5: 50 cent coins 4: 10 cent coins 1: 5 cent coin What is the probability that 3 randomly selected coins do not exceed €1? This is my approach: $$P = 1 -\frac{\binom{5}...
0
votes
0answers
24 views

Find invalid values of $Y$

Let $$Y = (\textbf{a})\cdot x_1 + (\textbf{a}+1)\cdot x_2 + (\textbf{a}+2)\cdot x_3 + (\textbf{a}+3)\cdot x_4 + . . . + (\textbf{a}+n)\cdot x_n$$ Where $x_1,x_2,x_3.... x_n$ are all positive integers ...
-1
votes
1answer
25 views

Combinations: There are 30 members

There are $30$ members of the Bay City marching band. Among them, $16$ play the saxophone, $4$ play drums, $8$ play clarinet, and $9$ twirl the baton. No one who plays sax twirls. Everyone who plays ...
0
votes
0answers
19 views

Probability that taxi requiring repair is dispatched to airport C

I'm working through the textbook Mathematical Statistics with Data Analysis 4th edition and didn't understand the solution for question 2.25. It refers to the previous question 2.24 which asks how ...
1
vote
1answer
26 views

Three different medals- gold, silver and bronze- are awarded to athletes in TWO different races…

Three different medals- Gold, Silver and Bronze- are awarded to athletes in two different races. If no athlete may win more than one medal, and there are 6 athletes in total, how many different ...
3
votes
2answers
53 views

$ \sum_{k=0}^n (-1)^{k} {{m+1}\choose k }{{m+n-k}\choose m }= 0$ if $n>0$

I need to show that $ \sum_{k=0}^n (-1)^{k} {{m+1}\choose k }{{m+n-k}\choose m }= 0 $ if $n>0$. Here $m$ is a non negative integer. I am thinking induction, but do I apply it on $m$ or $n$? I ...
0
votes
0answers
28 views

Twelvefold way, alternative proof

I'm looking for a proof of the twelvefold way, where the "balls" are indistinguishable, i. e., the number of equivalence classes of the relation(where $A$ is the domain): $$f \sim g \iff \exists \pi \...
0
votes
0answers
29 views

Show that $ \sum_{k=1}^n (-1)^{k+1} \frac1k {n\choose k }= \sum_{k=1}^n \frac1k$ [duplicate]

I need to show that $$\sum_{k=1}^n (-1)^{k+1} \frac1k {n \choose k} = \sum_{k=1}^n \frac1k,$$ where $n$ is a positive integer. Can anyone tell me how to do this? I tried induction but couldn't ...
1
vote
0answers
26 views

An interesting way of partitioning with inner ordered combinations

Assume $ K $ labeled blocks $ s_1, s_2, \dots, s_K $ ($ s_1 < s_2 < \dots < s_K $) that arrive sequentially and need to be accomodated as they arrive in $ N $ containers (partitions with ...
2
votes
1answer
81 views

What is a mathematical solution to this problem? (Project Euler #106)

I've already asked this question before, but then I realized that wording was, unfortunately, quite confusing. The statement of the problem is following: Let $S(A)$ represent the sum of elements ...
1
vote
1answer
27 views

Finding the number of triples given certain conditions.

Find the total number of ordered triples ($A_1,A_2,A_3$) such that $$A_1 \cup A_2 \cup A_3=\{1,2,3,4,5,6,7,8,9,10\}$$ and $$A_1\cap A_2\cap A_3=\emptyset.$$ $$\text{Attempt}.$$ From second condition, ...
2
votes
0answers
39 views

How many equal partitions of the set are trivially unequal? [duplicate]

Suppose we have set $S=\{x_1,x_2,....,x_{2n-1},x_{2n}\}$ , where $x_1 < x_2 ..... <x_{2n-1}< x_{2n}$ We have non-empty disjoint subsets $A$ and $B$ both having size $n$. Question is, how ...
5
votes
3answers
119 views

Summation Involving Product Of Two Identical Polynomials.

Recently I stuck, to a problem. However I rarely think that there is some proper formula for this problem, but here I am in search of algorithm's or theorem that relate to this problem or can solve ...
8
votes
1answer
72 views

Putnam Combinatorics/Set Theory Question

This is a problem from the 1985 Putnam Exam: Determine, with proof, the number of ordered triples $(A_1, A_2, A_3)$ of sets with (i) $A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10\},$ and (ii) $...
4
votes
1answer
44 views

How many ways can 15 people be divided into 3 classes of 5, if there are 3 blond people…

How many ways can 15 people be divided into 3 classes of 5, if there are 3 blond people and each class needs to have 1 blond person? My attempt at the question: First, the 3 blond people are ...
-1
votes
1answer
21 views

Number of ways to pull balls

I have a box that contains 9 balls indistinguishable by touching: $3$ balls are white, $2$ balls are black, and $4$ are red. I do this operation 4 times: I randomly pick a ball, i note its color ...
0
votes
0answers
23 views

Number of combinations from a set with repeated items [duplicate]

In trying to solve the problem stated below, I'm not sure how I can find the total number of combinations possible? "Find the probability that 3 vowels and 2 consonants are chosen when five letters ...
0
votes
0answers
42 views

In what order we need to put weights on scale?

I' am doing my homework in programming, and I don't know how to solve this problem: We have a set of n weights, we are putting them on a scale one by one until all weights is used. We also have ...
1
vote
1answer
37 views

What is the probability of integer 1 occurring only once in a 6-digit number generated from 1, 2, 3?

So seeing that the six digits number is generated from integers 1, 2, 3. What is the probability that: Integer 1 will occur once? Integer 2 - 2 times? Integer 3 - 3 times? I know that all possible ...
0
votes
2answers
22 views

Conditional probability on hypergeometric distribution

I'm working through a practice question in combinatorics and my first attempt at counting through a particular problem has yielded the wrong answer (I have a copy of the actual solutions, for ...
4
votes
1answer
60 views

Proof that $\sum_{k=1}^n(-1)^k(k-1)!{n \brace k} = 0$ in use combinatoric interpretation

Proof that $$\\\sum_{k=1}^n(-1)^k(k-1)!{n \brace k} = 0\\$$ where $n > 1$. I know how it can be done with standard algebraic methods: Solution $$ \begin{align*} \sum^n_{k=1}(-1)^k(k-...
0
votes
0answers
30 views

Is there a concept or a terminology describing the sizes of inverse images of a function?

Now I am studying some applications of a class of special functions $f$ from a finite set $A$ onto another finite set $B$. Let $I(f)$ denote the sizes of inverse images of a function $f$, i.e., $$I(f)=...
-1
votes
0answers
19 views

Calculating Permutations with no values within 2 positions of each other being adjacent.

I have a problem where I need to generate permutations of length b out of the set 1 to 48. However, I can't have any two adjacent values be within 1 of each other. Likewise I can't have any set of ...
-4
votes
2answers
44 views

The math department of a college has 20 faculty members, of whom 5 are women and 15 are men…

Continued question: "A curriculum committee of 4 faculty members is to be selected. How many ways are there to select the committee that has more women than men?" Possible Ways: M M M M F F F F F ...
1
vote
1answer
27 views

Circular Permutations. Difference between clockwise and anti-clockwise permutations.

Please tell me the total permutations possible of the beads in a necklace where all the beads are distinct. The necklace consists of n distinct beads. Answer as per me: the answer is (n-1)! as the ...
2
votes
2answers
40 views

number of ways to distribute different balls among children

In how many ways can eight different balls be distributed among 4 kids, s.t each gets at least one. my approach: so I read a similar question here and figured out I should do this: $$4^8 - \binom{4}{...
1
vote
0answers
25 views

Combinatorics, special permutations of cubic cells.

I'm trying to produce a set of permutations of 3 axis Cartesian coordinates which are limited by a specific geometric constraint: Perhaps the simplest way to visualize this is with a Sudoku-like game ...
0
votes
1answer
37 views

Can any counting situation that works for one side of an identity work for the other (combinatorial proof)

If I come up with a situation that works for one side of a combinatorial proof, does some interpretation always exist for how the other side counts that same situation? Or is it possible that one ...
1
vote
1answer
31 views

Creating a generating function for the Stirling transform

Does there exist a sequence $c_n$ such that $$S(n, k) = \frac{c_n}{c_k c_{n - k}}$$ for $0 \leq k \leq n$, where $S(n, k)$ are the Stirling numbers of the second kind? I ask because I'm trying to ...
1
vote
0answers
84 views

What is the formula for the number of connected graphs with N vertices of max. degree up to 4? Leaving $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + …$

It is known that F(x) is the generating function of the counting sequence of connected simple graphs with N vertices is given by: $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + ...$ where the ...
0
votes
1answer
30 views

With repetition, no order. Probability of drawing atleast 18 distinct balls, when there are 20 different balls and one has 50 draws?

I came up with this today, however I could not figure out a solution to this problem. Say, you have a pool of 20 different balls. Therefore, the probability of drawing one of the balls is equal to ...
0
votes
2answers
40 views

Solution mod 2 of polynomial equation

Can one find a polynomial $p(x,y)$ such that it is integer for integer $x,y$ and it satisfies $$ p(x,y) + p(y,x) = x^2 + y^2 +1 \mod 2$$ or prove that it is not possible?
0
votes
2answers
17 views

Probability of drawing exactly X previously unseen numbers

Let's say we have $M$ balls, numbered $1$ to $M$, in a sack. Let us say we have already seen $Y$ of those balls. We now draw $N$ balls without replacement. What is the probability of seeing exactly $X$...
-3
votes
0answers
24 views

Permutations/Probability [duplicate]

A club has $n$ members and $r$ officers. In how many ways can we choose $r$ different officers from the members of the club? Answer would have to start with: # of ways to pick $r$ officers from $n$ ...
1
vote
0answers
17 views

Bounding the space of translation invariant type polynomials

Given a field $k$ of characteristic 0, one can show that the space of translation invariant polynomials in $n$ variables, homogeneous of degree $N$ is spanned by $$ \{ (x_1-x_2)^{d_1}(x_2-x_3)^{d_3}\...
1
vote
1answer
35 views

Number of subgroups of index 2 in $(C_2)^3\times C_3$

I need to count the number of subgroups of index 2 in $(C_2)^3\times C_3$. I think there are 3, because we have to take $C_3$ and then we have 3 choices for a $C_2$ not to pick. However, a classmate ...
4
votes
5answers
66 views

Why is row $n = 2^x$ in Pascal's triangle have all even numbers except the $1$'s?

In row $n = 2^x$, $x$ being a positive integer, in the Pascal's triangle, all entries except the two $1$'s in extreme left and right are even. I tried to prove but I couldn't. Here is my try:- ...
0
votes
1answer
54 views

Count the non-decreasing sequences of positive integers below a given one, for component-wise ordering

How do you find the number of unique integer sequences of a nondecreasing sequences length $n$ with these conditions? $$ a_{n+1} \geq a_{n}$$ Possible rephrasing: Given a particular nondecreasing ...
1
vote
1answer
68 views

Explanation of Freeman Dyson's solution of the counterfeit coin problem

Freeman Dyson's paper, The problem of the pennies Math. Gaz., 30 (1946) 231-234, offers a solution to a counterfeit coin detection problem. I quote his solution of one case as follows. I would ...
2
votes
1answer
68 views

Which integer partitions correspond to the most set partitions?

Which integer partitions of n correspond to the most distinct set partitions? For small n where it is feasible to calculate these values for every integer partition and compare, this is a ...