For 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
2answers
57 views

In AB + BC + AC = N, how can I find all possibilities for A, B and C in less than n³ computational time?

The problem is the one on the title. Given a N, find all possibilies for A, B and C that make this true: $AB+BC+AC = N$when $A \ge B \ge C$. This code in C do the job: ...
0
votes
4answers
61 views

In how many ways can a group of $n$ people composed of six types be created with restrictions?

Suppose we need to create a group of $n \geq 20$ people with the following types and requirements: Scientists, at least 2; Pro Athletes, at least 1; Mathematicians, at least 5; Plumbers, at least 0; ...
2
votes
1answer
56 views

Is there a more concise expression of this product?

In a longer computation, I have stumbled upon the following product, where $k,r \in \mathbb{N}_0$ are fixed numbers: $$\prod_{0 < i_0<i_1<\dots<i_r\leq k} (i_r-i_{r-1})(i_{r-1}-i_{r-2})\...
0
votes
1answer
36 views

Least distance between two points in an equilateral triangle [closed]

Five points lie inside an equilateral triangle of side 2 units.Prove that at least 2 points are no more than a unit distance apart.
0
votes
1answer
38 views

Picking balls from boxes, a logical approach?

You have a box with ten purple balls, five red balls, five blue balls, three yellow balls. You pick out four balls at random. What is the probability of all four balls being the same color? I've ...
11
votes
2answers
467 views

Differentiating the binomial coefficient

I took a lecture in combinatorics this semester and the professor did the following step in a proof: He showed that function $f: x \mapsto \binom{x}{r}$ is convex for $x > r - 1$ (in order to use ...
3
votes
1answer
32 views

How to find number of integral solutions, containing large number of cases?

Number of positive unequal integral solutions of the equation $x+y+z=12$ can be found out knowing the cases it involves: $(1, 2, 9) , (1,3,8), (1,4,7), (1,5,6), (2,3,7), (2,4,6) and (3,4,5)$. Thus, ...
1
vote
2answers
48 views

Problem 14, Ch. 1 from Blitzstein and Hwang, Intro to Probability

You are ordering two pizzas. A pizza can be small, medium, large or extra large, with any combination of 8 possible toppings (getting no toppings is also allowed, as is getting all of 8). How many ...
0
votes
0answers
26 views

Problem 13, Ch1 from Blitzstein and Hwan, Intro to Probability

A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. Thus, a superdeck has $52{\cdot}10=520$ cards, with 10 copies of each card. How many ...
5
votes
5answers
121 views

Prove that $\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$

Prove that $$\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$$ I've tried multiple things that didn't work. Maybe this would help $$\sum_{k=0}^n \binom{3n-k}{2n}=\sum_{k=0}^n \binom{3n-(n-k)}{2n}=\...
0
votes
3answers
68 views

Find the number of sums that you will get A, when A=100?

Problem: Take any number $A \in \Bbb{N} = \{1, 2, 3, \dots\}$, and then take $x, y \in \Bbb{N}$, where $x \ne y$ and $x + y = A$. Find the number of possible choices for $x$ and $y$ when $A=100$. ...
-4
votes
2answers
52 views

b) How many onto functions are there from A to C? [duplicate]

Let $A=\{1,2,3,4\}$ Let $B= \{a,b\}$ Let $C= \{ \text{hiking, baseball, hockey} \}$ a) How many onto functions from A to B $(1,a) (1,b) (2,a) (2,b) (3,a) (3,b) (4,a) (4,b)$ Thus 8. b) How many ...
2
votes
2answers
47 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
1
vote
2answers
108 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
0
votes
0answers
22 views

Consider the system S which can take n input parameters and each parameter can take on m values

(a) What is the maximum number of pairs a single test case for this system can cover? "I know that there are m^n different combinations in this example, but i'm unsure how many pairs a single test ...
0
votes
1answer
44 views

Combination Problem : $6$ Countries , $4$ players from each country

$6$ Countries participate a world tournament . Each country has $4$ players. One Cricket player , One Rugby player , one Volleyball player and one Football player. Need to select a team of $8$ ...
0
votes
1answer
22 views

Least amount of repetitions s.t. probability greater than 1/2

Assume that for a formula $F$ over $n$ variables, there are exactly $k$ allocations that satisfy it. How many random samples from the set $\{0,1\}^n$ are necessary to find an allocation satisfying the ...
2
votes
0answers
31 views

Build a generating function

Build a generating function for $a_r$ ,the number of integer solutions to the equation $e_1+e_2+e_3+e_4=r$ $2\le e_i\le 8$ where $e_1$ is even and $e_2$ is odd The answer I got is $(x^2+x^4+x^6+x^...
3
votes
0answers
49 views

Linear separability / Number of positive solutions of a random linear system

This one is on linear separability of cyclic patterns. The shorter geometric version: Take a ring of length $p$ of randomly assigned mean-free binary values $x_i = \pm 1$, $i = 1 \cdots p$. ...
2
votes
4answers
70 views

Algebraic expression of Prime of form $4k-1$

Every prime of the form $4k+1$ can be written as an algebraic expresion of sum of two squares. Question: If $p=4k-1 $, can it be written as a sum of some powers? (algebraic exprssion like $p= y^3+ (...
1
vote
1answer
25 views

Calculating intersection cardinalities of cover sets

I'm having trouble automating calculation of intersection cardinalities of particular sets. Here are some definitions. Number of available elements is $n$, size of a particular set $S \in \...
0
votes
3answers
43 views

Problem 7, Ch1 from Blitzstein and Hwang, Intro to Probability

I am trying to solve this problem. Two chess players, A and B are going to play 7 games. Each game has three possible outcomes : a win for A (which is a loss for B), a draw(tie) and a loss for A (...
1
vote
1answer
23 views

Number of ways of getting same number when four people throw a die once

Four people are rolling a die once. How many ways None of them get same number Exactly two of them get same number Two of them get the same number Three of them get same number All of them get same ...
3
votes
1answer
43 views

Arbitrary team in moba games.

Imagine you have a moba-game where are N characters and team consists from M players. You have found a team with M players and for a tournament you need to be able to take any combination of M (out of ...
2
votes
0answers
96 views

Number of ways to connect vertices of n squares with line segments

What is the number of ways to connect the vertices of n squares with non-intersecting line segments ? These line segments should not cross the edges of the given squares as well. Obviously $N(3)$ is ...
-4
votes
0answers
40 views

A good Number theory problem [closed]

In a test there are $p$ questions and ($2^p-r$)students gave wrong answer at least $r$ question .The total no of wrong answers are $2047$.Find the possible value of $p$.
0
votes
1answer
46 views

Number of pies and sides combinations

I sell 5 inch savory pies with sides and gravy I am trying to calculate how many possible combinations / options my customers have Simple variables we offer 8 pies 5 sides 2 gravies The variables ...
0
votes
0answers
20 views

enumerating polyominos

Polyominoes are made by gluing together finitely many squares along their edges. They always have connected interiors, but are allowed to have holes. Enumerating polyominoes is a huge subject, and ...
0
votes
1answer
43 views

How many numeric strings of length 8 have exactly three 9's OR exactly three 8's (or both)?

I need help with a question: How many numeric strings of length 8 have exactly three 9's OR exactly three 8's (or both)? Thanks.
3
votes
4answers
90 views

Find the coefficient of $ x^{12}$ in $(1-x^2)^{-5}$

Find the coefficient of $x^{12}$ in $(1-x^2)^{-5}$ What can be said for $x^{17}$ Tried $\frac{1}{(1-x^2)^{5}}$=$\sum_{n=0}^\infty \binom{n+5-1}{n}x^n$ not sure that i can do that with $x^2$
2
votes
2answers
71 views

Show that $\sum_{k=0}^n \frac{(2n)!}{{k!^2(n-k)!}^2}= \binom{2n}{n}^2$

Show that $$\sum_{k=0}^n \frac{(2n)!}{k!^2(n-k)!^2} = \binom{2n}{n}^2.$$ I tried canceling $2n!$ from both sides then moving $k!$ to right but still not sure how to proceed.
6
votes
4answers
166 views

Proof of the summation $n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$?

I was going through a Number Theory book the other day and found this question. It asked for the proof of the following equation: $$n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$$ I tried hard but ...
1
vote
0answers
49 views

Circular permutations with repetitions

$n$ distinct objects have $n!$ (linear) permutations and thus $(n-1)!$ circular permutations. Now consider $m$ objects, some identical, $r_1$ of the first kind, $r_2$ of the second kind, ..., $r_k$ ...
3
votes
1answer
32 views

Why am I under-counting when calculating the probability of a full house?

I was trying to answer this question. Find the probability of getting a full house from a $52$ card deck. That is, find the probability of picking a pair of cards with the same rank (face value), ...
9
votes
2answers
276 views

Counting: how many ways of climbing a stair?

You are climbing a staircase. At each step, you can either make $1$ step climb, or make $2$ steps climb. Say a staircase of height of $3$. You can climb in $3$ ways $(1-1-1,\ 1-2,\ 2-1)$. Say a ...
1
vote
4answers
51 views

Probability: 5 cards drawn at random from a well-shuffled pack of 52 cards [closed]

A poker hand consists of 5 cards drawn at random from a well-shuffled pack of 52 cards. Then, the probability that a poker hand consists of a pair and a triple of equal face values (for example, 2 ...
17
votes
4answers
2k views

Have I found all the numbers less than 50,000 with exactly 11 divisors?

The math problem I am trying to solve is to find all positive integers that meet these two conditions: have exactly 11 divisors are less than 50,000 My starting point is a number with exactly 11 ...
7
votes
1answer
38 views

The size of sets of positive integers not having distinct subsets with equal size and sum

Let us call a set $S$ of positive integers "good" if there does not exist a pair of distinct subsets $A,B\subseteq S$ who have equal size and an equal sum. Equivalently, a set $S$ is good if the ...
2
votes
1answer
33 views

How to find that a number is a sum of multiple of different numbers?

Suppose a product comes in packs of 3, and 5, and a customer demands 8 quantities of that ...
6
votes
1answer
86 views

example of toric varieties with nontrivial first cohomology group

If I remember correctly, when a toric variety is smooth or simplical (the moment polytope is simplicial rational), then there is no odd dimensional cohomology group and the dimension of the even ...
3
votes
4answers
175 views

How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$

Show that if $m$ and $n$ are integers with $0\leq m<n$ then $$\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$$ Attempts: $(-1)^{k}\binom{n}{k}$ is the coefficient of $x^{k}$ in ...
1
vote
2answers
46 views

Probability problem with a die

I've been practicing probability problems lately and I came to this problem A number is formed in the following way. You throw a six-sided die until you get a 6 or until you have thrown it three ...
1
vote
1answer
40 views

How many ways are there to pick k cards in a game of Skat?

In a game of Skat there are 4 suits (spades, hearts, diamonds, clubs) and 8 values (7, 8, 9, 10, jack, queen, king, ace) yielding 32 cards altogether. I'm trying to figure out in how many ways $k \geq ...
0
votes
3answers
57 views

N is a four digit number. If the leftmost digit is removed, the resulting three digit number is 1/9th of N. How many such N are possible? [closed]

N is a four digit number. If the leftmost digit is removed, the resulting three digit number is 1/9th of N. How many such N are possible with solution?
0
votes
2answers
28 views

Probabilities in infinite Bernoulli type of series

While I was trying to solve the 1st problem from here I run into the following problem: find the probability of the events such as $1122213$ or $2122111116$ in infinite series of dice rolls which end ...
3
votes
1answer
67 views

Problem 48 in A First Course in Probability

I have an issue with problem 48 Chapter 2, page 51 in Sheldon Ross' A First Course in Probability (9th edition). The problem is as follows, Given 20 people, what is the probability that among the 12 ...
9
votes
1answer
106 views

Prove that $\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$ is an integer

Let $a$ and $b$ be integers and $n$ a positive integer. Prove that $$\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$$ is an integer. Define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but ...
2
votes
1answer
24 views

Transposal generators like {1, 1, 2, 3, 3, 2}

The sequence {1, 1, 2, 3, 3, 2} generates all the transposals of {1,2,3}. Just cyclically pick positions $n, n+2, n+4$. Is there a sequence like this for 1-4, 1-5, and so on?
0
votes
1answer
35 views

Permutation: Number of ways 4 cars could park

I came across this question in my Algebra textbook: Find the number of ways 4 cars could park right next to each other if the parking slots were: a) in a straight row b) in a circular ...
0
votes
2answers
32 views

How many ways can numbers be split into different groups

If I had the numbers [2,2,2,2,3,3] and I wanted to find the number of ways to split them into two groups, then how would I do it. I know that if I had all different numbers eg.[1,2,3,4,5,6] then I ...